[Solution] Different Medians CodeChef Solution

Problem

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})$

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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

• 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.

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.