Given an array A of N elements, determine 4distinct 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)
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)
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.
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