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

Before contest

Forethought Future Cup - Elimination Round

20:38:56

Register now »

Forethought Future Cup - Elimination Round

20:38:56

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | tourist | 3628 |

2 | Um_nik | 3534 |

3 | Petr | 3341 |

4 | wxhtxdy | 3329 |

5 | ecnerwala | 3305 |

6 | LHiC | 3300 |

7 | mnbvmar | 3291 |

8 | sunset | 3278 |

9 | V--o_o--V | 3275 |

10 | dotorya | 3188 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 188 |

2 | Errichto | 183 |

3 | rng_58 | 161 |

4 | PikMike | 159 |

5 | Petr | 157 |

6 | Vovuh | 156 |

7 | Ashishgup | 153 |

8 | 300iq | 151 |

9 | Um_nik | 149 |

10 | majk | 148 |

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

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/20/2019 00:26:05 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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).

well, if was accepted, it must be right rsrs, thanks

Here is a solution. The key observation is that if

x=max_{i}a[i], thenxcan be only be paired with one other number: 2^{k}-x, wherekis minimal so that 2^{k}>x. This makes a greedy algorithm clear: sorta[0] < ... <a[n- 1]. Now go from the top. When I am processinga[i], if 2^{k}-a[i] is still in the set, I match it. Otherwise, I continue.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.

Smells like Integer LP, which is NP complete!

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.