Adjacent Sum Greater than K

3.2

11 votes
, Greedy algorithm, Linear Search, Algorithms, Observation
Problem

A permutation of length \(N\) is an array of \(N\) integers such that every integer from \(1\) to \(N\) appears exactly once. For example, \([2, 3, 5, 4, 1] \) is a permutation of length \(5\), while \([1,2, 2], [4, 5, 1, 3] \) are not permutations.

You are given two integers \(N,K\). Find a permutation \(P\) of length \(N\) such that \(P_i + P_{i+1} \ge K\) for each \(1\le i \lt N\). If there are multiple permutations find the lexicographically smallest one. Print \(-1\) if no such permutation exists.

A permutation \(P\) is lexicographically smaller than a permutation \(Q\) of the same length \(N\) if there exists an index \(1\le i \le N\) such that \(P_1 = Q_1, P_2 = Q_2, \dots\) and \(P_i \lt Q_i\).

Input format

  • The first line of input contains an integer \(T\) denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains two integers \(N,K.\)

Output format

For each test case, print \(-1\) if no suitable permutation exists, otherwise print the lexicographically smallest permutation satisfying the conditions.

Constraints

\(1\le T \le 10^5 \\ 2 \leq N \le 3\cdot 10^5\\ 1\le K \le 2 \cdot N\\ \text{Sum of $N$ over all test cases does not exceed }3\cdot 10^5.\)

Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
  •  In the first test case, there are multiple permutations of length \(6\) which satisfy the given condition for \(K = 5\), for example\([3, 5, 1, 4, 2, 6], [1, 5, 2, 3, 4, 6], [6, 1, 4, 3, 2, 5]\)etc. \([1, 4, 2, 3, 5, 6 ]\) is the lexicographically smallest permutation among them.
  • In the second test case, there is no permutation of length \(4\) that satisfies the given condition for \(K = 6.\) 

 

 

Editor Image

?