**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[i].

**EXPLANATION** –

From key observations, we can build a recurrence. This recurrence can be easily implemented by dynamic programming. dp[i] 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[i] = min(dp[i],a[i] + dp[i-r[j]]); else dp[i] = a[i]; } }

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)