Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### beginner_boy's blog

By beginner_boy, history, 14 months ago, ,

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

• +8

 » 14 months ago, # |   0 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).
•  » » 14 months ago, # ^ |   +14 well, if was accepted, it must be right rsrs, thanks
 » 14 months ago, # | ← Rev. 2 →   +47 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.
•  » » 14 months ago, # ^ |   +6 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.
•  » » » 14 months ago, # ^ |   +14 Smells like Integer LP, which is NP complete!
•  » » » » 14 months ago, # ^ |   +6 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.