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)