 # IOIPRAC INOI : What's the expected approach for Calvin's Game ?

#1

Whats the expected approach for Calvin’s Game INOI 13

My approach of choosing max(forwardphase_at_i + Reverse_At_i) apparently fails…

#2

### DP Solution: Compute the following quantities#

\$Forward*\$ = \$Max\$ \$score\$ \$if\$ \$we\$ \$move\$ \$forward\$ \$from\$ \$K\$ to \$i\$, \$for\$ \$all\$ \$K <= i <= N\$

Backward* = Max score if we move backward from i to 1, for all K <= i <= N

Ans = Max (Forward* + Backward*) for all K <= i <= N

Make sure to include the case in which you don’t move forward at all.

``````
(http://paste.ofcode.org/t3F82vBwPyPtkVybbpJWjD)``````

#3

I have a doubt. May be the doubt is silly

if the input is
5 2

5 3 -2 1 1 (sample input) then we can continuously increase our score by from 3 to 1 and then 1 to 3 repeatedly (here 3 refers to the number 3 and not the third position)… I probably didnt read the question properly but pls clarify this doubt.

#4

We can only one forward phase(not move) followed by one backward phase. If you go from 3 to 1 and come back to three you have completed the forward phase and cannot go forward any more.

#5

That’s very generous ,Thank You Very much, Now I know what I missed  #6

There’s also a simple enough graph side of things.

#7

thanks!!!