DELELE2 - 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:

TBD

PREREQUISITES:

None

PROBLEM:

An array A is deletable if it can be reduced to size \le 2 via the following operation:

  • Choose an index i (1 \lt i \lt |A|) such that A_{i-1} + A_{i+1} \ge A_i
  • Add X to A_{i-1} and Y to A_{i+1} such that X+Y=A_i to either of its neighbors.
  • Delete A_i from the array.

Given an array A, count the number of deletable subarrays.

N \le 2000.

EXPLANATION:

Let’s understand when an array A of length N is deletable itself.
If N \le 2 it’s trivially true, so we assume N \ge 3.

Intuitively, an element can be deleted (and its value split between its neighbors) if it is “small”.
This suggests that “large” values are the ones causing issues, and the larger the element, the more likely it is to cause trouble.
However, this doesn’t apply to endpoints - i.e. A_1 and A_N; for these values it’s always better to be large since they will never appear in the ‘middle’ of the array even after deletions.

With this in mind, let’s look at the largest element in the middle of the array, i.e the element

\max(A_2, A_3, \ldots, A_{N-1})

Let’s denote this value by M.
We’ll try to figure out some bound on large M can be before bad things happen.

Observe that upon performing an operation, the sum of the array remains unchanged since we just split the chosen A_i among its neighbors.

With this in mind, let’s look at what happens in the very final merge, i.e. the one that brings the array down to length 2.
Just before the merge, the array looks like [x, y, z] where x+y+z = \text{sum}(A).
If y is too large here, we run into issues - specifically if y \gt x+z.
This translates to 2y \gt x+y+z = \text{sum}(A).

That is, if the middle element in the end is larger than half the total sum, then we’re unable to perform the final merge.

The above observation can be further extended: if we ever have an element in the middle (i.e. not at an endpoint) that’s larger than half the sum, then we can never get rid of it - since we’ll never be able to choose it for merging; and performing the operation on other elements cannot reduce this one’s value.

In particular, if M = \max(A_2, \ldots, A_{N-1}) is already larger than half of \text{sum}(A), the array A is surely not deletable.

But what if it isn’t, i.e. 2M \le \text{sum}(A)?
Then the array is always deletable!

Proof

Let S = \text{sum}(A), and suppose that 2M \le S.
Note that this implies that every element in the middle is also \le S/2.
(Here, by middle we mean any element that’s not at an endpoint.)

Now look at the minimum element in the middle (if there are multiple occurrences, choose any one.)
This element can surely be operated on - we just need to decide how to distribute its value.

If the chosen minimum is adjacent to either position 1 or position N, we can then give its value entirely to the endpoint and be fine.
So, assume the minimum is not next to an endpoint.

Suppose the chosen index is i.
Then, there’s a simple greedy choice:

  • Give as much value as possible to index i-1 while ensuring that it doesn’t exceed S/2.
  • Give all the remaining value to index i+1.

This is always possible, because if it weren’t, that would imply that the total sum of these three elements (at indices i, i-1, i+1) is at least S.
However, since i was not near an endpoint, and the endpoints have values 1 each (at least), the total sum of the array will then become at least S+2, contradicting it having sum S.

Thus, a viable distribution always exists, while ensuring that all middle elements remain \le S/2.
Simply repeat this over and over until the middle is gone.

Since this is the easy version of the problem and quadratic time is allowed, we can use this characterization to obtain a rather simple solution.

Fix L, the left endpoint of the subarray.
We’ll then iterate R, the right endpoint, in the order L, L+1, \ldots, N.
While iterating, store two values: the sum of the current subarray, and also the maximum element among the values \{A_{L+1}, A_{L+2}, \ldots, A_{R-1}\}.

Knowing the sum of the subarray and its internal maximum, we can then easily tell if the subarray is deletable or not in constant time.

This gives a quadratic solution, which is fast enough here.

TIME COMPLEXITY:

\mathcal{O}(N^2) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 0
    for i in range(n):
        sm, mx = 0, 0
        for j in range(i, n):
            sm += a[j]
            if j > i+1: mx = max(mx, a[j-1])
            
            if j <= i+1 or 2*mx <= sm: ans += 1
    print(ans)
DELELE - Editorial