beginner_boy's blog

By beginner_boy, history, 4 months 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  

»
4 months 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).

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Smells like Integer LP, which is NP complete!

      • »
        »
        »
        »
        4 months 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.