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

Easy

PREREQUISITES:

Dynamic programming

PROBLEM:

Define f(A) as the largest integer M such that [1, 2, \ldots,M] appears as a subsequence of A.

Given an array A, compute the sum of f(A) across all contiguous subarrays of A.

EXPLANATION:

For a fixed array A, computing f(A) can be done easily using a greedy algorithm as follows:

  • Let i_1 be the smallest index such that A_{i_1} = 1.
    Pick this element, if it exists.
  • Let i_2 \gt i_1 be the smallest index such that A_{i_2} = 2.
    Pick this element, if it exists.
  • Let i_3 \gt i_2 be the smallest index such that A_{i_3} = 3.
    Pick this element, if it exists.
    \vdots

In general, starting with 1 we can simply keep picking the nearest element to the right till it’s no longer possible to do so.

We can turn this greedy solution into a mechanism for summing up f(S) across all subarrays S, by computing the contribution of each element.
That is, for each element, we’ll try to figure out in how many subarrays it’s chosen by the greedy algorithm.

Consider some index i.
Let’s analyze when it will be chosen by a subarray.

First, consider the case of A_i = 1.
In this case, i will be chosen only if it is the leftmost occurrence of 1 in the array.
So, if we let j \lt i be the nearest occurrence of 1 to the left of i, we see that i will be chosen exactly for those subarrays [L, R] satisfying j \lt L \le i and R \ge i.
There are (i-j)\cdot (N-i+1) such subarrays, so add this to the answer.

Next, consider the case of A_i \gt 1.
In this case, for i to be chosen, there must exist an index j \lt i such that:

  1. A_j = A_i - 1,
  2. j is itself chosen, and
  3. No other occurrence of value A_i appears in the range [j, i-1] of indices.

To deal with this, let’s define l_i \lt i to be the nearest occurrence of value A_i to the left of index i.
Then, we only need to consider values of j in the range [l_i+1, i-1].

Now note that we can simply iterate through all such j that we have as candidates!
(Make sure to only iterate through occurrences of value A_i - 1 in this range, and not all indices.)

This works because each element will be iterated through at most once - since value A_i can be iterated over exactly by the nearest occurrence of A_i + 1 to its right.

This allows us the following solution.

Define c_i to be the number of left endpoints for which index i can chosen by the greedy algorithm (note that the choice of right endpoint doesn’t matter at all for whether i is chosen; so once we know the number of left endpoints we can simply multiply it by the number of indices \ge i.)

Define l_i \lt i to be the nearest occurrence of A_i to the left of i.

Then,

  • If A_i = 1, we have c_i = (i - l_i)
  • If A_i \gt 1 we have c_i = \sum c_j, where j varies over all indices in the range [l_i+1, i-1] with value A_i - 1.

This takes \mathcal{O}(N) time if implemented properly.

The answer is

\sum_{i=1}^N c_i \cdot (N-i+1)

to account for choice of right endpoint.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    pos = [ [] for _ in range(n+1) ]
    c = [0]*n
    for i in range(n):
        lt = -1 if not pos[a[i]] else pos[a[i]][-1]
        
        if a[i] == 1:
            c[i] = i - lt
        else:
            for j in reversed(pos[a[i]-1]):
                if j <= lt: break
                c[i] += c[j]
        pos[a[i]].append(i)

    ans = sum(c[i] * (n-i) for i in range(n))
    print(ans)