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

None

PROBLEM:

An array B is good if it can be converted to a strictly increasing array by performing the following operation several times:

  • Choose an index i and a positive integer X, and replace B_i by B_i\bmod X.

Given an array A, count the number of its subarrays that are good.
Here, N \leq 50 and \text{sum}(N) \leq 500.

EXPLANATION:

The limits on N are quite small in this version, so a reasonable solution would be to try and solve for each subarray in linear time or so, resulting in \mathcal{O}(N^3) overall which will be fast enough.
This means the only thing we need to figure out is: when can an array be made strictly increasing using the given operation?

Consider the array A.
First, for a fixed index i, let’s analyze which values A_i can possibly take.

  • We can of course choose to not operate on index i at all, leaving the value at A_i.
  • If we do operate on it, the resulting value will be strictly smaller than A_i.
  • In particular, look at A_i \bmod X where X \leq A_i.
    • If X \leq \frac{A_i}{2}, then we have (A_i \bmod X) \lt X \lt \frac{A_i}{2}
    • If X \gt \frac{A_i}{2}, then we have (A_i\bmod X) = A_i - X \lt A_i - \frac{A_i}{2} = \frac{A_i}{2}
  • So, no matter what we have A_i\bmod X \lt \frac{A_i}{2}.
  • It’s not hard to see that all the values 0, 1, 2, \ldots, \left\lceil\frac{A_i}{2}\right\rceil - 1 are attainable, by choosing X = A_i, A_i-1, A_i-2, \ldots respectively.

So, A_i can either be unchanged, or some integer in the range [0, \left\lceil \frac{A_i}{2} \right\rceil - 1].

Now, we’re trying to make the array be strictly increasing.
It’s not hard to see that this can be done greedily: make A_1 as small as possible, then make A_2 as small as possible while ensuring that it’s \gt A_1, then make A_3 small but \gt A_2, and so on.

This leads to a simple algorithm:

  • First, set A_1 = 0, which is always possible.
  • Then, for each i = 2, 3, \ldots, N in order:
    • If it’s possible to set A_i to A_{i-1} + 1, do that (note that we’ve already modified A_{i-1} here).
      This is easy to check: the only condition is A_{i-1} + 1 \leq \left\lceil \frac{A_i}{2} \right\rceil - 1.
    • If it’s not possible to do this, the only option is to leave A_i unchanged.
      This can result in a sorted array only if A_i \gt A_{i-1}, so if this check fails then the array isn’t good.

If all the elements can be set appropriately, we’ll have a strictly increasing array and be done; otherwise we won’t be.
This process takes \mathcal{O}(N) time, so just running it for each subarray gives a solution in \mathcal{O}(N^3) time which is good enough here.

TIME COMPLEXITY:

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

CODE:

Editorialist's code (PyPy3) 
def solve(a):
    a[0] = 0
    for i in range(1, len(a)):
        if (a[i]+1)//2 - 1 >= a[i-1] + 1:
            a[i] = a[i-1] + 1
        else:
            if a[i] <= a[i-1]: return False
    return True

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = 0
    for i in range(n):
        for j in range(i, n):
            ans += solve(a[i:j+1])
    print(ans)
2

Dp in the Cpp :stuck_out_tongue:

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &x : v) cin >> x;

    int ans = 1;
    vector<vector<int>> dp(n, vector<int>(n + 1, 1e18));
    dp[0][0] = -1;
    dp[0][1] = 0;

    for (int i = 1; i < n; i++) {
        dp[i][0] = -1;
        for (int len = 1; len <= n; len++) {
            int prev = dp[i - 1][len - 1];
            if (prev == 1e18) continue;
            if ((v[i] - 1) / 2 <= prev) {
                if (v[i] > prev) dp[i][len] = v[i], ans++;
            } else {
                dp[i][len] = prev + 1, ans++;
            }
        }
    }

    cout << ans << endl;
}