Archive for the ‘Tutorials’ Category

NIM Game   Leave a comment


In NIM Game you have n piles each contains ai (0≤i<n) stones, two players alternate turns in each turn a player may remove any positive number of stones from a single pile, the player who cannot make a move loses the game.

Here’s an example n = 1,a0 = 30

First player take 29 stones.

Second player take 1 stone.

First player loses (a0 = 0).

However First player could’ve won if he took 30 stones in the first turn.

Another example n = 2,a0 =3,a1 = 3.

First player take 3 stones from a0.

Second player take 3 stones from a1.

Try playing the game here Stone game reading the next part

If both players play optimally who will win the game?

We can easily find who will win the game by calculating the bitwise XOR of all pile sizes(NIM sum) if this number is zero then second player wins otherwise first player wins.

So why does this work ? You can spend sometime trying to get some intuition by applying this rule on games with N ≤ 2, however when n grows a mathematical proof works best.

Here’s a sketch of a proof (Note: ^ is the bitwise xor)

lets assume we have piles a0,a1,…,an we prove that if a0^a1^…^an = 0 then we are in a losing position, otherwise we are in a winning position.

we prove the following

  • A-base case if all piles contain 0 stones then we are in a losing state (0 ^ 0 ^ .. ^ 0 = 0)
  • B-being in a losing state means that any move we make will put the opponent in a winning state

proof:

first being in a losing state means

a0 ^ a1 ^ a2 … ^ an = 0

lets assume without the loss of generality that we picked pile a0 to make our move and removed k (0<k≤an) stones from it

we need to prove that

(a0 – k) ^ a1 ^ a2 … ^ an != 0

starting from

a0 ^ a1 ^ a2 … ^ an = 0 xor both sides by a0 ^ (a0 – k)

we get

(a0 – k) ^ a1 ^ a2 … ^ an = a0 ^ (a0 – k)

but a0 ^ (a0 – k) will always be non zero for positive values of k.

  • C-being in a wining state means that there exists a move that will put the opponent in a losing state

proof:

assume that

a0 ^ a1 ^ a2 … ^ an = x

lets write x in binary, and look at the highest bit set there exists at least one pile that has that bit set assume without the loss of generality that this pile a0

we need to prove that there’s some POSITIVE k such that

(a0-k) ^ a1 ^ a2 … ^ an = 0

but (a0-k) ^ a1 ^ a2 … ^ an = x ^ a0 ^ (a0 – k)

thus we need to solve x ^ a0 ^ (a0 – k) = 0

xor both sides by a0 – k

we get

x ^ a0 = a0 – k which means

k = a0 – (x ^ a0) and with the assumption that a0 has the highest bit in x means that x ^ a0 is strictly less than a0 thus k is positive and we’re done.

using A,B,C we can use induction to obtain the complete proof.

Useful links

Play NIM game

Sample Problems

Stone game

Exclusively Edible

Box Game (Not direct NIM but try to get an observation and prove it in a similar way)

Advertisements

Posted June 25, 2013 by epicrado in Mathematics, Tutorials

Dynamic Programming   3 comments


Q:What is dynamic programming ? Why should you use it ?

Dynamic programming is a paradigm we can apply to some problems to reduce running time usually from exponential to polynomial, it depends mainly on dividing the problems into smaller subproblems and solving each subproblem then combining the result of those subproblems to solve the larger problem, And avoiding solving the same subproblem more than once.

To understand how is this done let’s take a simple example
assume we use the following recursive function to calculate the nth fibonacci number

long slow_fib(int n) {
	if (n == 0 || n == 1)
		return 1;
	return slow_fib(n - 1) + slow_fib(n - 2);
}

Now what’s the running time for this function ? it looks as if it’s O(2^n) however it’s a bit faster the accurate running time should be O(fib(n)).
This is too big for large values of n
fib(100)=573147844013817084101 which is too large

So how can we improve that ?
Let’s take a look at the recursion tree formed by calling slow_fib(6)

Why running time is exponential ?
Many subproblems are solved more than once.
fib(5) is called one time
fib(4) is called two times
fib(3) is called three times
fib(2) is called five times
fib(1) is called eight times
fib(0) is called five times
notice number of calls is also fibonacci numbers.

What if we solve each subproblem exactly once and store its result in some table, whenever we need it again we just retrieve it from the table.
We’ll use -1 as a flag to indicate that fib(n) isn’t calculated so we fill the array memo with -1.

int MAXN = 100;
long[] memo = new long[MAXN + 1];//fill with -1
long fib(int n) {
	if (memo[n] != -1)
		return memo[n];
	else {
		if (n == 0 || n == 1)
			memo[n] = 1;
		else
			memo[n] = fib(n - 1) + fib(n - 2);
		return memo[n];
	}
}

Now it’s guaranteed that each subproblem (i.e fib(i)) will be solved/evaluated exactly once,and whenever we need it again we’ll just retrieve it from the table.

Now what the Running time ?
Each subproblem is solved only once, and for each subproblem we do 1 operation to reach smaller subproblems.

Number of subproblems ? n
Operations per subproblem ? 1

Total running time O(n)

Lets see another problem

Treasure map

Imagine a person standing at the top level of this pyramid and wants to get to the bottom level collecting as much treasures as possible, at any given cell he can go to the one below it to the left or below it to the right, the amount of treasure he collects is the sum of the numbers on the cells he used.

A recursive solution
Let F(i,j) be the solution for the problem if we are currently standing at the ith row and jth column, the neighbours of cell i,j are i+1,j and i+1,j+1

Being at the ith cell and jth row guarantees that we’ve taken treasures at map[i][j] then we have two choices either go to i+1,j or i+1,j+1 so we evaluate both F(i+1,j) and F(i+1,j+1) and choose the best among them.
So a simple recurrence for solving the problem would be
F(i,j) = map[i][j] if (i == n-1)
F(i,j) = map[i][j] + max(F(i+1,j),F(i+1,j+1)) otherwise
The answer to the problem should be F(0,0)

int n;
int[][] map;
int slow_treasure_map(int i, int j) {
	if (i == n - 1)
		return map[i][j];
	else
		return map[i][j]
				+ max(slow_treasure_map(i + 1, j),
						slow_treasure_map(i + 1, j + 1));
}

Running time ? O(2^n)
Why? at any given step we have two choices and we do n-1 steps.

Now how to improve this ?

Lets try to save time by avoiding solving some subproblems more than once, but first we need to see if there’s overlapping subproblems ( subproblems which are solved more than once )
First imagine we took path in red

We gained 3 + 3 and we are going to solve F(2,1)
Another path could be this one
We gained 3 + -5 and we are going to solve F(2,1)
for those two paths F(2,1) is the same but we evaluate it again, and the result of F(2,1) is totally independant of we’ve did to reach F(2,1)

Its obvious now that we solve some subproblems more than once, and this should be avoided to reduce the number of operations done.

So we should store the solution for each subproblem in a table and whenever we need to solution for this subproblem we first check if it exists on the table then we return it immediately, otherwise we should solve it and store the solution in the table.

For the fibonacci example the table was memo[n], however for this problem it’ll be two dimensional memo[n][n] as the problems now depend on two parameters ( current row and current column )
We also added the array solved to tell us whether we’ve solved the problem (i,j) before or not as -1 as a flag won’t work ( result can be -1 )

int n;
int[][] map;
int[][] memo;
boolean[][] solved;
int treasure_map(int i, int j) {
	if (solved[i][j])
		return memo[i][j];
	else {
		memo[i][j] = map[i][j];
		if (i < n - 1)
			memo[i][j] = memo[i][j]
					+ max(treasure_map(i + 1, j),
							treasure_map(i + 1, j + 1));
		solved[i][j] = true;
		return memo[i][j];
	}
}

Running time ? O(n^2) as  number of problems is n^2 and for each problem we do 1 operation

Notice here we avoided using the treasures gained from the current partial path as a parameter in the recurrence as in:

F(i,j,gain) = max(F(i+1,j,gain+map[i][j]),F(i+1,j+1,gain+map[i][j]))
Because this increases the the dependency of the subproblems on what we did to reach them, and we don’t really need to do this as it’ll increase our parameters for no good.

Now there’s a couple of questions

When  to use dynamic programming ?

To be able to use dynamic programming the problem we’re solving must have two properties

  1. Optimal substructure: meaning we can divide the larger problem into smaller problems and solve each of them optimally then combine their solutions somehow to obtain the optimal solution for the larger problem.
  2. Overlapping subproblems: meaning that there are subproblems which are solved more than once so applying dynamic programming would be useful then and save time, otherwise it would be  a waste of space to store solution for all possible subproblems.

How do we know the dimensions of the table we need to as our memo ?

To answer this question let’s introduce some definitions

State : The set of parameters which totally describe the problem and allows us to solve it immediately or divide it into smaller subproblems.

As in the fibonacci problem, the problem was to calculate nth fibonacci number so the state would be a single parameter just n.

Transition : Actions we can take to move from one state to another(usually from a larger problem to a smaller one).

In the treasure map problem,the problem was to calculate the maximum number of treasures that can be collected given we’re at the ith row and jth column so our state would be two parameters i and j, we may also ask ourselves what would happen if we used only i as our parameter for memoization i.e memo[n] only ,this would mean that result for F(i,j) would be equivalent then to the result for F(i,k) for k!=j which is not always true as state i,j isn’t equivalent to state i,k, Then the minimum number of parameters needed is 2 so we’ll need a two dimensional table.

So the dimensions of the table is usually the number of parameters in the state,also the state may be simple or complicated it may be some integers or subset of a set or both you’ll encounter more complicated states in later problems.

Now before we take more examples lets see how we should approach a dynamic programming problem

  • First we should try to find the state or basically describe the problem in a minimum number of parameters, this is usually done by manually solving the sample test data or even generating some small sample and trying to solve it or take random decisions and see how the problem changes and how to describe it before, after those changes.
  • Next we should look into the decisions we can take and see how this affects our state i.e find possible transitions between states.
  • We may also need to think of  base cases (problems which are already small enough to know the answer for immediately without further division into smaller problems)
  • Then we should express our solution as a recurrence and start coding it.

Usually Dynamic programming can be done in two ways

Top down dynamic programming (recursive / memoization) : writing a recursive function that solves the problems in the order required, this is usually easier to code and requires less thinking.
Bottom up dynamic programming (iterative) : usually this requires more work first we figure out the the order in which our dynamic programming table is filled and then use loops to fill it .

Bottom up example : fibonacci
We may notice that Fib(i) = Fib(i-1)+Fib(i-2) so if we knew the result of Fib(i-1) and Fib(i-2) we can easily calculate Fib(i),the key idea for bottom up dynamic programming is to fill the iterate over the table in such an order so that if we need to calculate solution for some problem then all problems which this problem depends on are already solved
here’s the code

long bottom_up_fib(int n) {
	long[] dp = new long[n + 1];
	dp[0] = 1;
	dp[1] = 1;
	for (int i = 2; i <= n; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[n];
}

For beginners I really recommend solving problems using the top down fashion and save the effort for finding the recurrence that solves the problem after you master this it shouldn’t be hard to start writing using bottom up dynamic programming.

Time/memory complexity of a dynamic programming algorithm
Time : number of possible states * number of operations for state transitions
Space : number of possible states
Sample problems

Combinations:
In How many ways can you choose r people out of n people ?
0<= r <= n <= 20
Solution
For this problem its obvious that the state is (n,r) as this what describes the problem but how to reach other states from (n,r)?
First let’s imagine that we have n people standing in some queue or so
Now look at the very first person, what options do we have for this person ?
Well we can either choose him or not
If we choose him then we’ll reduce the problem to (n-1,r-1)
If we don’t choose him then we’ll reduce the problem to (n-1,r) (we didn’t choose him now and shouldn’t ask if we should choose him again)
So if the answer to our problem is C(n,r),then
C(n,r)=C(n-1,r-1)+C(n-1,r), And the base case should be C(n,0)=1 and C(0,r)=0 for r!=0
The solution runs in O(n^2)
Top down solution

long[][] memo;
long top_down_C(int n, int r) {
	if (memo[n][r] != -1)
		return memo[n][r];
	else if (r == 0) {
		memo[n][r] = 1;
		return memo[n][r];
	} else if (n == 0) {
		memo[n][r] = 0;
		return memo[n][r];
	} else {
		memo[n][r] = top_down_C(n - 1, r - 1) + top_down_C(n - 1, r);
		return memo[n][r];
	}
}

Bottom up solution

long bottom_up_C(int n, int r) {
	long C[][] = new long[n + 1][n + 1];
	for (int i = 0; i < C.length; i++)
		C[i][0] = 1;
	for (int i = 1; i < C.length; i++)
		C[0][i] = 0;
	for (int i = 1; i < C.length; i++)
		for (int j = 1; j < C[i].length; j++)
			C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
	return C[n][r];
}

Classical problem:Knapsack
Given a set of n items each having weight and value (given as arrays where the ith element has weight[i] weight and value[i] value) and a Bag with maximum weight W ,choose the a subset having maximum total value(total value of is the sum of all values of items in the subset ) and fits in the bag (sum of weights <= W)


0<=n<=200,0<=W<=1000,-1000<=value[i]<=1000,0<=weight[i]<=W
Solution
Observation:Order of adding the items to the sack doesn’t matter.

Whenever the order doesn’t matter, use a specific order to process the data in.

This allows us to choose a certain order to process items in, and for each item we would have to choices either take it or leave it.(i.e process first item take it or leave it then process the second item…)

So far we’ll have in our state the index of the next item to be processed,and for the given item we should try to take it or leave it and use the maximum from both, But how do we make sure that we’ll not cross the maximum weight allowed of the bag ?
We’ll need another parameter for this which would be the weight left in the bag.
So the state now would be (i,WeighLeft)

  • i : index of the next item to be processed.
  • WeighLeft : weight available in the bag.

And the transition would be

  • Either take the ith element and gain v[i] value and lose w[i] from WeightLeft then solve for i + 1,given that
  • Leave it and solve for i + 1

Here’s the recurrence that solves the problem
F(i,W) = max(value[i]+F(i+1,W-weight[i]),F(i+1,W)) if w[i] <= W
F(i,W) = F(i+1,W) otherwise

Number of states n * W
Transitions take 1 operation
Overall running time O(n * W)

Q:can you create test cases to show that this problem has overlapping subproblems?
TODO:think of the base cases and implement the solution using both top down and bottom up approaches.

The Antique Trader
A Trader has n antiques put on a shelf,on each year he sells exactly a single antique, the ith antique have value[i] value, furthermore if he sold the ith antique in the jth year he gets j * value[i] pounds

If the trader is only allowed to sell either the leftmost antique or rightmost antique at any given year find the maximum amount of money he can make.

0<=n<=100

Solution
Lets assume we have the items placed on the shelf, being at year 1 what can we do ? we can either sell the first item or the last item if we sold the first item, at the next year we would be having an array that has the bounds of (1,n-1) and if we sold the last element we would have an array that has the bounds of (0,n-2) making more operations will show us that at any state we’ll be holding a subarray of the original array

So how do we represent that ? we use two integers l,r that represent the start and the end of the subarray, at any given state we’ll have two options either sell the left element or the right element

so the state would be (l,r,year)

  • l : index of leftmost element.
  • r : index of the rightmost element.
  • year : current year we’re at

and the possible transitions would be

  • sell the leftmost element and go from (l,r,year) to (l+1,r,year+1)
  • sell the rightmost element and go from (l,r,year) to (l,r-1,year+1)

Number of states is approximately n * n * n
Transitions take 1 time
so overall running time is O(n^3) which suits well for n<=100
But What if n <= 1000 ?
The question is how do we get our O(n^3) algorithm to run in time for n <= 1000
There’s many ways to optimize a dynamic programming solution one way is

Drop a parameter recover it from the others.

This means that we should check if we can reduce the number of states by reducing the parameters ,this can be done by checking if we have some parameters that depends on other parameters like if we have the state (A,B,C) and we have C=f(A,B) where f is some function then we can safely remove C from the state and whenever we need it we just compute it using A and B
now how do we apply this in our problem here
lets try some values of L,R and see if we can know the year
0,n-1 at year 1
0,n-2 at year 2
1,n-1 at year 2

the current year would be 1 + number of elements sold
so we can use year = f(l,r) where f(l,r) = n+1-(r-l+1)
we can easily recover year from l,r so keeping it just adds redundant states and increases the running time for nothing so we safely remove it.
now the recurrence that solves the problem is
max_gain(l,r) = f(l,r) * value[l] if(l==r)
max_gain(l,r) = max(f(l,r) * value[l]+max_gain(l+1,r) , f(l,r) * value[r] + max_gain(l,r-1))
otherwise
now the running time is O(n^2)

Codeforces Round #89 DIV2 D
After reading the problem statement we can reduce the problem to a simpler one(one without story) and it is, how many binary numbers having n1 zeroes,n2 ones with maximum number of consecutive zeroes k1 and maximum number of consecutive zeroes k2.
0<=n1,n2<=100 and 0<=k1,k2<=10
Return the answer modulo 100000000

Solution
Let’s imagine we’re creating a binary number using n1 zeroes,n2 ones what options do we have?

  • add a ‘0’ to the beginning then go to (n1-1,n2) this is only valid if n1>0
  • add a ‘1’ to the beginning then go to (n1,n2-1) this is only valid if n2>0

So far our state is (n1,n2) but yet we didn’t solve the problem as we didn’t put any control on the number of consecutive ones or the number of consecutive zeroes.

Q:What would be the output if we coded the solution this way?
A:C(n1+n2,n1) or C(n1+n2,n2) they are the same.

Now to fix this problem we need to add more parameters to our state to help us decide whether we can add a one or a zero without breaking the rules for maximum consecutive ones or zeroes.

so lets introduce two more parameters to the state so that the state would be (n1,n2,b,l)
where b is the last bit used and l is the length of consecutive b bits at the end of our binary number.

now those additional two parameters should help us to decide whether we can add another bit of type b or we must switch.

this solution should run in O(n1 * n2 * max(k1,k2) * 2)

import java.util.Scanner;
public class DP1_CL {
	static int[] k = new int[2];
	static int[][][][] dp;
	static int mod = 100000000;
	public static int go(int n1, int n2, int b, int l) {
		if (dp[n1][n2][b][l] != -1)
			return dp[n1][n2][b][l];
		int res = 0;
		if (n1 == 0 && n2 == 0)
			res = 1;// we're done
		else if (b == 0) {
			if (n1 > 0 && l + 1 <= k[b])// add another 0
				res = (res + go(n1 - 1, n2, 0, l + 1)) % mod;
			if (n2 > 0)// add 1 and reset l
				res = (res + go(n1, n2 - 1, 1, 1)) % mod;
		} else if (b == 1) {
			if (n1 > 0)// add 0 and reset l
				res = (res + go(n1 - 1, n2, 0, 1)) % mod;
			if (n2 > 0 && l + 1 <= k[b])// add another 1
				res = (res + go(n1, n2 - 1, 1, l + 1)) % mod;
		}
		return dp[n1][n2][b][l] = res;
	}
}

Dynamic programming is a matter of practice, you should solve as much dp problems as you can to be able to see the state/transition and figure out the recurrences quickly.
Practice problems
Unidirectional TSP
Barcodes
Sqrt log sin
Wedding shopping
Super Sale
Sum of different primes
Chest of drawers

if you find any mistakes or have a feedback please leave a comment, thanks for reading 🙂

Posted September 14, 2012 by epicrado in Tutorials

Effective factorization using Sieve of Eratosthenes   2 comments


We’ll modify Sieve of Eratosthenes to have a prime factor for every number in our interval.
Sieve works by eliminating composites using their prime factors(uses prime numbers to eliminate all their multiples).
we used this property to have a prime factor for every number.

int[] primeFactor = new int[MAXN];// initialized with 0
primeFactor[0] = primeFactor[1] = -1;
for (int i = 2; i * i < MAXN; i++)
	if (primeFactor[i] == 0)
		for (int j = i * i; j < MAXN; j += i)
			primeFactor[j] = i;
for (int i = 2; i < MAXN; i++)
	if (primeFactor[i] == 0)
		primeFactor[i] = i;// sets every prime factor of a prime number	as the number itself

To factorize a number n we can use this array

int n = 48548;
Vector<Integer> pfactors = new Vector<Integer>();
while (primeFactor[n] != -1) {
	pfactors.add(primeFactor[n]);
	n /= primeFactor[n];
}
System.out.println(pfactors.toString());//output is [53, 2, 2, 229]

Posted February 6, 2012 by epicrado in Tutorials

Computing Functions involving prime numbers over a range of integers.   3 comments


In this tutorial we’ll get to know some functions involving prime numbers such as

  • Generating prime numbers over a range of integers:isPrime(n)
  • Numbers k< n  and Gcd(k,n)=1:Phi(n)
  • Number of prime factors of a number:nPrimeFactors(n)
  • Number of factors of a number:nFactors(n)

First We’ll introduce a way to generate prime numbers over a range of integers Sieve of Eratosthenes

boolean[] isPrime = new boolean[MAXN];//Weather a number n is prime or not
Arrays.fill(isPrime, true);//Assumes all numbers are primes in the beginning
isPrime[0]=isPrime[1]=false;//zero and one are not primes
for(int i = 2;i*i<MAXN;i++)
	if(isPrime[i])//if the current number is a prime
		for(int j = i*i;j<MAXN;j+=i)
			isPrime[j]=false;//then all it's multiples are not primes

Now we can modify sieve a bit to compute Euler’s totient function we used the formula at wikipedia
Phi(n) = n *[ (1-1/a) * (1-1/b) ….] where a,b,… are the distinct prime factors of n
Here’s the code

int[] phi = new int[MAXN];
phi[0] = 0;
phi[1] = 1;
for (int i = 2; i < MAXN; i++)
	phi[i] = i;
for (int i = 2; i < MAXN; i++)
	if (phi[i] == i)// then i is a prime number
		for (int j = i; j < MAXN; j += i)
			phi[j] = phi[j] / i * (i - 1);// divide by i then multiply by i-1

Notice here we didn’t stop the first for loop in sieve at sqrt(MAXN) instead we continued till MAXN as we want to use every prime number to modify phi for all it’s factors.

To compute the number of prime factors of a number we’ll use this formula
nPrimeFactors(n) = nPrimeFactors(a)+nPrimeFactors(b) if n = a*b
nPrimeFactors(n) = 1 if n is a prime number
this leads us to
nPrimeFactors(n) = 1 + nPrimeFactors(n/p) if n is a multiple of p and p is a prime and that’s how we’ll compute our answer quickly so we’ll need to know one prime factor of every composite we have

int primeFactor[] = new int[MAXN];//holds a single prime factor for each number,initialized with zero
for (int i = 2; i * i < MAXN; i++)
	// we didn't iterate over the whole interval cause we only need to
	// know a single prime factor for each composite
	if (primeFactor[i] == 0)
		for (int j = i * i; j < MAXN; j += i)
			primeFactor[j] = i;
for (int i = 2; i < MAXN; i++)
	if (primeFactor[i] == 0)
		primeFactor[i] = i;// sets every prime factor of a prime number as the prime it self
int[] nPrimeFactors = new int[MAXN];// we'll have the result here
nPrimeFactors[0] = nPrimeFactors[1] = 0;
for (int i = 2; i < MAXN; i++)
	nPrimeFactors[i] = 1 + nPrimeFactors[i / primeFactor[i]];// Like a DP 😉

To count the number of factors of an integer we’ll use a technique similar to the one described above
let n be a number and n = p1^a * p2^b * p3^c….where p1,p2,p3.. are prime numbers
then nFactors(n) = (a+1)*(b+1)*(c+1)…..
simply we choose a power for each prime factor of n.
Thus we can write the function nFactors(n) as
nFactors(n)=(a+1)*nFactors(k) if n = p^a * k where p is a prime factor of n

int primeFactor[] = new int[MAXN];
for (int i = 2; i * i < MAXN; i++)
	if (primeFactor[i] == 0)
		for (int j = i * i; j < MAXN; j += i)
			primeFactor[j] = i;
for (int i = 2; i < MAXN; i++)
	if (primeFactor[i] == 0)
		primeFactor[i] = i;
int[] nFactors = new int[MAXN];
nFactors[0] = 0;
nFactors[1] = 1;
for (int i = 2; i < MAXN; i++) {
	int a = 0;
	int k = i;
	while (k % primeFactor[i] == 0) {// computes k and a
		a++;
		k /= primeFactor[i];
	}
	nFactors[i] = (a + 1) * nFactors[k];// nFactors[k] is computed since k<i
}

Posted February 6, 2012 by epicrado in Tutorials