Hail XOR December codechef challenge problem solution 2020

 Hail XOR  December codechef challenge problem solution 2020-

Hail XOR problem is taken from December codechef challenge 2020. Let's read problem statement.

You are given a sequence A1,A2,…,AN$A_1,A_2,\dots ,A_N$ and you have to perform the following operation exactly X$X$ times:

• Choose two integers i$i$ and j$j$ such that 1≤i<j≤N$1\le i<j\le N$.
• Choose a non-negative integer p$p$.
• Change Ai$A_i$ to Ai⊕2p$A_i\oplus 2^p$, and change Aj$A_j$ to Aj⊕2p$A_j\oplus 2^p$, where ⊕$\oplus$ denotes bitwise XOR.

Find the lexicographically smallest sequence which can be obtained by performing this operation exactly X$X$ times.

A sequence B1,B2,…,BN$B_1,B_2,\dots ,B_N$ is said to be lexicographically smaller than a sequence C1,C2,…,CN$C_1,C_2,\dots ,C_N$ if there is an index i$i$ such that Bi<Ci$B_i<C_i$ and for each valid j<i$j<i$, Bj=Cj$B_j=C_j$.

Input

• The first line of the input contains a single integer T$T$ denoting the number of test cases. The description of T$T$ test cases follows.
• The first line of each test case contains two space-separated integers N$N$ and X$X$.
• The second line contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$.

Output

For each test case, print a single line containing N$N$ space-separated integers ― the lexicographically smallest obtainable sequence.

Constraints

• 1≤T≤10$1\le T\le 10$
• 2≤N≤105$2\le N\le {10}^5$
• 1≤X≤109$1\le X\le {10}^9$
• 1≤Ai≤109$1\le A_i\le {10}^9$ for each valid i$i$

Subtasks

Subtask #1 (30 points): N≤100$N\le 100$

Subtask #2 (70 points): original constraints

Example Input

1
3 3
2 2 3

Example Output

0 0 3

Explanation

Example case 1: The original sequence is (2,2,3)$(2,2,3)$. Consider the following three operations:

• Choose i=1$i=1$, j=2$j=2$ and p=1$p=1$. Then, A1$A_1$ changes from 2$2$ to 2⊕21=0$2\oplus 2^1=0$ and similarly, A2$A_2$ changes from 2$2$ to 2⊕21=0$2\oplus 2^1=0$. Now the sequence is (0,0,3)$(0,0,3)$.
• Next, choose i=1$i=1$, j=2$j=2$ and p=1$p=1$. Then, A1$A_1$ changes to 0⊕21=2$0\oplus 2^1=2$ and A2$A_2$ changes to 0⊕21=2$0\oplus 2^1=2$. The sequence is (2,2,3)$(2,2,3)$.
• Next, again choose i=1$i=1$, j=2$j=2$ and p=1$p=1$. Then, A1$A_1$ changes to 2⊕21=0$2\oplus 2^1=0$ and A2$A_2$ changes to 2⊕21=0$2\oplus 2^1=0$. The sequence is (0,0,3)$(0,0,3)$ again.

We can check that after exactly 3 operations, this is the lexicographically smallest sequence we can obtain.

Solution -

hint- You have to iterate n time not x time.

Actually Hail XOR is easy-medium level question of this contest.You it's is pretty easy once you get 1 test case and general approach 

to solve this question. As i told you in hint that you have to iterate n time not x time so we will first iterate through the array 

and we will try to reduce ith element as small as possible in one operation. We can reduce current element 2^(msb) most significant bit.

so we will reduct ith elemet a[i] XOR 2^(msb) and for jth element we will iterate from i+1 elment to n and we found any element witch 

gives smaller value when we do XOR this number with 2^msb we select that element and reduct a[j]=a[j] XOR 2^(msb)

if we do not find such element we will choose last element as jth element.

we will not increment i until a[i] become zero or total operation become zero.

in next time we will search for next msb of ith element. and reapeat same process until a[i] become zero.

for msb i have written a function which return all set bit position in curr element.

after i reach to n-1 ans still some operation left we can achive same squence if n is not equal to 2.

Special case-

if(remainng operation is odd and n==2){

 if(x>0){

            if(x%2!=0&&n==2){

                v[1]=1;

                v[2]=v[2]^1;

        }

       

       }

}

finally we print the array.

Here is my solution.

Join Telegram Channel for More Editorial. 

link -https://t.me/competitiveProgrammingDiscussion