Neo-Robin Hood#12846

Neo-Robin Hood (Editorial)

Authors: Daniel Posdărăscu

Lucian Bicsi

Solved by:

First to solve: KhNURE_Energy is not over

Let's start by sorting the politicians decreasingly on their wealth. It is not hard to argue that, for any fixed set of "helped" politicians, it is always optimal to rob the richest remaining politicians. Let's binary search on the answer , and do the following approach:

Let's consider the -th politician (in sorted order) is the least expensive politician that we decide to rob. Naturally, it must be the case than i \geq k. Then, we will have to steal from of the politicians in the left part , help the other i-k get political influence, and then also choose some extra 2k-i politicians in the right part to help, in order to cover up for all of our thefts. But which politicians to choose?

From the right part, it's easy: just choose the 2k-i politicians with lowest p_j values. From the left part, we have to assess the gain from deciding to steal from a politician, instead of helping him. This gain turns out to be p_j+m_j for all politicians in the left part, as Neo-Robin Hood will save m_j dollars from not helping the politician, as well as p_j dollars from stealing from it.

From here on, the solution should be clear: for all i \geq k, we try to pick the smallest 2k-i p_j values in the right part, and the biggest p_j+m_j values in the left part. If we can satisfy these politicians for some k \leq i \leq 2k (the money that we steal from is assured), then we can conclude that the answer is at least .

Dynamically keeping the largest p_j+m_j values and the largest 2k-i m_j values can be easily computed using two separate passes, and priority queues in O(\log n). More involved solutions (using binary search on treaps/Fenwick trees) are also possible.

Total complexity is O(n \log^2 n).