INOI1301-Editorial

infinitepro · January 5, 2020, 9:29am

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given an array A of N integers. You start at index K with a score of 0.
There is a forward phase followed by a backward phase.

Forward - If you are at index p, you can move to index p+1 or p+2.
Backward - If you are at index p, you can move to index p-1 or p-2.

On moving to a particular index p, you add A_p to your score.
Find the maximum score you can obtain, if you stop on reaching index 1.

QUICK EXPLANATION:

Consider the forward phase.
We determine the maximum possible score over all valid forward sequences from K\rarr i, for all valid i, using DP. Call the maximum score achievable from K\rarr i as \text{FW}_i.

Any valid backward sequence from i\rarr 1 is also a valid forward sequence from 1\rarr i.
Thus, we determine the maximum possible score over all valid forward sequences from 1\rarr i, for all valid i with DP. Call the maximum score achievable from 1\rarr i as \text{BW}_i

Therefore, the maximum possible score over all sequences from K\rarr i\rarr 1 is

\text{FW}_i+\text{BW}_i-A_i

where A_i has been subtracted since A_i is counted twice, once each in \text{FW}_i and \text{BW}_i
Using this, we determine the maximum score from K\rarr i\rarr 1, over all i.

EXPLANATION:

Let us start by only considering the forward phase, that is, we try to determine the maximum possible score when we start from square K and when only forward jumps are allowed.

Now, this is a well known DP problem, which is a modified version of the classical ‘staircase problem’. However, for those that are not familiar with the solution, I shall (briefly) explain the solution here.

Note : Those that are completely new to DP are requested to read a tutorial on DP, the link to which is given in the prerequisites.

Let \text{Forward}(i) represent the maximum score achievable over all forward phases (starting at K) that end at square i. In other words, \text{Forward}(i) represents the maximum possible score that we can attain, if we start at square K and stop at square i, jumping forward by either 1 or 2 squares in each move.

Now, we can reach square i either by jumping 1 square forward from square i-1 or two squares forward from square i-2 (provided they are valid squares). Thus, we add A_i (as we jump to this square, so the value gets added to our score) to the maximum possible over the 2 cases.
The recurrence is as follows.

\text{Forward}(i)=A_i+\max(\text{Forward}(i-1),\text{Forward}(i-2))

There are some base cases that we need to handle.

i<K : This is an out-of-bounds case, as we start from square K (in the forward phase) and only move forward. In this case we return a very large negative number.
i=K : This state is our initial state (as we start out at square K) and our score in this state is 0 (and not A_K since we start out at this square and not jump on it). Here, we return 0.

The existence of overlapping subproblems in our recursion convinces us of the need to use DP.
Let \text{FW}[i] represent the maximum score achievable over all forward phases that start at square K and end at square i.

Thus, the above recursion, along with DP implemented, is given below.

int Forward(int i){
    if(i < K) //Out-of-bounds
        return -INF;
    if(i == K) //Base case
        return FW[i] = 0;

    if(FW[i] != -INF) //Already Computed
        return FW[i];
    //Recurrence of the DP
    FW[i] = A[i] + max(Forward(i - 1), Forward(i - 2)); 
    return FW[i]; //Max score at square i in the forward phase
}

Notice that calling \text{Forward}(N) also calls \text{Forward}(N-1) which calls \text{Forward}(N-2) and so on.
Thus, a single call \text{Forward}(N) suffices to compute the maximum score achievable when the forward phase ends at square i, for all valid i.

Now, let’s solve for the backward phase.
Notice that, both the forward and backward phase show some similarity. In the forward phase, we wanted to maximize the score when moving from square K\rarr i for some valid i. In the backward phase, we want to maximize the score when moving from square i\rarr 1.

Observation : Any valid backward sequence from square i\rarr 1 is also a valid forward sequence from square 1\rarr i.

Proof

Let (i_1, i_2,\dots,i_k) where i_1=i and i_k=1, represent a backward sequence from square i\rarr1.
Thus 1\le i_j-i_{j+1}\le 2 holds for all j.

Now, this implies that i_{k-1}-i_k\le 2 which implies that it is possible to jump from square i_k (which is square 1) to square i_{k-1}.

This can thus be extended similarly for all valid j which brings us to the conclusion that (i_k,i_{k-1},\dots,i_1) is also a valid forward sequence from square 1\rarr i.

This observation now enables us to find the maximum possible score over all forward phases that start at square 1 and end at square i. We can use the above DP code, tweaking the base cases as mentioned below.

i<1 : This is an out-of-bounds case, as there exists no square before square 1. In this case we return a very large negative number.
i=1 : We return A_i in this case, as this is the square at which we stop and can no longer jump backwards.

Let \text{BW}[i] represent the maximum score achievable over all forward phases that start at square 1 and end at square i. Note that, in this case, the values at both the end squares 1 and i are added to the score (in the previous case, the value at square K was excluded), as both are to be counted in the score achieved in the backward phase.

The solution code is thus as follows.

int Backward(int i){
    if(i < 1) //Out-of-bounds
        return -INF;
    if(i == 1) //Base case
        return BW[i] = A[i];

    if(BW[i] != -INF) //Already Computed
        return BW[i];
    //Recurrence of the DP
    BW[i] = A[i] + max(Backward(i - 1), Backward(i - 2)); 
    return BW[i]; //Max score at square i in the backward phase
}

We now merge the calculated results to determine the final answer. The merging is relatively easier.
As we know the maximum score attainable over all forward/backward phases that end/start at square i (for all valid i), the maximum possible score attainable over all valid sequence from K\rarr i\rarr 1 is

\text{FW}[i]+\text{BW}[i]-A[i]

Why the -A[i] at the end?
FW[i] includes the sum of the value on square i and so does BW[i]. Thus, this results in double counting (as in our sequence from K\rarr i\rarr 1, we jump only once on square i) and so we subtract A[i] from the sum.

The answer to our problem is thus the maximum value of the above equation for all valid values of i!

SOLUTION SNIPPET:

int Forward(int i){
    if(i < K) //Out-of-bounds
        return -INF;
    if(i == K) //Base case
        return FW[i] = 0;

    if(FW[i] != -INF) //Already Computed
        return FW[i];
    //Recurrence of the DP
    FW[i] = A[i] + max(Forward(i - 1), Forward(i - 2)); 
    return FW[i]; //Max score at square i in the forward phase
}

int Backward(int i){
    if(i < 1) //Out-of-bounds
        return -INF;
    if(i == 1) //Base case
        return BW[i] = A[i];

    if(BW[i] != -INF) //Already Computed
        return BW[i];
    //Recurrence of the DP
    BW[i] = A[i] + max(Backward(i - 1), Backward(i - 2)); 
    return BW[i]; //Max score at square i in the backward phase
}

//INF = INT_MAX
FW.resize(N, -INF); BW.resize(N, -INF); //uninitialised state
Forward(N - 1); Backward(N - 1);

int ans = -INF; //To hold our final answer
for(int i = K; i < N; i++){
    //Overall maximum score if we stop forward phase at square i
    int maxi = FW[i] + BW[i] - A[i];
    ans = max(ans, maxi);
}
cout << ans << endl;

TIME COMPLEXITY:

There are N-K states (K\rarr N) in the DP solution of the forward phase. Similarly, there are N states (1\rarr N) states in the DP solution of the backward phase.
Computing each state of the DP takes O(1).

The iteration over all valid n to determine the maximum possible score takes time O(N).

Therefore, the overall complexity of the solution is

O((N-K)+N+N) \approx O(N)

SOLUTIONS:

Editorialist’s solution can be found here.