SHFSRT - Editorial

editorial
, , ,
1

PROBLEM LINK:

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

Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

You’re given an array A.
You can choose indices i_1 < \ldots \lt i_k such that i_j - i_{j-1} \gt 1 and i_k \lt N, then choose integers x_1, \ldots, x_k, and:

  • Add x_j to the element at index i_j + 1.
  • Subtract x_j from the element at index i_j.

Is it possible to sort A in ascending order?

EXPLANATION:

The array A is sorted if and only if A_i \le A_{i+1} for each 1 \le i \lt N.

Let’s call an index i “bad” if A_i \gt A_{i+1}.

Suppose the bad indices of the array be i_1, i_2, \ldots, i_k from left to right.
Since we can only perform the given operation once, observe that every bad index must be chosen by us.
This is because, if A_i \gt A_{i+1} initially, then only way to make A_i \le A_{i+1} is to transfer some value from index i to index i+1.
(Note that this is specifically because we’re only allowed to transfer positive values only.)

In particular, if there are two adjacent bad indices (i.e. A_i \gt A_{i+1} \gt A_{i+2} for some i), then we cannot include both of them at the same time; so there’s no way make the array sorted.

Thus, we only need to care about the case where all the bad indices are “disjoint”, as in they have distances of more than 1 between them.

We must include every bad index into the chosen subsequence.
It’s also not hard to see that there’s no point in including any non-bad indices: if A_i \le A_{i+1} already then transferring value from the left to the right will only make things worse.

So, the set of indices that need to be chosen is exactly the set of all bad indices of A.
Now that this is fixed, let’s figure out what values to transfer for each one.

Let’s look at the first bad index, i_1.
What should we transfer from it to index i_1+1, i.e. what should x_1 be?
Well, after the transfer, we should certainly have

A_{i_1} - x_1 \le A_{i_1 + 1} + x_1

Since these will be the new values at indices i_1, i_1+1.
This tells us that 2\cdot x_1 \ge A_{i_1} + A_{i_1 + 1} must hold, so we have a lower bound on x_1, that being

\text{ceil}\left(\frac{A_{i_1} - A_{i_1 + 1}}{2}\right)

Now it can be seen that it’s always optimal to choose x_1 to be this lower bound.
This is because, with a higher x_1, both sides cause issues:

  • If we reduce A_{i_1} too much, it might fall below A_{i_1-1}.
  • If we increase A_{i_1 + 1} too much, it might increase to be more than A_{i_1+2}.
    • Further, it might be the case that index i_1+2 is itself bad, which will cause A_{i_1+2} to further reduce when we transfer value from it.
      So, it’s even more beneficial to keep A_{i_1+1} from increasing as much as we’re able to.

Thus, it’s optimal to choose x_1 = \text{ceil}\left(\frac{A_{i_1} - A_{i_1 + 1}}{2}\right).

In fact, this exact same reasoning tells us that for each j, it’s optimal to choose

x_j = \text{ceil}\left(\frac{A_{i_j} - A_{i_j + 1}}{2}\right)

which is the smallest amount that needs to be transferred.

After making all these minimal necessary transfers, simply check if the resulting array is sorted.
If it is, we’re done. If not, it’s impossible to end up with a sorted array.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0);
        for (int &x : a) cin >> x;
    
        for (int i = 0; i+1 < n; ++i) {
            if (a[i] <= a[i+1]) continue;
            
            int shift = (a[i] - a[i+1] + 1) / 2;
            a[i] -= shift;
            a[i+1] += shift;
            ++i;
        }
        
        if (ranges::is_sorted(a)) cout << "Yes\n";
        else cout << "No\n";
    }
}