beginner_boy's blog

How to solve AtCoderGrandContest029 — Power of Two ?
By beginner_boy, history, 6 years ago, In English

Hello, someone can explain how to solve this problem from today contest in AtCoder?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved it with 2 greedy algorithms: pair up the numbers from lowest to highest power of 2 and from highest to lowest power of 2. Taking the best answer of these 2 algorithms passes the tests, not sure if it is correct. I have a feeling this isn't correct but can't find a counterexample (I also didn't think too hard about it).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +47 Vote: I do not like it

Here is a solution. The key observation is that if x = maxia[i], then x can be only be paired with one other number: 2k - x, where k is minimal so that 2k > x. This makes a greedy algorithm clear: sort a[0] < ... < a[n - 1]. Now go from the top. When I am processing a[i], if 2k - a[i] is still in the set, I match it. Otherwise, I continue.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I wish I had noticed that during the contest. I spent most the contest trying to get my max flow solution that uses index compression and grouping all terms with the same value into a single node to work. Dinic's is fast enough but I couldn't figure out a good way to represent the case where two terms with the same value get paired with each other. So I passed all the test cases except 1. I need some sort of flow network where there are certain edges which only allow even quantities of flow to pass through.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Smells like Integer LP, which is NP complete!

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Thanks for pointing that out. Now I know it is probably not a good idea to try to modify max flow algorithms to handle these new types of edges.

        → Reply