LENTMO - EDITORIAL

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 ?

I am finding it hard to understand.
What I understood is :

after i operations we have y elements xored with x.

( Does it mean that those y elements are different and no element is xored twice ? )

Now, in next operation we assume we take z elements among which y xored with x and rest which are not xored

( what does z elements mean? Is z equal to n ?)

Now, in next operation we assume we take z elements among which y xored with xx and rest which are not xored. So finally number of elements xored with x will be y−z+k−z which is y+k-2*z which is even.

( I get that those y elements that are already xored will be reset to their original value.
I could not understand how the final number of xored elements will be y-z+k-z
Can you please explain it a bit more? )

it is bit different . you haven’t consider the cases when

Case a: k is even;
Case b: k is odd.
as mentioned in editorial

Thanks!. there was a typo. Also I tried to make it more clear in the editorial . Let me know if any issues there.

can you provide some more test cases.I don’t know why I am getting it wrong

@cenation092 Your video solution was awesome and you did a great work can you please clear the last case (M is odd and K is even) which you explained in video a little bit more as its not cleared to me … :slight_smile:

Can anyone please help me find error in my code. I am getting only 10 points, Here is my code

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

@vinayagarwal_4 It doesn’t matter what the value of k is. What matters is that whether k is even or odd.We don’t need to XOR k elements together .We can XOR individual elements if k is odd and pairs if k is even( as explained in the editorial).
In our case we stop when our sum of k XORs becomes negative. The sum might comprise of elements which give positive rise but it isn’t enough to make the overall sum positive. This is the mistake those positive rise elements could have also been XORed using the technique in the editorial.

1 Like

Okayy, got it. Thanks.

HOW DID WE DO THIS AS WE CAN SELECT ONLY K ELEMENTS?(what if k=n-1 and odd)