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 [Li; Ri] (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.
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*[j][k] denotes the probability of occurence of color k at jth index in ith turn. Init dp*[j][k] to 0 for all i , j, k. for(int i=1;i<=N;i++) dp*=1;
Let dp*[j][k] denotes the probability of occurence of color k at jth index in ith turn.
Let us think on how to compute dp*[j][k] :
In the ith turn , we need to change the color of any subset from [ Li ; Ri ] , so the probability of occurence of each color in the range [1 ; Li-1 ] and [ Ri+1 ; N ] will be same as the (i-1)th turn.
Let us now focus on the interval [ Li ; Ri ] for ith turn. Probability of presence of a index in all random subsets from [ Li ; Ri ] is 0.5 ( Reason : Either you will take that element or you won’t take that element for the subset).So , dp*[j][k] += dp[i-1][j][k] * (0.5) , if the jth 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 mth 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 mth color is 1/(2C).
The resulting color will be mk , where k is the existing color of that index. So , probability that the index is colored with kth color and is colored with mth color will add to the probability of getting (m * k)%C color.
So dp[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][j] , dp[K][j] denotes the probability of color j at ith index at the end . so we can summate over j * dp[K]*[j] over all i and j and get the expected value.
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*[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*[j][k] += dp[i-1][j][k]*0.5 else //This is unaffected in this turn dp*[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]*[j]; return answer
O(K * N * C * C).