ZCO14002 - Editorial

PROBLEM SETTER -
ZCO 2014

DIFFICULTY
Easy-medium

PREREQUISITES
Dynamic Programming

PROBLEM IN SHORT
We have to select some elements from the array, so that the sum of selected elements is as minimum as possible with respect to constraint that there should not be 3 or more unselected consecutive elements.

KEY OBSERVATIONS
Suppose, for some i in 1,…,N, we want to calculate the answer for the array [1,i], if we select i^{th} element and we know the answer for arrays [1,i-1] , [1,i-2] and [1,i-3], selecting (i-1)^{th}, (i-2)^{th} and (i-3)^{th} element respectively. The answer for array [1,i] would be minimum of answer of the 3 arrays – minimum( [1,i-1] , [1,i-2] and [1,i-3] ) + a*.

EXPLANATION
From key observations, we can build a recurrence. This recurrence can be easily implemented by dynamic programming. dp* denotes the minimum answer for array [1,i] by selecting i^{th} element.
The recurrence code will look like this –

    int r[] = {1,2,3};
    for(int i = 1;i < n+1;i++)
	{
		for(int j = 0;j < 3;j++)
		{
			if(i-r[j] >= 0)
				dp* = min(dp*,a* + dp[i-r[j]]);
			else
				dp* = a*;
		}
	}

The above recurrence is in accordance with the key observation.
The answer to the problem would be minimum of dp[N], dp[N-1] and dp[N-2], as we have to select one of the element from the last 3 indices in order to follow the constraint that there should not be 3 or more un-selected consecutive elements.

ANOTHER INTERESTING SOLUTION
The problem IPL (ZCO14004) and this problem are very much related. So much so, that a 1-2 line change in the code of either problem can work as the solution for the other problem. This is because of a very simple relation - Sum of elements of array = answer of problem IPL + answer of problem SUPW. The proof of this relation is left on to the readers to be derived.

TIME COMPLEXITY -
O(N*3)

4 Likes

I am getting runtime error in this implementation.
Can someone pls point out the mistake?

n = int(input())
l = list(map(int,input().split()))

dic = {}
dic[0] = l[0]
dic[1] = l[1]
dic[2] = l[2]


def solve(x):

    if x not in dic:
        dic[x] =  min(solve(x-1),solve(x-2),solve(x-3)) + l[x]

    return dic[x]


if n < 3:
    print(0)
else:
    print(min(solve(n-1),solve(n-2),solve(n-3)))