LENTMO - EDITORIAL

0 0 0 1 1 1
//doing first time
1 1 1 0 0 1
//doing second time
0 0 0 1 0 0
// doing third time
1 1 1 1 1 1

1 Like

As k is odd you can individually xor any element you wish. So u can xor all zeros and leave ones. Hence the ans becomes 6.

I get my mistake now. Taking K at a time I was missing positive rise elements (if the sum was negative) which could have been xored using the techniques of the editorialist.

well I have the O(n) solution look at this…

https://www.codechef.com/viewsolution/24628476

my approach Codechef JUNE Challenge 2019 | Lent Money | LENTMO - YouTube in O(N)

3 Likes

According to case b we proved that a single xor can be obtained(is it possible to xor with single bag and leave rest as it is).But how to prove that we can xor with any number of bags if k is odd ? In other words - suppose n = 20 , k =3 , then how to prove that we can xor with 1 or 2 or 3 … or 20 bags and leaving rest as it is.If i missed something in editorial please tell .

3 Likes

can you please explain the second case when k is odd

1 Like

I used the same logic but got WA cuz i missed out a corner case :expressionless:

2 Likes

Test case 2
(others cases as you mentioned)
a[i] is 0 or 1
x = 1
k<n
so our question will be a sequence of 0s and 1s
z = no. of zeroes
if(k is odd or zeroes is even)
ans = n
else
ans = n-1

For other test cases
let a[i] be some element
make a new array p
p[i][0] is a[i] and p[i][1] is a[i]^x if a[i]<a[i]^x
else
p[i][1] is a[i] and p[i][0] is a[i]^x
(denoting lower element with 0 and higher with 1 :))
gs += p[i][1] for all i
for the ans n case gs is the ans
for the n-1 case loop for every i and find max of
gs - p[i][1] + p[i][0]
O(n) solution :slight_smile:

Nice editorial
:slight_smile:

1 Like

case b: for k is odd how is he doing xor for k+1 and then xoring k in next step

2 Likes
    #include<iostream>
    #include<stdio.h>
    #include<vector>
    #include <stack>
    #include <bits/stdc++.h>

    #define rep(i,n) for(int i=0;i<n;i++)
    #define repA(i,a,n) for(int i=a;i<=n;i++)
    #define repD(i,a,n) for(int i=a;i>=n;i--)
    #define ll long long int
    #define fi first
    #define se second

    using namespace std;

    int main()
    {
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    	int t;cin>>t;
    	while(t--)
    	{
    		int n;cin>>n;
    		ll a[n],ch=0;
    		rep(i,n) cin>>a[i];
    		rep(i,n) ch+=a[i];// sum of all elements
    		int k,x;cin>>k>>x;

    		int ct=0;
    		ll b[n];
    		rep(i,n)
    		{
    			b[i]=((a[i])^x)-a[i];
    			if(b[i]>0) ct++;// counts the number which are increasing after taking XOR
    		}

    		sort(b,b+n);
    		int end=n-1,j=0;
    		while(j<ct)
    		{
    			ch+=b[end-j];
    			if(j!=ct-1) b[end-j]=b[end-j]*(-1);
    			j++;
    		}
    		sort(b,b+n);

    		if((ct%2==0) || (ct%2 && k%2))  /* if ct is EVEN and if both ct & k are ODD, we can take all increasing XOR*/
    			printf("%lld\n",ch);
    		else
    		{
    			if(b[end]+b[end-1]>0) ch=ch+b[end-1];
    			else ch=ch-b[end];
    			printf("%lld\n",ch);
    		}
    	}
    	return 0;
    }

Please help, why my code is not passing all the test cases?
I am storing the change in number after taking its XOR. If no of positive change is even then we can take all the numbers, also if both no of positive changes & ‘k’ is odd we can take all the numbers.
In rest of the cases which will take (total no of positive changes) - 1 or we can also take the one remaining positive change + smallest negative change such that there sum is positive.
Thanks in advance.

I did something similar, how did you overcome it? Can you explain in a little more detail?

I used same logic but there is something wrong in my code can you tell me where I am wrong. Here is my code: https://www.codechef.com/viewsolution/24877754

Hi, I guess you missed few cases. suppose n=k=3 and first two elements of vec are positive while the third is negative. As per your code, you will pick first two and not the last, but actually you will have to pick all the three as you have no choice.
Correct me if I am wrong.

But in editorial @teja349 He prove that we can take two elements instead of k elements.
SO that I take two elements each time.

Check case 1, what you say is when k<n. :smile:

how is that different from what they have? Even while using greedy you have to keep in mind that then number of increments (due to v[i] ^ x - v[i]) can only be even when K is even and anything when K is odd? And the editorial also states the same thing, of taking only those values which result in a positive change when xor-ed?

Ok I got it Thanks for pointing out.

1 Like

I didn’t understand. Can you please explain more ?