-->

12/8/20

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 and you have to perform the following operation exactly X times:

  • Choose two integers i and j such that 1i<jN.
  • Choose a non-negative integer p.
  • Change Ai to Ai2p, and change Aj to Aj2p, where  denotes bitwise XOR.

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

A sequence B1,B2,,BN is said to be lexicographically smaller than a sequence C1,C2,,CN if there is an index i such that Bi<Ci and for each valid j<iBj=Cj.

Input

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

Output

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

Constraints

  • 1T10
  • 2N105
  • 1X109
  • 1Ai109 for each valid i

Subtasks

Subtask #1 (30 points): N100

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). Consider the following three operations:

  • Choose i=1j=2 and p=1. Then, A1 changes from 2 to 221=0 and similarly, A2 changes from 2 to 221=0. Now the sequence is (0,0,3).
  • Next, choose i=1j=2 and p=1. Then, A1 changes to 021=2 and A2 changes to 021=2. The sequence is (2,2,3).
  • Next, again choose i=1j=2 and p=1. Then, A1 changes to 221=0 and A2 changes to 221=0. The sequence is (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. 





Advertiser

all right reserved @technicalkeeda.in. Powered by Blogger.