There are N integers, in range [0, M).
Select 2 distinct integers (p and q) from them, and maximize:
1. p OR q
2. p AND q
3. p XOR q
4. p NOR q
NOTE: M can be very large, so please take simple operating into efficient consideration. i.e. It takes O(logM) time to compute (p OR q)
Can anyone come out with solutions less than O(N^2logM) ?
Select 2 distinct integers (p and q) from them, and maximize:
1. p OR q
2. p AND q
3. p XOR q
4. p NOR q
NOTE: M can be very large, so please take simple operating into efficient consideration. i.e. It takes O(logM) time to compute (p OR q)
Can anyone come out with solutions less than O(N^2logM) ?
N non-negative integers are given in binary code.
We can use a prefix tree (Trie) to solve case 3. (USACO Training 6.1.3 Cow XOR)
O(NlogM)
In case 4 we can sort the integers, and the max NOR value must be from two adjacent integers.
O(Nlog2M) using quick sort..