15,964,432 members
1.00/5 (1 vote)
See more:
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 1≤i<j≤N .Choose a non-negative integer p(could be 0) .Change Ai to Ai^pow(2,p), and change Aj to Aj^pow(2,p), where ^ denotes bitwise XOR.

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

Let us say the sequence is (2,2,3) . Consider the following three operations:

Choose i=1, j=2 and p=1. Then, A1 changes from 2 to 2@pow(2,1)=0 and similarly, A2 changes from 2 to 2^pow(2,1)=0. Now the sequence is (0,0,3) .

Next, choose i=1 , j=2 and p=1. Then, A1 changes to 0^pow(2,1)=2 and A2 changes to 0^pow(2,1)=2. The sequence is (2,2,3) . Next, again choose i=1 , j=2 and p=1. Then, A1 changes to 2^pow(2,1)=0 and A2 changes to 2^pow(2,1)=0. The sequence is (0,0,3) again.

hence after 3 operation (0,0,3) is the smallest lexicographically sequence we can get.

1≤T≤10

2≤N≤pow(10,5)

1≤X≤pow(10,9)

1≤Ai≤pow(10,9)

for each valid i

What I have tried:

Okay I have come up with a greedy approach. taking the highest active 1 in the first number note its position and then doing (1<<p) and then xoring the numbers which have 1 activated in this place by iterating to the rest numbers till my x becomes zero.

But obviously by looking at the constraints we can see that we need a better algo as it would give a tle.
Posted
Updated 7-Dec-20 10:52am
v2
Patrice T 6-Dec-20 4:31am
Show what you have done

## Solution 1

this is my solution, however this does not pass all the test case don't know why
plz help:

```import math
for i in range(int(input())):
N,X = map(int,input().split())
L = list(map(int,input().split()))

count = 0
curr = 0
while(curr<N-1 and count<X):
if(L[curr] == 0):
curr += 1
continue

temp = int(math.pow(2,int(math.log2(L[curr]))))

L[curr] = L[curr]^temp
for i in range(curr+1,N):
if(L[i]^temp < L[i]):
L[i] = L[i]^temp
break
if(i == N-1):
L[N-1] = L[N-1]^temp
count += 1

if(X>count):
if((X-count)%2!=0):
L[-2] = L[-2]^1
L[-1] = L[-1]^1
for i in range(N-1):
print(L[i],end=" ")
print(L[-1])```

Richard MacCutchan 7-Dec-20 16:07pm
And you expect us to guess what those test cases are, and which ones fail?
Richard Deeming 8-Dec-20 5:55am
"Here's some code that doesn't work" is not a solution to someone else's question.