PROBLEM LINK
Panel Members
Problem Setter: Suhash
Problem Tester:
Editorialist: Sunny Aggarwal
Contest Admin:
Russian Translator:
Mandarin Translator:
Vietnamese Translator:
Language Verifier:
DIFFICULTY:
Medium
PREREQUISITES:
Constructive Algorithm, Implementation, Observation, Simulation.
PROBLEM:
Given 2 integers N and K and we are asked to find the lexographically smallest permutation of first N natural number such that abs(i - position_i) \ge K for every i \in [1, N] if such a permutation exists. Print -1 otherwise.
EXPLANATION
We can claim that when K \le \lfloor{N/2}\rfloor, lexographical smallest solution will have the following form for each 2 * K size block i.e lexographically smallest answer will have first 2 * K elements present in the following order and similar order for each set of 2 * K elements.
K+1, K+2, K+3... ,2*K, ... 1, 2, 3, ... K
Note that if N\%(2*K) == 0 then we can perform shuffling as depicted above for each (N/(2*K)) set of 2*K size each otherwise we have to shuffle the remaining elements with the elements present before them to make a block of size 2*K and need to shuffle them as we did above.
We can also claim that no answer exist if K \gt \lfloor{N/2}\rfloor because the number that we can put in the position 1 to \lfloor{N/2}\rfloor are greater than \lceil{N/2}\rceil and the number that we can put in the position \lceil{N/2}\rceil+1 to N are less than \lfloor{N/2}\rfloor+1 . So we can’t put any number in position \lceil{N/2}\rceil.
COMPLEXITY
O(N*T)