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

None

PROBLEM:

An array is said to be smoothly increasing if it’s strictly increasing, and its difference array is smoothly increasing.

You’re given an array A. For each index i, check if the array formed by deleting the single element A_i from A is smoothly increasing.

EXPLANATION:

An array being smoothly increasing is a fairly strong condition: it should be strictly increasing, its difference array should be strictly increasing, the second-order difference array should be strictly increasing, and so on.

In fact, this condition is so strong that it ends up greatly limiting the length of a smoothly increasing array: in particular, it can be shown that a smoothly increasing array exhibits exponential growth, with A_i \geq 2^{i-1} being a necessary condition.

Proof

One way to see this is to look at the process in reverse.

Starting with A, we repeatedly form the difference array till it becomes a single element, and each of these must be strictly increasing.

Suppose we end up with the singleton element [x_1] in the end. Note that x_1 must be positive.
Then, the previous array must’ve been [x_2, x_2 + x_1] for some positive integer x_2.
The array before that must’ve been [x_3, x_3 + x_2, x_3 + 2x_2 + x_1] for a positive integer x_3.
The array before that must’ve been [x_4, x_4+x_3, x_4 + 2x_3 + x_2, x_4 + 3x_3 + 3x_2 + x_1] for some positive x_4, and so on.

In general, if the first elements of the arrays are x_1, x_2, \ldots, x_k, then the last element of the k-th array will be

\sum_{i=0}^{k-1} \binom{k-1}{i} x_{i+1}

Note that because each x_i must be positive, this is at least as large as

\sum_{i=0}^{k-1} \binom{k-1}{i} = (1+1)^{k-1} = 2^{k-1}

Where the summation is exactly what we obtain via the binomial expansion.
This proves our claim that the elements of a smoothly increasing array must grow at least as fast as powers of two.

Now, we’re dealing with array elements that are \leq 10^9 \lt 2^{30}. So, if an array with these elements has large enough length - specifically, |A| \geq 31 - then it will definitely not be smoothly increasing.

So, if N \geq 32, we definitely know that after deleting a single element, the resulting array will not be smoothly increasing.
This means, when N \geq 32, we can simply print N zeros as the answer.

That leaves the case of N \lt 32. However, this is small enough to just deal with in a brute-force manner.
That is, for each index i, compute the array formed by deleting A_i from A, and just brute-force check if this resulting array is smoothly increasing, by repeatedly computing its difference array and checking for sortedness.

This takes \mathcal{O}(N^2) for a single index, so \mathcal{O}(N^3) overall. However, it’s only done when N \leq 32 so it’s fast enough for the given constraints.
In particular, the worst case is with \frac{200000}{31} tests of N = 31, for which \sum N^3 is about 2\cdot 10^8 so this is fast enough.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase when N \geq 32, \mathcal{O}(N^3) per testcase when N \lt 32.

CODE:

Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

void Solve() 
{
    int n; cin >> n;
    
    vector <int> a(n);
    for (auto &x : a) cin >> x;
    
    if (n > 50){
        for (int i = 1; i <= n; i++){
            cout << "0";
        }
        cout << "\n";
        return;
    }
    
    auto check = [&](vector <int> a){
        while (a.size() > 1){
            for (int i = 1; i < a.size(); i++){
                if (a[i] <= a[i - 1]){
                    return false;
                }
            }
            
            vector <int> d;
            for (int i = 1; i < a.size(); i++){
                d.push_back(a[i] - a[i - 1]);
            }
            
            a = d;
        } 
        
        return true;
    };
    
    for (int i = 1; i <= n; i++){
        vector <int> b;
        for (int j = 1; j <= n; j++){
            if (j != i){
                b.push_back(a[j - 1]);
            }
        }
        
        cout << check(b);
    }
    cout << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // freopen("in",  "r", stdin);
    // freopen("out", "w", stdout);
    
    cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}
Editorialist's code (PyPy3) 
def check(a):
    if len(a) == 1: return '1'
    d = []
    for i in range(len(a) - 1): d.append(a[i+1] - a[i])
    if min(d) <= 0: return '0'
    return check(d)

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))

    ans = ''
    if n < 40:
        for i in range(n):
            b = a[:i] + a[i+1:]
            ans += check(b)
    else: ans = '0'*n
    print(ans)
1 Like
3

The rate when there are two elements is atleast linear .
integrating it becomes quadratic and so on. rate is ( delta in num ) / ( delta in index )

1 Like
4

Nice problem