ZCO12004-Editorial

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

EASY

PREREQUISITES:

Dynamic programming

PROBLEM:

You are given a circular array A consisting of N integers. A_i is adjacent to A_{i+1} for all 1 \le i < N (A_1 is adjacent to A_N). You have to select a set of elements from A such that, for every pair of adjacent elements in A, at least 1 element is present in the set.
Determine the minimum possible sum of values in the set.

EXPLANATION:

Let us forget about the circular part, and first try solving this problem for a linear A.

Statement: If A_i is present in the set, A_{i-1} or A_{i-2} has to be present in this set.

Proof

Fact: For every valid i, A_i or A_{i+1} has to be present in the set.
Assume when A_i is present, both A_{i-1} and A_{i-2} doesn’t exist in the set. This cause’s a contradiction to the fact stated above.

Thus, the statement holds true.

Lets define Minim(i) as the minimum possible sum of a (valid) set for the first i elements in linear A, where A_i is an element in the set. Thus a basic recursive solution would be as follows:

int Minim(i){
	return A[i] + min(Minim(i - 1), Minim(i - 2));
	//Out of bound cases to be handled!
}

Lets examine this simple code snippet. Recall Minim(i) refers to the minimum possible sum of a set for the sub-array A_1, A_2, \dots, A_i, when A_i is present in the set.

  • A[i] + \dots : A[i] is being added since this element is present in the set (as mentioned above)
  • min(\dots) : From the proof above, we know that at least one of A_{i-1}, A_{i-2} is present in the set. We want to select one of these elements in such a way, such that the overall sum is minimized. Thus min(\dots) is used.
  • \text{Minim}(i-1) : From the definition of Minim(i) above, it is quite clear that now we are trying to find the minimum sum for the sub array A_1, A_2,\dots,A_{i-1}. This is defined similarly for \text{Minim}(i-2) also.

Why is this recurrence valid? This is because, any set of elements selected from sub array A_1,A_2,\dots,A_{i-1} isn’t dependent on the values of any element after this sub array (Why?).

This simple recurrence is all there is to solve for linear A. The solution for this variant of the problem can be found by calling Minim(N).

But wait! Do you realise that a function call Minim(i) is being made multiple times for the same value of i?

Illustration through example

Let N = 3. This is the sequence of function calls:

Minim(3) gives a function call to Minim(2) and Minim(1).

Minim(2) gives a call to Minim(1) (Minim(0) is ignored here since it goes out of bounds).

Notice Minim(1) is called 2 times here. As N increases, the number of overlapping calls also increase.

Who likes to do the same thing multiple times? Chores and duties, no complains :stuck_out_tongue_winking_eye: ​, but otherwise no one likes it. Yes! Even the computer doesn’t like it and takes time to compute it every time. So what do we do? We store all pre-computed results, so that anytime the same value is asked to be computed, the computer can just spit out the already calculated (and stored) information.

Summary of the above para : We use DP to prevent re-computations.

The recursive code with DP would be as follows:

int Minim(i){
	if(Minim[i] == Computed) //Array Mini[i] = Minim(i).
        return Mini[i]; //Computed checks if this value is computed
    
    Mini[i] = A[i] + min(Minim(i - 1), Minim(i - 2)); //memoization
    return Mini[i];
}

Now let us come back to solving for circular array A. In this, at least one of A_1, A_N has to be present in the set. The case when A_N is present in the set is already covered by Minim(N), but how do we do for the case when A_1 is present?

Of all the different solutions used, the simplest one is as follows. We reverse A, and solve linearly for reversed A. Why is this true? This is because, reversing the array doesn’t change any of its properties (since its a circular array), and thus, the answer still remains valid. Now we solve similarly using the same Minim(i) function above, and Minim(N) now returns the minimum sum when A_1 is present in the array (since the array is reversed, so A_1 becomes A_N and vice-versa).

Now, do we really need to reverse the array? Not actually. We could make a new function Minim1(), in which we just change the function to call Minim(i + 1) and Minim(i + 2) in place of Minim(i - 1) and Minim(i - 2). Thus calling Minim(1) returns the minimum possible answer in this case.

If you’re unable to understand the above para clearly, try some examples to understand whats happening.

The code for this (with DP) is as follows:

int Minim1(i){
	if(Mini1[i] == Computed) //Array Mini1[i] = Minim(i).
        return Mini1[i]; //Computed checks if this value is computed
    
    Mini1[i] = A[i] + min(Minim1(i + 1), Minim1(i + 2)); //memoization
    return Mini1[i];
}

Thus the answer is the minimum between Minim(N) and Minim1(1).

SOLUTION SNIPPET:

int Minim(int i){ //To calculate case (1), when A[N] is the selected element
    if(i < 1 or i > N) return 0; //Out of bound case
    
    if(Mini[i] != -1) //If it has been computed
        return Mini[i];
    
    Mini[i] = A[i] + min(Minim(i - 1), Minim(i - 2)); //Memoization
    return Mini[i];
}

int Minim1(int i){ //To calculate case (2), when A[1] is the selected element
    if(i < 1 or i > N) return 0; //Out of bound case
    
    if(Mini1[i] != -1) //If it has been computed
        return Mini1[i];
    
    Mini1[i] = A[i] + min(Minim1(i + 1), Minim1(i + 2)); //Memoization
    return Mini1[i];
}

cout << min(Minim(N), Minim1(1)) << endl;

TIME COMPLEXITY:

Since there are only N unique DP states, and computation of each state takes O(1), overall complexity is

O(N + N) \approx O(N)

N+N since there are two DP arrays that we compute!

MEMORY COMPLEXITY:

Each DP array takes O(N) memory, thus overall memory complexity is

O(N+N)

SOLUTIONS:

Editorialists solution can be found here.

Bonus (for newbies to DP): Make a bottom-up solution!

HINTS:

Hint 1

The base cases are Mini[1] = A[1] and Mini[2] = A[2].

Hint 2

The iterative solution moves upwards from computing Mini[1] to Mini[N].

Hint 3

Converting the recurrence into iterative is very easy here. Mini[i] = A[i] + min(Mini[i - 1], Mini[i - 2]).

Hint 4

Similar method can be used to compute Mini1[i]. Thus answer is thus min(Mini[N], Mini1[1]).

SIMILAR PROBLEMS:

ZCO14002
ZCO14004

Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!

Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome :star_struck: editorial)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

Also don’t forget to up-vote this post if you liked it ! :smile:

4 Likes

Instead of reversing can we delete first element and put it in last?

1 Like

Yea, definitely. Infact I would have vouched for this method, but it would require knowledge of an additional container, namely deque. I wanted to keep the editorial as simple as possible, so I refrained from doing this.
Another method exists, where the last/first element is appended to the end/beginning of the array, and we would use a series of if loops to solve the 2 cases.
This would however add extra constraints in the recurrence(the recurrence solution is preferred due to its clarity in understanding), which would make it difficult to follow for a newbie. Thus, the reason for following this technique!
:smile:

1 Like