PROBLEM LINKDIFFICULTYMEDIUMHARD PREREQUISITESDynamic Programming, Matrix Exponentiation PROBLEMYou are given an array, say S, of size 1 x Z. Each value is between 1 and C. You can perform K operations of the following type.
Find the number of different recolorings of the paper, after performing at most K operations described above. Note that you have to find the number of recolorings possible, not the number of ways of achieving the recolorings. QUICK EXPLANATIONAnton Lunyov came up with changes to this problem to make it harder and provided the judge solution for it. He also produced notes regarding parts of his solution. This Editorial is largely based on those notes and an analysis of his solution (which is well commented as well). Let us look at a Dynamic Programming approach that would be too slow. We will be converting this in the Explanation section below, into a faster Matrix Exponentiation. Visualize any coloring of the cells as broken up into blocks of similar colored cells. No recoloring will ever take place to recolor a cell from its original color onto the same color. In other words, no wasteful operation will ever be performed. This helps us in defining the following Dynamic Programming state (on which we will see how we derive it from substates). DP'[n,k] = Number of ways of recoloring the first n cells, in not more than k operations, such that the last block of same colored cells was not recolored from their original colors. DP[n,k,c] = Number of ways of recoloring the first n cells, in not more than k operations, such that the last block of same colored cells, are recolored c. c may or may not be the original color that they had. If c is the original color that they had, then the recoloring certainly extends further to the left. Note: Do not confuse between DP'[n,k] and DP[n,k,S[n]]. DP'[n,k] considers recolorings in which the last block of color S[n] is smaller than or equal to the length of the block in the original coloring (we use the term original length in the discussion below). Where as DP[n,k,S[n]] considers recolorings in which the last block of color S[n] is strictly larger than the original length. Now, DP'[n,k] = DP'[n1,k] + Summation( DP[n1,k,x], x = 1 to C, except x = S[n] )
DP[n,k,c] = DP[n1,k,c], if c = S[n] = DP[n1,k,c] + DP'[n1,k1] + Summation( DP[n1,k1,x], x = 1 to C, except x = c ), if c != S[n]
Thus, the answer for a given case would be DP'[N,K] + Summation( DP[N,K,x], for all x = 1 to C ) This looks like it would lead to an O(N*C^{2}*K) algorithm. We can speed up the algorithm by a factor of C, by using D"[n,k] = Summation( DP[n,k,x], for all x = 1 to C ) This modifies the equations as DP'[n,k] = DP'[n1,k] + D"[n1,k]  DP[n1,k,S[n]] DP[n,k,c] = DP[n1,k,c], if c = S[n] = DP[n1,k,c] + DP'[n1,k1] + D"[n1,k1]  DP[n1,k1,c] Note the method 'slow' in the Tester's solution for a clear implementation of this approach. This approach would solve a large variety of cases. It is recommended that you implement this approach and visualize which colorings were counted under what path of the recursion to make it clear. EXPLANATIONIn the problem we note that
The Tester's solution implements a transition matrix that is derived from the DP formulation above and applies exponentiation over it for each of the block given in the input. This gives us a O(N*(N*K)^{3} log max(M_{i})) algorithm to solve the problem. The solution is heavily commented for building the Transition Matrix. It is recommended to go over it for reference on how you could go about doing the same. There is one tricky detail in conversion of the DP to the Transition Matrix. We cannot consider all values of C. We only consider those values that are present in the original paper (at most 7). And, we consider one special value, let us say c = 0, which is meant to be helpful in considering any other color. The matrix state would look like For some n (initially 0) [ D'[n,0], D'[n,1], ... D'[n,K], DP[n,0,0], DP[n,1,0], ... DP[n,K,0], DP[n,0,C[1]], DP[n,1,C[1]], ... DP[n,K,C[1]], ... ... DP[n,0,C[j]], DP[n,1,C[j]], ... DP[n,K,C[j]] ] Where there are j different colors given. SETTERS SOLUTIONNot Available. TESTERS SOLUTIONCan be found here.
This question is marked "community wiki".
asked 19 Nov '12, 06:56

This editorial was very tricky for me to write :(
Please advice me on how I can improve it. I shall do it ASAP to improve its quality and utility.