NeverSayNever's blog

Problem : AMR15C
By NeverSayNever, history, 8 years ago, In English

Hi Codeforces,

Can anybody help me with the following problem ?

Reduced Problem Statement

Given 2 integers N and K. We are asked to print the lexographically smallest permutation of first N natural number such that abs(i - posi) ≥ K for every if it exists where posi is the position of ith element in the permutation.

Constraints:

1 ≤ N ≤ 105

0 ≤ K ≤ N - 1

Example

Input:

3

2 2

3 0

3 1

Output:

-1

1 2 3

2 3 1

Explanation

For the first test case, N = 2 and K = 2. It is impossible to permute [1, 2] in any way such that abs(P[1]-1) >= 2 and abs(P[2]-2) >= 2. Hence, output is -1.

For the second test case, N = 3 and K = 0. We can just set P[i] = i, and hence the answer is 1 2 3 For the third case, the valid permutations are [2, 3, 1] and [3, 1, 2]. The answer is [2, 3, 1] since it is lexicographically smaller than [3, 1, 2].

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by NeverSayNever (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody please explain me solution to this problem ?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me with this please ?

→ Reply
»
8 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

We say that if the answer is in this sort:

And you can easily proov it.

Otherwise the answer is -1.because the number that we can put in the position 1 to are greater than and the number that we can put in the position to are less than . So we can't put any number in position .

So the problem completely solved.

→ Reply