ZIO15003 - Editorial

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 :slight_smile:

Hope you understood

:slight_smile:

8 Likes

Oh my ! You wrote such a long post, you deserve a like from me

3 Likes

very clearly explained :grinning: