Calvins Game | INOI1301 | Editorial
Read the problem statement here.
Analyzing the problem statement you might be wondering that — If on the right side of the square ‘k’, we have some consecutive positive integers, say at the (k+1)’th index and (k+2)’th index, then Calvin can move one step forward and backward for infinite time and eventually his score will also become infinite !
No, it won’t. Because once Calvin has started moving from right to the left(towards the square 1), he cannot turn back and move again from left to right.
Now let’s jot down the key points mentioned in the problem statement:
1. Calvin can move in two directions only— left to right or right to left.
2. In either of the type of moves, he can jump to the next square or to the next to next square. Which means he can make a jump of one or two steps in the direction he is moving.
3. The game ends only when Calvin steps on the first square.
4. Calvin’s score increases/decreases by the same number written on top of the square he jumps upon. Keep in mind that the square he is standing upon initially has no contribution to his score.
5. The goal is to maximize Calvin’s score.
Let’s build the intuition keeping the above points in mind:
1. Calvin can jump forward (towards the right) only on the squares which are on the right side of the square Calvin is currently standing. Its simply because once Calvin makes a backward jump, he cannot make a forward jump again.
2. While making a forward jump, Calvin will always try to jump on a square having a positive value to optimize his score. If consecutive squares to the right have positive values, he will make jumps of step 1 on each of them.
What happens if both the squares to the right are having negative values ? Calvin may wish to jump only if some square after the negative valued squares is having a positive value such that even if he jumps on the negative valued square and decreases his score, he will then get the chance to jump on the positive valued square and increase his score again. Thus, Calvin will forward-jump on a negative valued square only if some positive valued square exists to it’s right, stepping on which gives Calvin a net gain in score.
3. We can thus calculate the possible score of Calvin at every index greater than ‘k’ (the initial square from which Calvin begins), when Calvin makes only forward jumps.
How do we do that ? If Calvin is current standing at the ‘i’th square, he can move to the ‘i+1’th square, either from the ‘i’th square or from the ‘i-1’th square. As Calvin will always try to maximize his score, he will move to the ‘i+1’th square from that square which is having the maximum accumulated score between the ‘i’th square and the ‘i-1’th square.
4. Now, we will have to calculate the possible score of Calvin for every index from the last to the first, considering the fact that Calvin is only moving in the backward phase.
Why do we need to calculate the score for each index from the last to the first in case of backward jumps ? Because, making forward jumps Calvin can reach till the last (rightmost) square, and we know that to finish the game Calvin must return back to square 1.
5. We calculate the score for the backward jumps from the first to the last square. Calvin will have to step on the first square as his last jump, hence the first square’s value will definitely be added to his score.
Similarly, while making jumps in the backward phase, if Calvin has arrives on the second square then his score will be the value on the second square along with the value on the first square, as because immediately after he will make a jump to the first square and complete the game.
For square number 3 onwards, Calvin can take a decision as whether to jump on the second square or the first square or both, depending on which will give him the optimal score. Thus we will consider the current square value and the maximum of the accumulated scores between the previous square and the previous to previous square. In this way we compute all the backward jump scores.
Here’s an example demonstrating the above steps:
6. To get the final maximum score, i.e. the combined score of all the forward and the backward jumps, let’s analyze the two auxiliary arrays which we have constructed so far. For any index ‘i’ the sum of the forward[i] and backward[i] values will give us the maximum score of all forward and backward jumps upto index ‘i’.
Wait ! We know that the last square which Calvin reaches making forward jumps contributes to his score only once. Because after that we start making backward jumps to the squares on its left. Hence, we need to substract one occurrence of the value of that square which we are considering that Calvin might last step upon, so as to get the maximum score.
7. We need to keep track of Calvin’s maximum score, as we go on checking the possible score for each index ‘i’ in step 6.
Woohoo ! That’s all.
Click here for the solution.
Cheers !
