GENPERM - Editorial

PROBLEM LINK:

Practice
Contest

Author: Archit Karandikar
Tester: Jingbo Shang
Editorialist: Vaibhav Tulsyan

PROBLEM

For a permutation P = (p_1, p_2, ..., p_N) of numbers [1, 2, ..., N], we define the function f(P) = max(p_1, p_2) + max(p_2, p_3) + ... + max(p_{N-1}, p_N).

You are given N and an integer K. Find and report a permutation P of [1, 2, ..., N] such that f(P) = K, if such a permutation exists otherwise print -1.

Note f([ 1 ]) = 0.

Constraints:

1 \le T \le 40

1 \le N \le 10^{5}

Sum of N over all test cases in each file \le 10^{6}

1 \le K \le 2.10^{10}

EXPLANATION

What are the minimum and maximum values of f(P) that are possible?

The permutation that gives the minimum value of f(P) is f(P_{min}): [1, 2, 3, ... , N] and the permutation
that gives the maximum value of f(P) is f(P_{max}): [1, N, 2, (N - 1), ...].

K must lie between f(P_{min}) and f(P_{max}) for a valid permutation to exist.

Approach

Let’s start from P_{min} and move towards P_{max} by modifying the permutation incrementally.

Consider f(P) = f(P_{min}). If we swap N and (N - 1), we get:

P' = [1, 2, 3, ... , N, (N - 1)]

Observe that f(P') = f(P) + 1.

Similarly, if we swap N and (N - 2), we get permutation P" = [1, 2, 3, ... , N, (N - 2), (N - 1)].

f(P") = f(P') + 1.

Hence, we can see that the value of f increases by 1 for every move that we do.
The position of each number can be determined uniquely!

O(K) brute-force solution

We can keep performing swaps until we reach a permutation P with its f(P) equal to K.

This approach would exceed the time-limit and hence we need to find a faster solution.

O(N) solution

The change in value (\Delta_1) of f(P) for bringing N from index N to 2 is (N - 2).
Similarly, change in value (\Delta_2) bringing (N - 1) to index 4 after that is (N - 4).

\Delta_i = (N - 2.i)

We keep constructing the permutation [1, N, 2, (N - 1), ... , j, (N - j + 1), ...] until \sum\limits_{i=1}^j \Delta_j \le K.

Now, we need to append to the above, an arrangement of the numbers [(j + 1), (j + 2), ... , (N - j)].
We will need to keep moving (N - j) to a previous index if K > \sum\limits_{i=1}^j \Delta_j, because we still need to cover the remaining value which is K - \sum\limits_{i=1}^j \Delta_j.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

3 Likes

#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int n,k,va;
cin>>n>>k;
if(n==1)
{
va=0;
}
else
{
va=n*(n+1);
va=(va/2)-1;
}
if(va==k)
{
for(int i=n;i>=1;i–)
{
cout<<i<<" “;
}
cout<<”\n";
}
else
{
cout<<"-1\n";
}
}
return 0;
}