PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: hyder1102
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
Find four indices i \lt j \lt k \lt l such that all these conditions hold:
- A_k \gt A_i\oplus A_j
- A_i \gt A_j \oplus A_k
- A_l \gt A_j \oplus A_k
- A_j \gt A_k \oplus A_l
EXPLANATION:
The inequalities may look kind of arbitrary at first glance, but intuitively one thing they tell us is that we want some pairwise bitwise XORs to be “small” compared to the chosen elements themselves.
In particular, observe that if all of A_i, A_j, A_k, A_l have the same highest set bit, then the four inequalities will trivially hold.
This is because, if the common highest set bit is b,
- Every pairwise XOR will eliminate b so only bits smaller than b will remain.
This means every pairwise XOR will have a value \lt 2^b - Every single element has b so its value is certainly \ge 2^b.
So, if we are able to find four elements with the same highest bit, we can simply output those four elements.
But what if we can’t?
Well, since the elements satisfy 0 \le A_i \lt 2^{20}, there are only 20 possible choices for what an element’s highest bit can be.
If each highest bit occurs fewer than 4 times, we can thus have at most 3\cdot 20 = 60 positive elements.
There is one caveat: the element 0 has no highest set bit, so it’s possible to have a long array with 60 positive elements and then a bunch of zeros.
However, observe that 0 is never a valid choice of element, since it cannot be strictly greater than the bitwise XOR of some pair of elements (and the inequalities require each element to be greater than some pairwise XOR.)
Thus, we can just ignore zeros in the array entirely - meaning that as soon as the array has at least 61 positive elements, a solution surely exists!
When the array has \le 60 positive elements, we can simply brute force all quadruples; the number of tests is small enough for this to work.
In fact, rather than having to implement the “find four elements with same highest bit” part separately, we can just adapt the brute force to solve the problem entirely - simply take the first 61 positive elements of the array and run a brute force on them.
With M = \min(N, 61) the number of operations is \binom{M}{4} = 5\cdot 10^5 at worst, so even with 100 tests this is fast enough.
It’s also possible to solve the problem with slightly better complexity.
Observe that after fixing the middle two elements (indices j and k), the choices of i and l are independent, because no inequality involves both.
So we can run one loop to find any valid i and another loop to find any valid l, rather than needing to nest these loops.
This shaves off a linear factor, and brings the number of operations down to about 7\cdot 10^4 per test at worst.
However, this wasn’t needed to get AC.
TIME COMPLEXITY:
\mathcal{O}(\min(N, 61)^4) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
pos = []
for i in range(n):
if a[i] > 0: pos.append(i)
if len(pos) > 60: break
n = len(pos)
done = 0
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
for l in range(k+1, n):
if done: continue
w, x, y, z = a[pos[i]], a[pos[j]], a[pos[k]], a[pos[l]]
if (w ^ x) >= y: continue
if w <= (x ^ y): continue
if z <= (x ^ y): continue
if x <= (y ^ z): continue
done = 1
print(pos[i]+1, pos[j]+1, pos[k]+1, pos[l]+1)
if not done: print(-1)