-3

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 1≤i<j≤N.
  • Choose a non-negative integer p.
  • Change Ai to Ai⊕2p, and change Aj to Aj⊕2p, where ⊕ denotes bitwise XOR.

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

A copy of the question can be https://www.codechef.com/DEC20B/problems/HXOR

Approach:

Here, we are dealing with N integers for X times operations, we are performing the xor function for all integers in an array with the power of 2 elements (2^p), p represents the non -ve integer.

For finding lexicographically smallest sequence, we are doing xor of each element until it becomes smallest and then we shift to the next element. Meanwhile, we also store the elements used in the previous steps to make pairs.

Test Case:

Input:

4 3

2 2 3 3

Output:

0 0 0 0

#include <bits/stdc++.h>

using namespace std;

#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

#define ll long long

#define pb push_back


ll bs(vector<ll> check, ll key){
    ll n = check.size();
    for(ll i=0; i<n; i++)
    {
        if(check[i]==key)
        {
            return i;
        }
    }

    return -1;
}

ll highestPowerof2(ll n)
{
   ll p = (ll)log2(n);
   return (ll)pow(2, p);
}

void smallestSequence()
{
    ll t;
    cin >> t;
    while(t--)
    {
        ll n,x;
        cin >> n >> x;
        ll a[n];
        for(ll i=0;i<n;i++)
        {
            cin >> a[i];
        }

        if(n==2)
        {
            for(int i=1; i<n; i++)
            {
                a[i]^=a[0];
            }
            a[0]=0;

            if(x%2==0)
            {
                a[0]^=1;
                for(int i=1; i<n; i++)
                {
                    a[i]^=1;
                }   
            }
            
            for(ll i=0;i<n;i++)
            {
                cout << a[i] <<" ";
            }
            cout << endl;
            continue;
        }
        ll temp = x;
        x = 2*x;

        vector <ll> check;
        ll i;
        ll flag=0;
        for(i=0;i<n;i++)
        {
            ll p=1;
            while(a[i]!=0 && x>0)
            {
                if(bs(check, highestPowerof2(a[i]))>=0)
                {
                    check.erase(check.begin()+ bs(check, highestPowerof2(a[i])));
                }
                else{
                    if(temp>0)
                    {
                        check.pb(highestPowerof2(a[i]));
                        temp--;
                    }else {
                        ll j = 0;
                        ll si = check.size();
                        for(j=0; j<si; j++)
                        {
                            ll res = check[j]^a[i];
                            if(res<=a[i])
                            {
                                a[i]^=check[j];
                                x--;
                                check.erase(check.begin()+j);
                                j--;
                                si--;
                            }
                        }
                        break;
                    }
                }
                a[i]^=highestPowerof2(a[i]);
                x--;
            }

            if(a[i]!=0)
            {
                flag=1;
            }
        }
        
        // if(flag==0 && temp>0 && (temp*2)==x)
        // {
        //  if(temp%2==1)
        //  {
        //      a[n-1]=a[n-2]=1;
        //  }
        // }

        while(x>=0 && !check.empty())
        {
            a[i-1]^=check[0];
            check.erase(check.begin());
        }

        for(ll i=0;i<n;i++)
        {
            cout << a[i] <<" ";
        }
        cout << endl;
    }
}


int main()
{
    fast;

    smallestSequence();

    return 0;
}

Suggestions will be appreciated! I had been trying for this problem for almost 5 days now, I don't want a solution, I just want to know some special TCs where my code is giving WAs.

Jerry Jeremiah
  • 9,045
  • 2
  • 23
  • 32
Lucifer
  • 1
  • Is is `2p` or `2^p` ? – Damien Dec 10 '20 at 20:16
  • 2
    I recommend decrypting your code. Don't use `pow` to get integer exponents. You will get errors because of [floating point imprecision](https://stackoverflow.com/questions/588004/is-floating-point-math-broken). Use bitshifting `1<< p` instead. For the same reason, `log2` may have strange results. – user4581301 Dec 10 '20 at 20:24
  • 1
    TCs that give WAs? Don't assume such abrreviations are common knowledge outside of coding contests, they aren't. I usually have test cases and they either fail or pass. – 463035818_is_not_an_ai Dec 10 '20 at 20:49
  • 2^p is the power of 2 integers, where p is a non-negative integer. @Damien – Lucifer Dec 11 '20 at 07:14
  • @i know. But you mention `2p` at the beginning of the post – Damien Dec 11 '20 at 07:35
  • This is a question in a still running contest. Not Cool. https://www.codechef.com/DEC20B/problems/HXOR – Atlantis Dec 13 '20 at 19:32
  • as said, don't use pow for integer powers. See [Why does gcc compiler output pow(10,2) as 99 not 100?](https://stackoverflow.com/q/25474351/995714), [Why does pow(n,2) return 24 when n=5, with my compiler and OS?](https://stackoverflow.com/q/25678481/995714). But especially for powers of 2 you should never use `pow` which is not only imprecise sometimes but also hundreds or thousands of time slower. Use `1 << p` to get 2^p – phuclv Dec 14 '20 at 08:57

1 Answers1

0

This is a on going contest. So this is the best i could help you.

Input:

1
4 4
1 2 3 4

Your output:

0 0 0 4

Right output:

0 0 1 5
Atul
  • 1
  • 2