help plz

[lame]

We have been given an array of size n , and two integers k and x;
Now, We can perform the following operation any number of times (including zero):
1.Pick exactly k elements from array.
2.Xor the k chosen elements with x in the array.

Each element may be picked any number of times in different operations.

We have to find maximum sum of array we can have at the end if we perform the operations optimally.

Please help me out in these guys.
I have absolutely no clue.

[jonnin]

what does xor do to a number's value?
its a fancy bit-flipper. So you want to flip high order bits from 0 to 1. as many as you can without making numbers smaller.
but there is a monkey wrench: they are integers you said, not unsigned integers, so some bit flips will make negative numbers which will decrease your sum. You want to avoid that as well.

[lame]

@joinin only positive integers.

and how can we find out how many I have to perform the operations?

[notacoder]

the numbers are unsigned integers

[notacoder]

https://www.codechef.com/JUNE19B/problems/LENTMO
here is the link to question for better comprehension

[lame]

anybody knows the approach?
for partial?

[jonnin]

again, its a bit flipper. ignoring negatives now, its still the same... just easier.
sort the input. while your xor flips high order bits for more than 50% of the next K, do it. unclear to me, do you resort and repeat or proceed until the while exits, then resort and repeat until the first K can't be improved? Are these integers bucket sortable (that tends to beat std::sort)? If not, is a 'already almost sorted' algorithm faster (eg shell sort is faster the closer arrays are to already sorted)? something like this? Tweaking the sort is optional as it takes unusual data to beat std::sort. Its really only worth it if you can bucket, because that gives you lift twice for repeats (repeated values check once for xor better is more efficient as it can skip the duplicates easier).

[lazybot]

If anybody have good test cases, please tell.

[lame]

I have wrote my code , but it is giving WA.
Can anyone provide some test cases.

[Dum]

@lame
I think this case might help you

5
16 20 11 11 11
4
11

output : 91

[theKlaw]

@Dum, can you explain how this gives 91?
like each step

[Dum]

@theKlaw
sure.
step - 1 : (16 ^ 11) ( 20) (11 ^ 11) (11 ^ 11) (11 ^ 11)
27 20 0 0 0

step - 2 : (27) (20 ^ 11) (0 ^ 11) (0 ^11) (0 ^ 11)
27 31 11 11 11

27 + 31 + 11 + 11 + 11 = 91

[Dum]

@hdude0164
if you need testcases i will give but i can't share my code

[Dum]

Guys,
Daily limit of my PM is exceeded so i can't reply through PM

@abc123xyz
replace this with

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

typedef __int128_t ll;

this

#include <bits/stdc++.h>
using namespace std;
#include <boost/multiprecision/cpp_int.hpp>
using namespace boost::multiprecision;

typedef int128_t ll;

[kanken]

@Dum, what is the concept you are applying to get 100 points ?
Any small hint would also be appreciated or even if you could drop a direction to approach,
Thanks !

[despo]

yes....help us finding the pattern

[Dum]

@despo
this is not a pattern question.

[lame]

@Dum small hint plz

[Dum]

@maxdaen
from given n and k try to find the minimum number of values you can xor with

[kanken]

@Dum, I didnt get you, pardon me.
If you dont mind , could you please explain you point with a little example, if possible.
Thanks.