hpfdf's blog

Some interesting problems
By hpfdf, 14 years ago, In English
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) ?
  • Vote: I like it
  • +1
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
= =......这不会是作业题吧。。。
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
For case 1 (p OR q), it is sufficient to take X-1 and X where X is the greatest possible power of two: X=2^k such that 2^k < M <= 2^(k+1). It takes O (log M) time (linear in the number of bits) to construct such numbers.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I guess you misread the problem statement. We have N numbers from [0,M). Otherwise, all 4 functions can be maximized easily in O(log M).
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yeah, right, I had better gone back to sleep :) .
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Thx for your idea.

    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..
    → Reply