NANDXOR - Editorial

editorial
, , , ,
15

each pair consist of distinct 2 elements .For 31 pair we require 62 elements

16

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

Can someone tell why this is failing? I bruteforced all tuples from 0 to min(n,71).

17

The whole point of the problem was to think of the way of getting (n^4) accepted. XD

18

this question is similar to this problem https://codeforces.com/problemset/problem/1500/A

19

There can be 10^4 testcases and if each of them has exactly 60 elements (10^4 * 60 < 10^6 as per the constraint), wouldn’t it take 10^4 * 60^4 which comes to around 10^11? This is before considering the time for popcount to run. Even if we consider that to be negligible, how does this solution not give TLE. Am I missing something?

And also it would be nice if the author/editorialist explained why the author’s solution uses just 8 and how that is sufficient @very_slow @infinitepro

1 Like
20

My solution is little bit different :slightly_smiling_face: https://www.codechef.com/viewsolution/59737167

21

bro u are only considering ({i,j},{k,l}) and leaving ({i,k},{l,j}),({i,l},{j,k}) :slightly_smiling_face:.

23

in second loop u forget to write min(1ll*1500,n).

24

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

25

its remaining the same ; WA .

26

Got it! Thanks

27

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.

28

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:

29

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.

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

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

30

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

31

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

32

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 https://www.codechef.com/viewsolution/59806310

33

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

34

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
35

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