REIGN - Editorial

PROBLEM LINK:

link:Contest

Author: @kostya_by

Tester: @white_king

DIFFICULTY:

Easy

PROBLEM:

This can be solved using dynamic programming.
Call best_forward* to be the maximum prosperity of a sequence that ends at i. This can be computed as:
best_forward*=max(A*, best_forward[i-1] + A*).

From this, you may easily compute the maximum prosperity of any sequence that ends anywhere between 0…i as:
cumulative_best_forward* = max(cumulative_best_forward[i-1], best_forward*).

Similarly let best_backward* be the maximum prosperity of a sequence starting at i
best_backward*=max((ll)A*, best_backward[i+1] + A*). Similarly, you compute cumulative_best_backward*.

The answer is simply
max_{j=K+2 to N} (cumulative_best_forward[j-K-1] + cumulative_best_backward[j]).

4 Likes

I used the same approach. The maximum ‘prosperity’ in this problem is a popular problem - Maximum Subarray
.

Here’s my solution: REIGN

2 Likes

A similar problem appeard in jun13 DELISH

2 Likes

My idea is kind of similar, but not exactly the same. Instead of finding cumulative_best_forward* from best_forward* and cumulative_best_forward[i-1], I tried to directly obtain a recurrence relation for cumulative_best_forward[].

I defined two arrays - result* -> best sum upto i (not necessarily ending at i, exactly like cumulative_best_forward)

(a* is the array containing input elements)

rem* -> if the best sum upto i, is made by choosing the interval [j,k] 0<=j<=k<=i, then rem* = a[k+1]+a[k+2]+…a* i.e the sum of the elements to the right of the best interval, and before i which are not part of the interval (the sum of the remainder elements)

Next I wrote the following recurrence relations for the two arrays:

if (a[i+1]+rem* >=0 && result*+rem* >=0) { result[i+1] = result*+rem*+a[i+1]; rem[i+1] = 0; }

else if (a[i+1] >= result*) { result[i+1] = a[i+1]; rem[i+1] = 0; }
else {result[i+1] = result*; rem[i+1] = rem* + a[i+1];}

And after getting result* in the forward direction, I did the same for the backward, and looped through the input array to find the final answer.

I tried this, but my solution was not accepted (WA): http://www.codechef.com/viewsolution/3103902
Is there something wrong with my recurrence relation? I’m unable to find the mistake.
(I know it’s kind of complicated when compared to the traditional maximal sub-arrays solution, but I’m still new to DP, so I want to find the mistake in my thinking)
Can someone please help?

nice job

i Am getting wa…can anyone provide me any test case for which my code fails http://www.codechef.com/viewsolution/3448210