PROBLEM LINK:
Author: Praveen Dhinwa
Tester 1 Goutham Kobakini
Tester 2 Arjun Arul
Editorialist: Praveen Dhinwa
DIFFICULTY:
Easy - Medium
PREREQUISITES:
dynamic programming and maintaining prefix sum and minimum etc.
PROBLEM:
There are n trees having colors either red, green or blue. You want to re-color the tree’s in such a way that all the trees of same color are continuous. Changing color of i^{th} tree to some other color takes a cost of c[i].
QUICK EXPLANATION
-
You can notice that all the trees of same color are continuous leads us to very few possibilities of arrangements of colors.
-
Fix a color possibility/ system, eg. ‘RGB’. It means that first we will color some trees (may be none) red, then green and then blue.
-
Let us say that we create an array red[i] denoting minimum cost of coloring first i trees red. This array can be computed easily by a single traversal of the array c.
-
Now we need to create another array redGreen[i] denoting the minimum cost of coloring first i trees such that they are colored first red (may be none), then green. Computing this array is the most crucial part of the problem. This part can be done by dynamic programming which is thoroughly explained in the next section.
-
Similarly we can create redGreenBlue[i] array too.
-
Our answer for this color system will be redGreenBlue[n].
EXPLANATION
Very few possibilities of coloring in the final arrangement
The condition that all the trees of same color should be continuous leads us to very few possibilities.
- All the trees have same color. eg. All R’s, All G’s, All B’s.
- Only two possible colors eg. All ‘R’ trees followed by ‘G’, Similarly ‘RG’, ‘RB’, ‘GR’, ‘GB’, ‘BR’, ‘BG’.
- All three possible colores. In this case, all 3! = 6 permutations of red, green, blue will have to be considered.
Note that for the discussion in the next section, we will assume that we will have 3! = 6 possible cases of coloring. For that we will merge the first two cases into third case itself by adding an extra condition that number of trees of a particular color can be zero too.
Fix a final possibility of colors
So we will iterate over all possible colors in the final arrangement (out of 3! = 6 choices). Let us fix a particular choice of color and solve our problem for that case. For all other cases, we can solve the problem similarly. Finally our answer will be minimum over all those cases.
So let us say that our fixed color possibility is ‘RGB’.
Compute array red
Let red[i] denote minimum cost of coloring first i trees red. This array can be computed easily by a single traversal of the array c.
Compute array redGreen
Let redGreen[i] denote minimum cost of coloring first i trees such that first few of them (possibly zero or all) are red and then remaining ones are green. This part is the main crucial part of problem.
redGreen[i] = \min_{\ j = 0}^{\ i} \ (red[j] \ + \ green[j + 1, i])
redGreen[i] =\min_{\ j = 0}^{\ i} \ (red[j] \ + \ green[i] \ - \ green[j])
redGreen[i] = \min_{\ j = 0}^{\ i} \ (red[j] \ - \ green[j] \ + \ green[i] )
Let’s create an array diff[i] denoting red[i] - green[i]. Then you can simplify the above expression as
redGreen[i] = \min_{\ j = 0}^{\ i} \ (diff[j] \ + \ green[i] )
As green[i] does not vary when j varies, we can take it out of the expression.
So we have redGreen[i] = green[i] \ + \ \min_{j = 0}^{i} (diff[j])
Now we can create another array mindiff where mindiff[i] = \min_{\ j = 0}^{\ i} (diff[j]). Computing this array can be done in a simple \mathcal{O}(n) loop.
So now, we have redGreen[i] = green[i] \ + \ mindiff[i]
Computing array redGreenBlue
This part is exactly similar to previous part. I am writing the expression from which you can proceed in exactly the same way as previous one.
redGreenBlue[i] = \min_{\ j = 0}^{\ i} \ (redGreen[j] \ + \ blue[j + 1, i])
Answer for the fixed color system
It will be redGreenBlue[n] which will denote minimum cost of coloring n trees with the RGB color system.+
Time complexity
So we can see that we are fixing 6 possible color systems, for each color system, we are solving the problem in \mathcal{O}(n). So overall time taken is also \mathcal{O}(n). Please see authors solution for a clean implementation of this approach.