ZCO 2014 (last year) problem

general
1

http://www.iarcs.org.in/inoi/2014/zco2014/zco2014-2b.php

How to tackle such problems…

2

Is there any way through which we can submit the problem?

3

@bharatt- No you cannot submit it anywhere.

@kshitijkmr10- I have a DP solution(which I am pretty sure is correct) which I can discuss with you if you want to.

4

yeah sure, why not!.. @roxtar123

5

@kshitijkmr10 I told you my dp solution but havent been able to convince you. So I would like @roxtar123 or any other student answer this before telling my DP solution.

6

So basically we can pick atmost 2 consecutive elements from the array.
Let the input be in array x.
Let dp[i] denote the maximum sum we can obtain till x[i] by choosing atmost 2 consecutive elements.
Trivial Cases-
dp[0]=0;
dp[1]=x[1];
dp[2]=x[1]+x[2];

Now we try filling dp array from i=3 to n.
We have 3 options-

  1. We take max sum till x[i-1]. Here we cant take x[i] as dp[i-1] has sum till x[i-1].
  2. Take max sum till x[i-2] and add x[i].
  3. Take max sum till x[i-3] and add x[i] as well as x[i-1].

Now we fill dp[i] with the maximum of these 3 possible ways.

So our answer will be in dp[n].