PROBLEM LINK
DIFFICULTY
MEDIUM-HARD
PREREQUISITES
Dynamic Programming, Matrix Exponentiation
PROBLEM
You 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.
- Pick a range L, R.
- Paint all the cells between L and R, inclusive, with some color between 1 and C.
- You can only re-color a cell once.
Find the number of different re-colorings of the paper, after performing at most K operations described above. Note that you have to find the number of re-colorings possible, not the number of ways of achieving the re-colorings.
QUICK EXPLANATION
Anton 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 re-coloring 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 sub-states).
DP’[n,k] = Number of ways of re-coloring the first n cells, in not more than k operations, such that the last block of same colored cells was not re-colored from their original colors.
DP[n,k,c] = Number of ways of re-coloring the first n cells, in not more than k operations, such that the last block of same colored cells, are re-colored 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'[n-1,k] + Summation( DP[n-1,k,x], x = 1 to C, except x = S[n] )
- DP’[n-1,k] considers all colorings in which the (n-1)th cell is the same color as the original, and the block containing it has not been recolored.
- Summation( DP[n-1,k,x], x = 1 to C, except x = S[n] ) considers all the possible colorings in which the block ending at (n-1)th cell has any color beside S[n].
- The case of S[n] must be ignored because
- It will be counted in DP’[n-1,k] if S[n-1] = S[n]. This will ensure that the length of that block doesn’t exceed the original length.
- All cases in which the last block of color S[n] is larger than the original length, will be counted in DP[n,k,S[n]] separately, and must not be counted here.
- The case of S[n] must be ignored because
DP[n,k,c] = DP[n-1,k,c], if c = S[n]
= DP[n-1,k,c] + DP'[n-1,k-1]
+ Summation( DP[n-1,k-1,x], x = 1 to C, except x = c ), if c != S[n]
- DP[n-1,k,c] considers the case where (n-1)th cell is also being recolored to c.
- The operation will simply extend to the nth cell.
- Note that when c = S[n], this recursion ensures that cases in which the length of the last block is longer than the original length are the only ones being considered.
- Now, we consider cases where we are consuming one operation to recolor the last cell to c.
- DP’[n-1,k-1] considers all the cases where the (n-1)th cell is not recolored (and the block ending at n-1 is not larger than the original length).
- Summation( DP[n-1,k-1,x], x = 1 to C, except x = c ) considers all the cases in which the block ending at (n-1) is re-colored.
- We ignore when the color is c, since this is being taken care of within DP[n-1,k,c].
- The case when x = S[n-1] counts colorings where the block ending at (n-1)th is longer than the original length.
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*C2*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'[n-1,k] + D"[n-1,k] - DP[n-1,k,S[n]]
DP[n,k,c] = DP[n-1,k,c], if c = S[n]
= DP[n-1,k,c] + DP'[n-1,k-1] + D"[n-1,k-1] - DP[n-1,k-1,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.
EXPLANATION
In the problem we note that
- Z can be very large
- C can be very large
- K is very small (up to 7)
- There are very few unique colors in the paper originally.
- This becomes very useful in considering all the other colors together.
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(Mi)) 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 SOLUTION
Not Available.
TESTERS SOLUTION
Can be found here.
