Archive for the ‘Probability’ Category

UVA – 11628 – Another lottery   Leave a comment


Only last round matters since 2^i > 2^(i-1) + 2^(i-2) … + 2^0

#include <stdio.h>
long long int p[1000000];
long long int gcd(long long int a,long long int b)
{
	return (b==0)?a:gcd(b,a%b);
}
int main()
{
	int n,m;
	while(1)
	{
		scanf("%d %d",&n,&m);
		if(!n && !m)return 0;
		int i,j,k;
		for(i=0;i<n;i++)
		{
			for(j=0;j<m-1;j++)scanf("%d",&k);
			scanf("%d",&k);
			p[i]=k;
		}
		long long int sum = 0;
		for(i=0;i<n;i++)
			sum+=p[i];
		for(i=0;i<n;i++)
		{
			long long int x = p[i];
			if(x)
			{
				long long int g = gcd(x,sum);
				printf("%lld / %lld\n",x/g,sum/g);
			}
			else
				puts("0 / 1");
		}
	}
	return 0;
}

Posted June 27, 2012 by epicrado in Probability

UVA – 11500 – Vampires   Leave a comment


Well analyzing the problem a bit we can represent it as a state graph where each state is connected to two states one if first vampire won current dice roll and one if it lost current dice roll
example
for the game
1 1 3 1
(2,0)<–0.5—(1,1)–0.5–>(0,2)
The left most and right most states of course aren’t connected to any states as the battle has ended.

Such a problem can be solved easily when represented as a matrix let s[i] probability given being at current state and s[i-1] be the state that we can reach by wining current dice roll, s[i+1] the state we can reach by losing current dice roll, thus
for all i
s[i] = w * s[i-1] + (1-w) * s[i+1]
Except for those left,right most states (i.e battle already ended)
s[0]=1
s[n]=0

we can represent this as a system of linear equations
s[i] – w * s[i-1] – (1-w) * s[i+1] = 0 for all i except i = 0 and i = n
s[0] = 1
s[n] = 0
running gauss jordan algorithm should give the solution to this problem in O(n^3) where n is at most 20 or so.

More analysis to the state graph should give us more efficient solution
starting at s[n-1] we have
s[n-1] = w * s[n-2] + (1-w)*0 = w * s[n-2] (1)
s[n-2] = w * s[n-3] + (1-w)*s[n-1] (2)
with little substitution we can get
s[n-2] = k * s[n-3]

thus for any state i we can represent it as s[i] = a[i] * s[i-1] where a is some coefficient that depends on i
also knowing that s[0]=1
then we can compute s[i] for any i, and print the answer for the initial state, as we see this little analysis gave us an O(n) solution which is much more efficient and easier code.

#include <stdio.h>
int main()
{
	double a[30];
	while(1)
	{
		int ev1,ev2,at,d;
		scanf("%d %d %d %d",&ev1,&ev2,&at,&d);
		if(!ev1 && !ev2 && !at && !d)return 0;
		double w = at * 1.00 / 6;
		double l = 1-w;
		int c1 = (ev1+d-1)/d;
		int c2 = (ev2+d-1)/d;
		int tot = c1+c2;
		int i;
		for(i = 0;i<=tot;i++)
			a[i]=0;
		a[0]=1;
		while(tot-->1)
			a[tot]=w/(1-l*a[tot+1]);
		double p = 1;
		for(i = 1;i<=c2;i++)
			p*=a[i];
		printf("%.1lf\n",p*100);
	}
	return 0;
}


Posted June 27, 2012 by epicrado in Probability

UVA – 11427 – Expect the Expected   Leave a comment


Let A be the event of successfully applying the strategy in a single day
let p = Pr(A)
let q = 1-p = Pr(A’) ,then q is the probability of failing to apply the strategy in a single day
let the R.V X be number of days till the event A’ occur.
Then X follows Geometric Distribution and E(X) = 1/q

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class ExpectTheExpected {
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(in.readLine());
		int cc = 1;
		while (tc-- > 0) {
			String[] arr = in.readLine().split(" ");
			String[] frac = arr[0].split("/");
			int num = Integer.parseInt(frac[0]);
			int denum = Integer.parseInt(frac[1]);
			int n = Integer.parseInt(arr[1]);
			double[][] dp = new double[n + 1][n + 1];// state is [won][lost]
			for (int j = 0; j < dp.length; j++) {
				for (int i = 0; i < dp.length; i++)
					if ((i + j) * num < i * denum && i + j <= n) {
						dp[i][j] = 1;
						break;
					}
			}
			// transition is p*dp[i+1][j] + (1-p)*dp[i][j+1]
			for (int i = n; i >= 0; i--) {
				for (int j = n; j >= 0; j--) {
					if (dp[i][j] == 0) {
						if (i + 1 + j <= n) {
							dp[i][j] += (dp[i + 1][j] * num) / denum;
							dp[i][j] += (dp[i][j + 1] * (denum - num)) / denum;
						}
					}
				}
			}
			System.out.printf("Case #%d: %d\n", cc++,
					(int) (1 / (1 - dp[0][0])));
		}
	}
}

Posted February 8, 2012 by epicrado in Dynamic programming, Probability

UVA – 10169 – Urn-ball Probabilities !   Leave a comment


import java.util.Scanner;

public class UrnBall {
	public static void main(String[] args) {
		double[] dp1 = new double[1000001];
		int[] dp2 = new int[1000001];
		double rem = 1;
		for (int i = 1; i < dp1.length; i++) {
			int u1 = i;
			int u2 = i + 1;
			dp1[i] = dp1[i - 1] + (1.00 / u1) * (1.00 / u2) * (1 - dp1[i - 1]);
			double k = rem;
			k = k * u1 * u2;
			int count = 0;
			while (k > 10) {
				k /= 10;
				count++;
			}
			rem = k;
			dp2[i] = dp2[i - 1] + count;
		}
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int m = in.nextInt();
			System.out.printf("%.6f %d\n", dp1[m], dp2[m]);
		}
	}
}

Posted February 8, 2012 by epicrado in Dynamic programming, Probability

UVA – 10648 – Chocolate Box   Leave a comment


Simple if you calculate 1-p.

import java.util.Scanner;

public class ChocolateBox {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int tc = 1;
		while (true) {
			int n = in.nextInt();
			if (n == -1)
				break;
			int m = in.nextInt();
			double[][] p = new double[n + 1][m + 1];
			p[0][0] = 1;
			for (int i = 1; i <= n; i++) {
				for (int j = 0; j <= m; j++) {
					p[i][j] = p[i - 1][j] * (m - j) / m
							+ ((j >= 1) ? p[i - 1][j - 1] * j / m : 0);
				}
			}
			System.out.printf("Case %d: %.7f\n", tc++, 1 - p[n][m]);
		}
	}
}

Posted February 8, 2012 by epicrado in Dynamic programming, Probability

UVA – 11762 – Race to 1   Leave a comment


The problem can be decomposed to
Calculating Number of primes in an interval:easy
Calculating Number of distinct prime factors for a number:easy
Calculating the expected value:hard
Suppose we want to calculate E(N) where N is a number,k is the number of it’s distinct prime factors and p is the number of primes < n
thus
E(N)=1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak)) + ((p-k)/p) * E(N)
it means after one step we can choose a correct prime numbers(from the factors of N) or one of the wrong ones from (p-k) ones
such a recurrence kan be changed to
E(N) – ((p-k)/p) * E(N) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
E(N)*(k/p) = 1+(1/p)*(E(N/a1) + E(N/a2) + E(N/a3) … + E(N/ak))
We can apply dynamic programming then.

import java.util.Arrays;
import java.util.Scanner;
import java.util.TreeSet;

public class RaceTo1 {
	public static void main(String[] args) {
		int[] primes = new int[1000001];
		int[] primef = new int[1000001];
		int[] df = new int[1000001];
		double[] dp = new double[1000001];
		Arrays.fill(primes, 1);
		primes[0] = primes[1] = 0;
		for (int i = 2; i * i < primes.length; i++)
			if (primes[i] == 1)
				for (int j = i * i; j < primes.length; j += i) {
					primef[j] = i;
					primes[j] = 0;
				}
		for (int i = 2; i < primes.length; i++) {
			primes[i] += primes[i - 1];
			if (primef[i] == 0)
				primef[i] = i;
		}
		df[0] = df[1] = 0;
		for (int i = 2; i < df.length; i++)
			df[i] = 1 + df[i / primef[i]]
					- (((i / primef[i]) % primef[i] == 0) ? 1 : 0);
		dp[1] = 0;
		for (int i = 2; i < dp.length; i++) {
			TreeSet<Integer> factors = new TreeSet<Integer>();
			int k = i;
			while (primef[k] != 0) {
				factors.add(primef[k]);
				k /= primef[k];
			}
			double g = 0;
			for (int j : factors)
				g += dp[i / j];
			g = (g + primes[i]) / factors.size();
			dp[i] = g;
		}
		Scanner in = new Scanner(System.in);
		int tc = in.nextInt();
		int cc = 1;
		while (tc-- > 0) {
			int n = in.nextInt();
			System.out.printf("Case %d: %.9f\n", cc++, dp[n]);
		}
	}
}

Posted February 8, 2012 by epicrado in Dynamic programming, Probability

UVA – 941 – Permutations   1 comment


import java.util.*;

public class Permutations {
	public static long factorial(int n) {
		long res = 1;
		for (int i = 2; i <= n; i++)
			res *= i;
		return res;
	}

	public static String nThPermutation(String s, long n) {
		char[] arr = s.toCharArray();
		Arrays.sort(arr);
		StringBuilder sb = new StringBuilder(new String(arr));
		String res = "";
		while (n != 0) {
			int k = (int) (n / factorial(sb.length() - 1));
			long mod = n % factorial(sb.length() - 1);
			res = res + sb.charAt(k);
			sb.deleteCharAt(k);
			n = mod;
		}
		return res + sb;
	}

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int TC = in.nextInt();
		while (TC-- > 0) {
			String s = in.next();
			long n = in.nextLong();
			char[] arr = s.toCharArray();
			Arrays.sort(arr);
			System.out.println(nThPermutation(new String(arr), n));
		}
	}
}

Posted October 28, 2011 by epicrado in Factorials, Mathematics, Probability, String Processing