Editorialist : Sudheera Y S
Problem Link : ZIO 2015 Problem 3
Prerequisites : dynamic programming
Problem statement :
There are some positions and each of them has some color associated with it and a number also. We need to choose some position such that after changing their values as per given rules , the sum of the numbers in the position should be maximum. We should find this sum.
Rules for changing the values after choosing the beeds :
- If a position is not chosen , then its value is set to 0
- The value of the leftmost selected position is multiplied by 3
- For any other position , if the nearest position selected in the left has the same color then the number in the current position is unchanged , but if it is of different color , then the number in the current position is multiplied by 3
Idea :
Greedy approach works , but we may not consider some case or something like that , so greedy method is not 100% right , so to get a better , faster , more accurate solution , we will do dynamic programming approach
Let the numbers in the position stored in array βaβ
As we always do in dynamic programming , first let us define our dp
Dp[ i ] = maximum sum we can achieve by choosing the ith position and if we only consider position till i
Base case :
Dp[ 1 ] = ( only considering the first position , and we are selecting it , as it is the leftmost position , we will multiply it by 3 ) a[ 1 ]*3
Recursion :
Dp[ i ] = max( if this position is the first position to be selected , if this is not the first position to be selected )
= max ( a[ i ]*3 , for j : 1 β i-1 if we select j and then ith position )
Answer can be stored anywhere in dp , therefore the answer will be max(dp)
Let us do the subtasks so it becomes more clear :
Subtask A :
Position | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
Number | 5 | 8 | 20 | -2 | 10 | -8 | -2 | 13 | -8 |
Color | R | R | R | G | R | B | B | B | R |
So now , let us start filling our dp table :
Dp[ 0 ] = a[ 0 ]3 = 53 = 15
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 |
Now coming to the second position :
Either we can choose the position alone , or take it with the first position
If we taking it alone β 8*3 = 24
If we take it after choosing the first position β dp[ 1 ] + a[ 2 ] = 15 + 8 = 23
Therefore taking it alone would be better , therefore dp[ 2 ] = 24
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 |
Third position :
Case 1 : choose it alone β 20*3 = 60
Case 2 : choose it with first position β dp[ 1 ] + a[ 3 ] = 15 + 20 = 35
Case 3 : choose it with second position β dp[ 2 ] +a[ 3 ] = 44
Therefore the best would be again to choose it alone , therefore dp[ 3 ] = 60
NOTE : Here we are doing +a[ i ] only because the color is the same , so the value is left unchanged
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 |
Fourth position :
Case 1 : choose it alone β a[ 4 ]*3 = -2 * 3 = -6
Case 1 : choose with first position β dp[ 1 ] + 3*a[ 4 ] = 15 + -6 = 9
Case 2 : choose with second position β dp[ 2 ] + 3*a[ 4 ] = 24 + -6 = 18
Case 3 : choose with third position β dp[ 3 ] + 3*a[ 4 ] = 60 + -6 = 54
Maximum of all of these is 54 , therefore dp[ 4 ] = 54
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 |
Fifth position :
Case 1 : choose it alone β a[ 5 ]3 = 103 = 30
Case 2 : choose it first position β dp[ 1 ] + a[ 5 ] = 15 + 10 = 25
Case 3 : choose it second position β dp[ 2 ] + a[ 5 ] = 24 + 10 = 34
Case 4 : choose it third position β dp[ 3 ] + a[ 5 ] = 60 + 10 = 70
Case 5 : choose it fourth position β dp[ 4 ] + a[ 5 ]*3 = 54 + 30 = 84
Maximum of all of these is 84 , therefore dp[ 5 ] = 84
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 | 84 |
Sixth position :
Case 1 : choose it alone β a[ 6 ]3 = -83 = -24
Case 2 : choose it first position β dp[ 1 ] + a[ 6 ]*3 = 15 + -24 = -9
Case 3 : choose it second position β dp[ 2 ] + a[ 6 ]*3 = 24 + -24 = 0
Case 4 : choose it third position β dp[ 3 ] + a[ 6 ]*3 = 60 + -24 = 36
Case 5 : choose it fourth position β dp[ 4 ] + a[ 6 ]*3 = 54 + -24 = 30
Case 6 : choose it fifth position β dp[ 5 ] + a[ 6 ]*3 = 84 + -24 = 60
Maximum of all of these is 60 , therefore dp[ 6 ] = 60
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 | 84 | 60 |
Seventh position :
Case 1 : choose it alone β a[ 7 ]3 = -23 = -6
Case 2 : choose it first position β dp[ 1 ] + a[ 7 ]*3 = 15 + -6 = 9
Case 3 : choose it second position β dp[ 2 ] + a[ 7 ]*3 = 24 + -6 = 18
Case 4 : choose it third position β dp[ 3 ] + a[ 7 ]*3 = 60 + -6 = 54
Case 5 : choose it fourth position β dp[ 4 ] + a[ 7 ]*3 = 54 + -6 = 48
Case 6 : choose it fifth position β dp[ 5 ] + a[ 7 ]*3 = 84 + -6 = 78
Case 7 : choose it sixth position β dp[ 6 ] + a[ 7 ] = 60 + -2 = 58
Maximum of all of these is 78 , therefore dp[ 7 ] = 78
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 | 84 | 60 | 78 |
Eight position :
Case 1 : choose it alone β a[ 8 ]3 = 133 = 39
Case 2 : choose it first position β dp[ 1 ] + a[ 8 ]*3 = 15 + 39 = 54
Case 3 : choose it second position β dp[ 2 ] + a[ 8 ]*3 = 24 + 39 = 63
Case 4 : choose it third position β dp[ 3 ] + a[ 8 ]*3 = 60 + 39 = 99
Case 5 : choose it fourth position β dp[ 4 ] + a[ 8 ]*3 = 54 + 39 = 93
Case 6 : choose it fifth position β dp[ 5 ] + a[ 8 ]*3 = 84 + 39 = 123
Case 7 : choose it sixth position β dp[ 6 ] + a[ 8 ] = 60 + 13 = 73
Case 8 : choose it seventh position β dp[ 7 ] + a[ 8 ] = 78 + 13 = 91
Maximum of all of these is 123 , therefore dp[ 8 ] = 123
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 | 84 | 60 | 78 | 123 |
Ninth position :
Case 1 : choose it alone β a[ 9 ]3 = -83 = -24
Case 2 : choose it first position β dp[ 1 ] + a[ 9 ] = 15 + -8 = 7
Case 3 : choose it second position β dp[ 2 ] + a[ 9 ] = 24 + -8 = 16
Case 4 : choose it third position β dp[ 3 ] + a[ 9 ] = 60 + -8 = 52
Case 5 : choose it fourth position β dp[ 4 ] + a[ 9 ]*3 = 54 + -24 = 30
Case 6 : choose it fifth position β dp[ 5 ] + a[ 9 ] = 84 + -8 = 76
Case 7 : choose it sixth position β dp[ 6 ] + a[ 9 ]*3 = 60 + -24 = 36
Case 8 : choose it seventh position β dp[ 7 ] + a[ 9 ]*3 = 78 + -24 = 54
Case 9 : choose it eight position β dp[ 8 ] + a[ 8 ]*3 = 123 + -24 = 99
Maximum of all of these is 99 , therefore dp[ 9 ] = 99
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|
15 | 24 | 60 | 54 | 84 | 60 | 78 | 123 | 99 |
Now , we are done with the dp table , so we can compute our answer now.
As said earlier , our answer would be the maximum in the dp table , therefore the answer is 123
Answer : 123
Subtask B :
Here we see that for any particular position , instead of going to all positions before it , we know that
If the color is blue , Then the maximum score can be only from the maximum of ( maximum of red before i and maximum of green before it ) + a[i]*3 or if it is the same color , then maximum of all blue before it + a[i]
If the color is red , Then the maximum score can be only from the maximum of ( maximum of blue before i and maximum of green before it ) + a[i]*3 or if it is the same color , then maximum of all red before it + a[i]
If the color is green , Then the maximum score can be only from the maximum of ( maximum of red before i and maximum of blue before it ) + a[i]*3 or if it is the same color , then maximum of all green before it + a[i]
All we have to do is maintain three variables BlueMax , RedMax , GreenMax all of them equal to 0 first. As we keep on proceeding , we will update the maximum of the color with the position of the color we are processing now.
Let us do so that we will get better clarity
Here is the given input :
Pos | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Num | 8 | 9 | -5 | 2 | 4 | -6 | 2 | 1 | -3 | -3 | 7 | 9 | 1 |
Colou | R | R | R | R | B | B | B | B | G | G | B | B | B |
BlueMax = 0 , RedMax = 0 , GreenMax = 0
Base case : dp[ 1 ] = a[ 1 ]*3 = 24
The first position is red color , so as we have found dp[i] , we can update our RedMax from 0 to 24
BlueMax = 0 , RedMax = 24 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 |
Second position : color : Red
Different color β max(blue , green ) + a[i]*3 = 27
Same color β Redmax + a[i] = 24 + 9 = 33
Maximum of both of these is 33 , therefore dp[ 2 ] = 33
We have found the value of dp[ 2] and as the second position is red , we update our RedMax
BlueMax = 0 , RedMax = 33 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 |
Third position : color : Red
Different color β max(blue , green ) + a[i]*3 = -15
Same color β Redmax + a[i] = 33 + -5 = 28
Maximum of both of these is 28 , therefore dp[ 3 ] = 28
We have found the value of dp[ 3] and as the third position is red , we update our RedMax , but the initial value of RedMax is greater than the current value , therefore we donβt update RedMax
BlueMax = 0 , RedMax = 33 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 |
Fourth position : color : Red
Different color β max(blue , green ) + a[i]*3 = 6
Same color β Redmax + a[i] = 33 + 2 35
Maximum of both of these is 35 , therefore dp[ 4 ] = 35
We have found the value of dp[ 4] and as the fourth position is red , we update our RedMax
The current value of RedMax is 33 but we have found a position of red color and larger number , therefore we update RedMax from 33 to 35
BlueMax = 0 , RedMax = 35 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 |
Fifth position : color : Blue
Different color β max(red , green ) + a[i]*3 = 35 + 12 = 47
Same color β BlueMax + a[i] = 0 + 12 = 12
Maximum of both of these is 47 , therefore dp[ 5 ] = 47
We have found the value of dp[ 5] and as the fifth position is blue , we update our BlueMax
BlueMax = 47 , RedMax = 35 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 | 47 |
Sixth position : color : Blue
Different color β max(RedMax , GreenMax ) + a[i]*3 = 35 + -18 = 17
Same color β BlueMax + a[i] = 47 + -6 = 41
Maximum of both of these is 41 , therefore dp[ 6 ] = 41
We have found the value of dp[ 6] and as the sixth position is blue , we update our BlueMax
But BlueMax is already larger than the value , so we need not update it
BlueMax = 47 , RedMax = 33 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 | 47 | 41 |
Seventh position : color : Blue
Different color β max(RedMax , GreenMax ) + a[i]*3 = 35 + 6 = 41
Same color β BlueMax + a[i] = 47 + 2 = 49
Maximum of both of these is 49 , therefore dp[ 7 ] = 49
We have found the value of dp[ 7 ] and as the seventh position is blue , we update our BlueMax
As the current value of dp is greater than the BlueMax , we need to update BlueMax from 47 to 49
BlueMax = 49 , RedMax = 33 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 | 47 | 41 | 49 |
Eight position : color : Blue
Different color β max(RedMax , GreenMax ) + a[i]*3 = 35 + 3 = 38
Same color β BlueMax + a[i] = 49 + 1 = 50
Maximum of both of these is 50 , therefore dp[ 8 ] = 50
We have found the value of dp[ 8 ] and as the eight position is blue , we update our BlueMax
As the current value of dp[8] is greater than the BlueMax , we need to update BlueMax from 49 to 50
BlueMax = 50 , RedMax = 33 , GreenMax = 0
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 | 47 | 41 | 49 | 50 |
Ninth position : color : Green
Different color β max(RedMax , BlueMax ) + a[i]*3 = 50 + -9 = 41
Same color β GreenMax + a[i] = 0 + -3 = -3
Maximum of both of these is 41 , therefore dp[ 9 ] = 41
We have found the value of dp[ 9 ] and as the ninth position is green , we update our GreenMax
As the current value of dp[9] is greater than the GreenMax , we need to update BlueMax from 0 to 41
BlueMax = 50 , RedMax = 33 , GreenMax = 41
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
24 | 33 | 28 | 35 | 47 | 41 | 49 | 50 | 41 |
Soooo onβ¦β¦. And we will get the maximum as 72
Answer : 72
Subtask C : Bonus
Hope you understood