AMR15C - Editorial

acmamr15
amr15c
constructive
editorial
greedy
implementation
medium

#1

PROBLEM LINK

Practice
Contest

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)