NANDXOR - Editorial

PROBLEM LINK:

Contest - Division 3
Contest - Division 2
Contest - Division 1

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Bruteforce, Pigeon Hole Principle

PROBLEM:

Given an array A of N elements, determine 4 distinct indices i,j,k,l such that \text{popcount}(A_i\oplus A_j) = \text{popcount}(A_k\oplus A_l).

EXPLANATION:

Observation: There are atmost 30 different values of \text{popcount}(A_i\oplus A_j) over all valid pairs i,j.

By the above observation, it is immediately follows by Pigeon Hole Principle that, if we were to make 31 pairs (using elements of A), there would be atleast 2 pairs with the same \text{popcount}.

Thus, when there are \ge 62 elements in A, an answer always exists; a valid tuple of indices can be found by creating 31 pairs from A and comparing the popcount of each of the pairs till 2 pairs with the same popcount are found.

When there are < 62 elements in A, an O(N^4) bruteforce that tries all valid tuples (i,j,k,l) suffices to find the answer under the given constraints.

TIME COMPLEXITY:

O(N^4)

when N \le 62, and

O(1)

otherwise, per test case.

SOLUTIONS:

Editorialist’s solution can be found here
Author’s solution can be found here


Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)

  • 1
  • 2
  • 3
  • 4
  • 5

0 voters

4 Likes

Nice O(63^4) solution !! Had me by surprise

But can you give a counter case to my O(1500*1500) solution : link : Solution: 59762837 | CodeChef

1 Like

Can someone explain my my solution is failing, I bruteforced all possible indexes for first min(n,99) elements of the given array in O(99^4)
Solution: 59746677 | CodeChef

Edit: Got it (just pruning for making execution time even less)

And I won’t submit because of TC :upside_down_face:

1 Like

How does 62^4 for each test case work? Total complexity over all cases would be more than 1e11

7 Likes

Author solution does it in 8^4 per test case? How to prove that works?

1 Like

8^4 = 4096
There are max 10^4 test cases
Time complexity = 4096 * 10^4 = 4.096 * 10^7

It easily executes under time limit of 1s.

How to prove 8^4 approach works. How to prove answer always exists when more than 8 elements are present?
Editorial says 62^4

1 Like

If there are 1e4 test cases each with n = 60, shouldn’t it give TLE in the O(n^4) solution?

5 Likes

A simple n^4 solution works. Such weak test cases . Admins should atleast check testcases before sending questions for contest , i loved the piegonhole idea but the fact that a simple n^4 is accepted kills the problem for me.

2 Likes

you require 31 pairs ? Then why 62 ?

i,j,k,l ---- all are different.

6x5 + 4x3 = 42 >= 31.

So length 6 will work !!

Because C(8, 4) = 70, means 70 sets for 4 indices exists if n = 8, which is greater than 62 hence we can be sure that popcount(xor) will repeat.

1 Like

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

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

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

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

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

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

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

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

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