HXOR - Editorial

editorial
, , ,
23

I think that the editorialist’s solution is not correct.
If I put in:
1
4 1
1 2 3 4
The output is:
0 2 2 4

However, a better solution is:
1 2 7 0

25

bro ou are considering output as a number, so consider them as strings so u will understand that string 0224 is <1270

26

Thanks for explaining it, that makes a lot more sense!

27

I think you were lucky. For the input
1
3 4
1 31 1
your code returns 0 0 31, but it should be 0 2 29 since there aren’t enough changes available to change both the first two numbers to 0.

28

still getting TLE…please help

int main()
{
    int t;
    cin>>t;
    
    while(t--)
    {
        long long int n,x,p=0;
        cin>>n>>x;
        
        long long int a[n];
        for(long long int i=0;i<n;i++)
            cin>>a[i];
        
        long long int index=0;
        while(x-- >0 && index < n-1)
        {
            
            p = log2(a[index]);
            long long int r = pow(2,p);
            a[index] = a[index]^r;
            
            long long int j = index+1;
            bool flag = false;
            while(j<n-1)
            {
                if(a[j] > (a[j]^r))
                {
                    a[j] = a[j]^r;
                    flag = true;
                    break;
                }
                j++;
                
            }
            if(!flag)
                a[n-1] = a[n-1]^r;
        }
        while(a[index] == 0)
                index++;
        if(x==1 || (x%2 != 0 && n<3))
        {
            a[-1] = a[-1]^1;
            a[-2] = a[-2]^1;
            
            
            
        }
        for(long long int i = 0;i<n;i++)
            cout<<a[i]<<" ";
    }
    return 0;
}`
29

Exactly, it didn’t made sense to me at that point of time and somehow there were no edgy test case to pin point such situation.

1 Like
30

can anyone please explain how the complexity of program is N.log(10^9) ?

31

can anyone please explain why my c program is working fine and java program is giving tle although structure of both programs are same only syntax is different?

32

My solution with explanation for corner case.

33

Use bitwise shift operation(<<) instead of power function. It takes lesser time.

34

but it is working in solution and in python…why is so

36

can anyone suggest me a testcase for which my program is showing WA?
link for my solution: CodeChef: Practical coding for everyone

Thanks

37

How is it possible to preserve the sequence when remaining operation is 1? I tried the editorial but it seems too heavy to understand.

1 Like
38

please reply to this anyone…

39

no its not possible then

40

watch the editorial video completely once.

41

Can anyone suggest me a testcase for which my program is showing WA ?
Link for my solution: https://www.codechef.com/viewsolution/40444499

Thanks in adVance to the responder…
please reply to my query…
And remember to SavE watEr…

42

in the text editorial it says that it can be preserved for N>=3 and a[i]=0;0<=i<=N-2

43

I have almost copied ur code…could you please tell me why am I getting TLE in one of the test cases and WA in another

#include
#include<bits/stdc++.h>
#include
using namespace std;

int main() {
int t = 0;
cin>>t;
while(t–)
{
int n,x;
cin>>n>>x;
int arr[n];
for(int i = 0;i<n;++i)
cin>>arr[i];
int index1 = 0,index2;
int bestxor;
while(x–)
{
bestxor = int(pow(2,int(log2(arr[index1]))));
for(int j = index1+1;j<n;++j)
{
if(arr[j]^bestxor<arr[j] && j<n-1)
{
index2 = j;
break;
}
else index2 = n-1;
}
arr[index1]^=bestxor;
arr[index2]^=bestxor;
while(arr[index1]==0 && (index1+1)<n)
index1++;
if(index1==n-1)
{
if(x==0) break;
else if(x&1 && n==2)
{
arr[index1-1]^=1;
arr[index1]^=1;
break;
}
else break;
}
}
for(int l = 0;l<n;++l)
cout<<arr[l]<<" “;
cout<<”\n";
}
return 0;
}

44

I tried your idea on n>2 and x>=n, and it worked!
Thanks a lot!