Click here to Skip to main content
15,071,637 members
Please Sign up or sign in to vote.
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
Comments
Patrice T 6-Dec-20 4:31am
   
Show what you have done

1 solution

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])
   
Comments
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.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900