ASCDESC - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: raysh07
Tester: sushil2006
Editorialist: raysh07

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

f(P) is sum of ascents in P and descents in P^{-1}. Find a permutation P of length N = 10^5 with f(P) \ge 1.99 \cdot 10^5.

EXPLANATION:

Note that f(P) is trivially bounded by 2 \cdot N - 2, and hence we are asked to construct a nearly optimal permutation. Infact, we are allowed to be off the trivial bound by at most 1000 (at most 998 to be exact).

We use square root decomposition ideas for this, assume N = B^2 is a perfect square for now.

Create B increasing chains each of length B in P, which helps get B(B - 1) ascents in P.

The last increasing chain should contain the numbers 1, B + 1, 2 \cdot B + 1, .....

The 2nd to last increasing chain should contain the numbers 2, B + 2, 2 \cdot B + 2, ....

And so on, the first chain should contain B, 2 \cdot B, 3 \cdot B, .....

Hence, the construction looks like

[B, 2B, 3B, .......], [B - 1, 2B - 1, 3B - 1, ....., ], [B - 2, ....], ....., [1, B + 1, 2B + 1, ...] (brackets added for clarity

In this way, we make 1 appear after 2, 2 appear after 3, …, B - 1 appear after B (because they lie in latter chains). Thus (for Q = P^{-1}) Q_i < Q_{i + 1} for all these pairs. Infact only for i \bmod B = 0, Q_i < Q_{i + 1} is not satisfied.

This construction obtains 2 \cdot B \cdot (B - 1) which is N - 2 \cdot B = N - 2 \cdot N^{0.5}.

When N is a not a perfect square, we can solve for the largest square (say S) \le N, and then append [S + 1, \ldots, N]. Here, we can ensure f(P) \ge N - 3 \cdot N^{0.5} which is good enough.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist'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;
    
    auto f = [&](vector <int> p){
        int ans = 0;
        vector <int> q(n);
        for (int i = 1; i < n; i++){
            ans += p[i] > p[i - 1];
        }
        for (int i = 0; i < n; i++){
            q[p[i]] = i;
        }
        for (int i = 1; i < n; i++){
            ans += q[i] < q[i - 1];
        }
        return ans;
    };
    
    vector <int> p(n);
    int s = sqrt(n);
    int cnt = 0;
    
    for (int i = 0; i < s; i++){
        for (int j = s - 1; j >= 0; j--){
            p[j * s + i] = cnt++;
        }
    }
    
    while (cnt < n){
        p[cnt] = cnt;
        cnt++;
    }
    
    int val = f(p);
    // cout << val << "\n";
    for (auto x : p){
        cout << (x + 1) << " ";
    }
    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;
}