ADJSUM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Dynamic programming

PROBLEM:

An array is called good if every non-zero element equals the sum of its neighbors.

You’re given an array A. Find the minimum number of operations needed to make it good, where in one operation you can increment or decrement a single element by 1.
All elements must be non-negative at all times.

EXPLANATION:

Let’s figure out what a good array must look like.

Obviously, if A consists of only zeros, it’s good - so we look at the case where it contains some positive elements.
Let i_1 be the index of the leftmost positive element in A.
Then, we want A_{i_1} = A_{i_1 - 1} + A_{i_1 + 1} to hold.
However, we know A_{i_1 - 1} = 0, since everything to the left of index i_1 is a 0.
This means we have A_{i_1} = A_{i_1 + 1}.

However, applying the condition to index i_1 + 1, we see that we’re forced to have A_{i_1 + 2} = 0.
So, essentially we have two equal elements surrounded on both sides by zeros.

The same logic can then be applied to the next non-zero element after index i_1 + 2, and so on.

In general, it can be seen that in a good array, we’ll have several pairs of equal adjacent elements, and each of these pairs will be separated by a positive number of zeros.

Now we need to find the minimum number of moves needed to achieve this state.
To do that, we can use dynamic programming.

Define dp_i to be the minimum number of operations to make the first i elements of the array satisfy the necessary condition.
To compute dp_i, there are two possibilities:

  1. We can set A_i = 0.
    This has a cost of A_i (since the only way to do this is to repeatedly decrease A_i by 1).
    Then, the remaining i-1 elements just have to satisfy the condition among themselves; and by definition the minimum cost to achieve that is dp_{i-1}.
    So, one possibility is (A_i + dp_{i-1}).
  2. We can have A_i \gt 0.
    If we decide to do this, then A_i and A_{i-1} must be made equal (since non-zero elements come in equal pairs), and also A_{i-2} must be made 0 (since positive pairs need to be separated by zeros).
    Making A_i and A_{i-1} equal has a cost of |A_i - A_{i-1}|, and making A_{i-2} equal 0 has a cost of A_{i-2}.
    Once these are done, the remaining prefix can be solved independently; and its minimum cost is dp_{i-3} by definition.
    So, the other option we have is (A_{i-2} + |A_i - A_{i-1}| + dp_{i-3}).

Thus, quite simply, we end up with

dp_i = \min(A_i + dp_{i-1}, A_{i-2} + |A_i - A_{i-1}| + dp_{i-3})

Compute this for all i, and the answer is dp_N.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = [0, 0, 0] + list(map(int, input().split()))
    dp = [0]*len(a)
    dp[3] = a[3]
    for i in range(4, len(a)):
        dp[i] = a[i] + dp[i-1]
        dp[i] = min(dp[i], abs(a[i] - a[i-1]) + a[i-2] + dp[i-3])
    print(dp[-1])