NANDXOR - Editorial

well I think he uses 8 elements because he is taking all tuples of size 4 from 8 elements so that makes 8C4 = 70 tuples. Which is well above 62. This is why that works

its remaining the same ; WA .

Got it! Thanks

Well, i think the answer always exists when there are strictly more than 5 elements in array. This is because, if there are n elements in array, then there can be atmost 3choose(n,4) distinct pairs ({a,b} , {c,d}). There are only 31 distinct popcounts at Max, (from 0 to 30). So the smallest integer n, satisfying 3choose(n,4) >31 is what we’re looking for. It’s 6. So any array having 6 or more elements will always have an answer.

My solution which assumed 6 was enough fails, whereas switching it to testing first 8 passed, although I derived it the same way you did. I’d like the author to elaborate on this topic if possible. Thanks :slight_smile:

Please help me to understand this:

I understand this part (please correct me if I am wrong):
unique number of pairs can be 30 or 31 since the bits are from 0 to 30. So, according to pigeon hole if we have pair greater than 31 then that part will repeat itself.

if N>=62 elements there always be repeated pop-count pairs.
if N<62 elements there may be repeated pop-counts pairs.

Why in loop(iterations) we are using min(8,n) ?

Can any on explain how some people getting answer in min(n,34)??

This problem felt very similar to Problem - A - Codeforces
The time complexity is elusive.

Bro i cant able to find any reason why it giving wrong answer.
This is code with taking n=min(n,1500) and it passes easily

can anyone tell me how get good in this cuz i didn’t undwestand a single thing . ;-;

Though 70 might guarantee that there will be repeated xor values for the pairs, what guarantees that the repeated xor values will occur for disjoint pairs?

In other words, how can you say that the repeated xor values will occur in the same tuple?

1 Like

thanks bro , a mail just arrived saying my solution is correct ; and rating is updated according to that