[Solution] Sorting Array CodeChef Solution | CodeChef Problem Solution 2022

[Solution] Sorting Array CodeChef Solution | CodeChef Problem Solution 2022

Given an array A$A$ of length N$N$.

You are allowed to perform the following operation on the array A$A$ atmost 20$20$ times:

• Select a non-empty http://subsequence S$S$ of the array [1,2,3,…,N]$[1,2,3,\dots ,N]$ and an integer X$X$ (0≤X≤106)$(0\le X\le {10}^6)$;
• Change Ai$A_i$ to Ai+X$A_i+X$ for all i∈S$i\in S$.

You have to sort the array A$A$ in strictly increasing order by performing atmost 20$20$ operations.

It is guaranteed that we can always sort the array A$A$ under given constraints.

Input Format

• The first line of input contains a single integer T$T$, denoting the number of test cases. The description of T$T$ test cases follow.

Solution Click Below:-  CLICK HERE

• The first line of each test case contains an integer N$N$ - the length of the array.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ representing the initial array A$A$.

Output Format

For each test case print (2⋅Q+1)$(2\cdot Q+1)$ lines. Here Q$Q$ denotes the number of operations you performed to sort the array A$A$. Note that, Q$Q$ must be less than or equal to 20$20$. For each test case,

Age Limit Codechef Solution

Equal Distribution Codechef Solution

Minimum number of Flips CodeChef Solution

Divisible by 3 CodeChef Solution

How Many Maximums CodeChef Solution

Minimum or Maximum CodeChef Solution 

Maximise Set Bits CodeChef Solution

Sorting Array CodeChef Solution

Construct An Array CodeChef Solution

• In the first line, print Q$Q$, the number of operations you perform.
• Then, print 2⋅Q$2\cdot Q$ lines. The (2⋅i−1)th$(2\cdot i-1{)}^{th}$ and (2⋅i)th$(2\cdot i{)}^{th}$ of these lines denote the ith$i^{th}$ (1≤i≤Q)$(1\le i\le Q)$ operation.

To describe the ith$i^{th}$ operation, print two space-separated integers Ki(1≤Ki≤N)$K_i(1\le K_i\le N)$ and Xi(0≤Xi≤106)$X_i(0\le X_i\le {10}^6)$ on (2⋅i−1)th$(2\cdot i-1{)}^{th}$ line and print Ki$K_i$ space-separated integers describing subsequence Si$S_i$ on (2⋅i)th$(2\cdot i{)}^{th}$ line.

Constraints

• 1≤T≤5⋅104$1\le T\le 5\cdot {10}^4$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤Ai≤105$1\le A_i\le {10}^5$
• Sum of N$N$ over all test cases does not exceed 105${10}^5$.