Need a better algo...

Question

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 5-Dec-20 19:01pm

Christian Bale

Updated 7-Dec-20 10:52am

Chris Maunder772.9K

v2

Add a Solution

Comments

Patrice T 6-Dec-20 4:31am

Show what you have done

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

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

Member 15014657 · Answer 1 · 2020-12-07T08:44:00

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