PROBLEM LINK:
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.