LEPAINT - Editorial

[devuy11]

PROBLEM LINK:

Practice
Contest

Author: Vitaliy Herasymiv
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

DIFFICULTY:

Medium

PREREQUISITES:

Dynamic Programming.

PROBLEM:

You are given N objects from 1 to N.Initially they are colored with color 1.You are supplied with C colors from 0,…C-1 .When object with color a is painted in color b, the resulting color will have color (a*b) mod C. Little Elephant is going to make K turns.
At i-th turn he will randomly choose any subset (even empty) of objects with indices in range [L_i; R_i] (inclusive) and paint all objects in chosen subset with random color (the same for all objects in the subset).
Little Elephant wants to know the expected sum of all colors over all n objects after making all K turns.

Explanation

This problem can be solved using a simple dynamic programming approach.
The main idea is to find the probability of occurence of each color at each index for every turn.
Note : Sum of probability of occurence of colors at any index i is 1.

So let us think about the base case for this dp :

Initially the color at each index is 1 , so the probability of occurence of color 1 is 1 at each index.

Pseudo Code For Base Case

dp[i][j][k] denotes the probability of occurence of color k at jth index in ith turn.
Init dp[i][j][k] to 0 for all i , j, k.
for(int i=1;i<=N;i++)
	dp[0][i][1]=1;

Let dp[i][j][k] denotes the probability of occurence of color k at j^th index in i^th turn.

Let us think on how to compute dp[i][j][k] :

In the i^th turn , we need to change the color of any subset from [ L_i ; R_i ] , so the probability of occurence of each color in the range [1 ; L_i-1 ] and [ R_i+1 ; N ] will be same as the (i-1)^th turn.

Let us now focus on the interval [ L_i ; R_i ] for i^th turn. Probability of presence of a index in all random subsets from [ L_i ; R_i ] is 0.5 ( Reason : Either you will take that element or you won’t take that element for the subset).So , dp[i][j][k] += dp[i-1][j][k] * (0.5) , if the j^th index is not selected in the subset.

Let us now focus on the case when index j is considered in the subset. Probability that it is considered in the subset is 0.5 .
Probability that this index is now colored with m^th color is 1/C , because there is equal probability of each color to be choosen. So probability that the index is choosen and is colored with m^th color is 1/(2C).

The resulting color will be m*k , where k is the existing color of that index. So , probability that the index is colored with k^th color and is colored with m^th color will add to the probability of getting (m * k)%C color.
So dp[i][j][(m * k)%C] += dp[i-1][j][k]/(2C) is justified.

Finally after all the turn’s , we can compute the expected value from dp[K][i][j] , dp[K][i][j] denotes the probability of color j at i^th index at the end . so we can summate over j * dp[K][i][j] over all i and j and get the expected value.

Psedo Code

for(int i=1;i<=K;i++)
	Take_Input( L and R )
	for(int j=1;j<=N;j++)	//for all indices
		for(int k=0;k<C;k++)
			if( j>=L && j<=R)
				// if you choose the subset and you choose mth colors
				for(int m = 0;m<C;m++)
					dp[i][j][(m*k)%C] += dp[i-1][j][k]/(2*C);
				//if you don't chose it [ probability that you do not take it in subset is 0.5 ]
				dp[i][j][k] += dp[i-1][j][k]*0.5
			else
				//This is unaffected in this turn
				dp[i][j][k] += dp[i-1][j][k]

Finding_Answer:
	for(int i=1;i<=N;i++)
		for(int j=0;j<C;j++)
			answer = answer + j*dp[K][i][j];
	return answer

Complexity:

O(K * N * C * C).

AUTHOR’S and TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

[sousnake]

@author : Please note that the complexity for t test cases will be O(tkncc) which is 2.5*10^8 (extreme cases) which creates a doubt in the mind of solver. I did get accepted in the end but for a long time i was concern about the issue of time limit.

[gkcs]

http://www.codechef.com/viewsolution/4272997

I didn’t use dynamic programming at all. The distribution of numbers from each number is predictable.

@priyanshuid : Hope this helps.

Imagine the possibilities to be a tree. This tree will have c^k nodes. Ignore color 0 for the moment. Hence possibilities now are (c-1)^k, as we have ignored 0. Now when c is prime, you will notice all colors are possible in the next level of the tree for all nodes. The sum of colors from 1 to (c-1)=(c)(c-1)/2. This happens for every c-1 colors. Hence total colors possible= (c(c-1)/2)((c-1)^k))/(c-1)=c(c-1)^k. When color=0, rest of tree will have all zero colors. So it has no effect on numerator.

When c is not prime, well i tried to figure out a mathematical formula for long, but in the end took an array as current colors. I figured out which colors pop out from which color in the nums[][] array. Then for every kth iteration, i multiplied the current colors by their factors. Simply put, its like traversing the tree and keeping counts of colors.

Finally, all the fancy combinatorics is because chef can chose any subset of the segment.

a[i]=number of appearances for i.

So 2^a[i] is multiplied to denominator and comb(a[i],j) is multiplied to the numerator.

[gauravdewan007]

Complexity: O(KCC + N) for each test case (since matrix multiplication (power of matrix) can be reused for all the n objects.)

[achaitanyasai]

Very nicely explained,I have struggled nearly more than a week for the idea!, really DP is great!

[phantom002]

Very Nicely explained…with the solution broken down to various aspects of the problem…really very helpful to me…(y)…One of the best editorials I have ever read…:D…thanks!!

[filmwalams]

I am still weak in Dynamic programming.

[a7i7]

I had tried a different approach which timed out due to lots of calculations. Here is the approach.
Its based on the formation of Markov Chain.

Markov chain

Build a c x c matrix M(c is the number of colors) where M[i][j] represents the probability of going from color i to color j in a single paint. If a block is painted T times, then raise the matrix to the power T (M^T). Row number 1 will contain the corresponding probabilities from which expectation of that block can be calculated.
I think the main idea is explained. The rest is fairly simple. Maintain an integer array A[n] with all elements initialized to 0. After reading all the values of Li Ri update A[i] such that A[i] tells the number of times block i is to be colored. Raise M to the power A[i] for all blocks and calculate corresponding expectations. If anyone is interested here is the code.

http://www.codechef.com/viewsolution/4257930

[tec]

O(n^2+t*(kn+c+ku^2)) where u is the number of divisors of c.

http://www.codechef.com/viewsolution/4298097

Precompute: binomial coefficient of NxN. (O(n^2))

For each test case:

1. count the number of paints each object is involved in. (O(k*n))

2. partition [0,c) into groups by gcd(i,c), recording group size and average value. (O(c))

3. build u x u transition matrix, computing the probability of transit between each 2 groups after 0…k paintings (O(k*u^2))

4. compute the expect color after k paints. (O(u))

5. summarize on each object and possible paint combinations on that object. (O(k*n))

[rtheman]

I didn’t use DP,
http://www.codechef.com/viewsolution/4281657
a commented and properly indented soln. is present here

Ideone.com

[baljitsingh]

@devuy11 we are increasing the probability of dp[i][j][(m*k)%C] if index is choosen in the subset. would’nt it lead to decrease in the probability of rest of colors because the summation of probability of all colors at each index in each step is 1?

[obscure79]

Great tutorial on DP and probability theory!! Thanks…

[abcdexter24]

Good question, and great explanation

[gkcs]

Dynamic programming is a powerful tool, but I tend to avoid it as long as the solution remains intuitive. Complexity here is the same: O(KNCC).

[mithunmk93]

One of the best editorials i have read till date on DP. Thank you

[priyanshuid]

hey, could you give a little detail of your idea… could not figure it out from your code, since i code in cpp. Thanks!

[gkcs]

Btw, If someone can figure out how to calculate total colors when n is not prime, complexity will fall to O(KN). That would be great.

[grayhathacker]

nice editorial!!! simple and clear

[unrealsoul007]

Solved it using the same approach. But I would say, this is a great explanation of LEPAINT solution. Truly, one of the best DP-based editorial that I have read. Keep it up…!! (y) …

[tec]

Do you mean for prime and non-prime c? For non-prime c, no simple formula, but the logic is similar. Assume a series of updates c0=1,c1,…,ck, let di = gcd(ci,c), di is a divisor of c, and non-decreasing. for color ci and update x, if x and c/di is coprime, then di is unchanged; otherwise, di is multiplied by (x,c/di). in both cases, all numbers with same di has equal probability. prime c is just a special case, where di in {1,c}. whenever di changes from 1 to c, color changes to 0 and stop controbution to the sum. See my solution below.