GREEDYLIS - Editorial

editorial
,
1

PROBLEM LINK:

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

Author: raysh_07
Tester: mridulahi
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given N and X, find a permutation of length N such that the difference between its actual LIS length and greedy LIS length is exactly X.
The greedy LIS is obtained by taking elements from left to right whenever possible.

EXPLANATION:

Alice’s greedy process always takes the first element, so we have some control there: we can try to ensure that the actual LIS doesn’t include the first element.

Suppose we set P_1 = K, and then place everything else after it to obtain the permutation

[K, 1, 2, 3, \ldots, K-1, K+1, \ldots, N]

The greedy algorithm will result in the sequence [K, K+1, K+2, \ldots, N], of length N-K+1.
The actual LIS however, is to ignore K and take everything else, for length N-1.
Note that this assumes K\gt 1.

The difference between these values is N-1 - (N-K+1) = K-2.
So, by choosing K = 2, 3, 4, \ldots, N we have a construction for differences X = 0, 1, 2, \ldots, N-2 already!

This only leaves X = N-1 and X = N.
X = N is clearly impossible to achieve as a difference.
X = N-1 is also almost always impossible to achieve: after all, the only way to obtain a difference of N-1 is if the greedy algorithm gives a length of 1 and the true LIS length is N; but if the true length is N the permutation must be [1, 2, \ldots, N] (in which case the greedy algorithm also gives an answer of N).

The only exception to this is N = 1, in which case N-1 = 0 is attainable as a difference.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

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

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

void Solve() 
{
    int n, x; cin >> n >> x;
    
    if (x == n || (x == n - 1 && n != 1)){
        cout << -1 << "\n";
        return;
    }
    
    if (n == 1){
        cout << 1 << "\n";
        return;
    }
    cout << x + 2 << " ";
    for (int i = 1; i <= n; i++) if (i != (x + 2)) cout << i << " ";
    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 (Python) 
for _ in range(int(input())):
    n, x = map(int, input().split())
    if x == n:
        print(-1)
    elif x <= n-2:
        print(x+2, *list(range(1, x+2)), *list(range(x+3, n+1)))
    elif n == 1:
        print(1)
    else:
        print(-1)
1 Like