Whats the expected approach for Calvin’s Game INOI 13
My approach of choosing max(forwardphase_at_i + Reverse_At_i) apparently fails…
Whats the expected approach for Calvin’s Game INOI 13
My approach of choosing max(forwardphase_at_i + Reverse_At_i) apparently fails…
Forward[i] = Max score if we move forward from K to i, for all K <= i <= N
Backward[i] = Max score if we move backward from i to 1, for all K <= i <= N
Ans = Max (Forward[i] + Backward[i]) 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)
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.
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.
That’s very generous ,Thank You Very much, Now I know what I missed
There’s also a simple enough graph side of things.
thanks!!!
I used the same approach. But cannot figure out the corner case where my soln fails
A test case would be really helpful.
Solution
you need to calculate the maximum from the (k-1)th index to n , not from the starting index.