[Solution] Different Medians solution codechef

Different Medians solution codechef – Chef is given an integer N. Chef wants to construct a permutation A = [A_1, A_2, \ldots, A_N] of \{1, 2, 3, \ldots, N \} that satisfies the following condition:

  • Let P_i denote the prefix of A of length i, i.e, P_i = [A_1, A_2, \ldots, A_i]. Then, for every 1 \leq i \lt N, it must hold that \text{median}(P_i) \neq \text{median}(P_{i+1})

Table of Contents

[Solution] Different Medians solution codechef

Help Chef find such a permutation A. If multiple answers exist, you may print any of them.

Note: The median of an array is defined as follows:

  • Let A be an (1-indexed) array of length N. Let B be the array obtained by sorting A. Then \text{median}(A) is defined to be B_{\left\lceil \frac{N}{2}\right\rceil}. For example, \text{median}(\{3, 1, 2\}) = 2, and \text{median}(\{3, 4, 1, 2\}) = 2

Input Format

  • The first line of input will contain a single integer T, denoting the number of test cases.
  • The first and only line of each test case contains a single integer N.

Output Format

For each test case, output the required permutation. If multiple answers are possible, you may print any of them.

[Solution] Different Medians solution codechef

  • 1 \leq T \leq 30
  • 2 \leq N \leq 1000
  • The sum of N over all test cases won’t exceed 1000.

Sample 1:

Input

Output

2
2
3
2 1
2 1 3

Different Medians solution codechef Explanation:

Test case 1: The prefixes of the given permutation are [2] and [2, 1], with medians 2 and 1 respectively.

Test case 2: The prefixes of the given permutation are [2] (with median 2), [2, 1] (with median 1), and [2, 1, 3] (with median 2). No two adjacent medians are equal.

For Solution

“Click Here”

Leave a Comment