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

Given an array A containing positive integers, count the number of its subarrays that can be sorted by performing the following operation any number of times:

  • Choose an element and multiply it by -1.

EXPLANATION:

First, we must understand when an array A is sortable by negating some of its elements.

The fact that all the elements of A are initially positive is powerful here.
In particular, observe that if we decide to negate index i, then we are forced to negate all indices smaller than i as well - because -A_i would otherwise be smaller than some positive element before it.

This means the only reasonable operation we have is to choose a single prefix of A, and negate all its elements.
Suppose we are able to do this with the prefix of length k, meaning

-A_1 \le -A_2 \le\ldots\le -A_k \le A_{k+1} \le\ldots\le A_N

For the first k elements to be non-decreasing after negation, they must’ve been non-increasing before negation.
So, we obtain two conditions:

  • A_1 \ge A_2 \ge\ldots\ge A_k, and
  • A_{k+1} \le A_{k+2} \le\ldots\le A_N

That is, the array A must first decrease, then increase.

It’s now easy to see that such a condition is both necessary and sufficient for A to be sortable.
Necessity has been shown above already; as for sufficiency, if the array is of this form we can simply negate the descending prefix and obtain a sorted array.
(Again, this is contingent on all elements initially being positive.)

The above characterization is what we’ll use to solve the problem.
We’re interested in counting the number of subarrays that first descend, then ascend.
For simplicity, we call these V-shaped subarrays.
Note that subarrays that are either only non-increasing or only non-decreasing also count as V-shaped.

One way to compute the number of V-shaped subarrays quickly is with dynamic programming.

Define dp_R to be the number of V-shaped subarrays ending at index R.
Then,

  • If A_R \ge A_{R-1}, any V-shaped subarray ending at index R corresponds to taking a V-shaped subarray ending at index (R-1) and appending element A_R to it.
    Also, we have the singleton subarray [A_R] itself.
    So, dp_R = dp_{R-1} + 1 in this case.
  • If A_R \lt A_{R-1}, observe that it’s impossible to include both A_R and A_{R-1} into a V-shaped subarray that has a non-decreasing part.
    So, the only possible “V-shaped” subarrays ending at index R, are those subarrays that are only non-increasing.

To deal with the second case, we simply maintain the number of non-increasing subarrays as well!
That is, define dec_R to be the number of non-increasing subarrays ending at index R.
Then,

  • If A_R \le A_{R-1}, we can extend any valid subarray ending at R-1 into a subarray ending at R.
    This gives dec_R = dec_{R-1} + 1.
  • If A_R \gt A_{R-1}, then the only option is to take [A_R] itself, so that dec_R = 1.
  • Once the above has been computed,
    • If A_R \ge A_{R-1}, we already saw that dp_R = dp_{R-1} + 1.
    • Otherwise, we simply have dp_R = dec_R.

The final answer is

dp_1 + dp_2 + \ldots + dp_N

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
n = int(input())
a = list(map(int, input().split()))

dec = [1]*n
dp = [1]*n
for i in range(1, n):
    if a[i] <= a[i-1]:
        dec[i] += dec[i-1]
    
    if a[i] >= a[i-1]:
        dp[i] += dp[i-1]
    else:
        dp[i] = dec[i]
print(sum(dp))