Thanks to the many authors of this contest (all eight of them) for a great set of problems! I'll sketch out the solution ideas for a few of them here:
Let's assume our goal is to end the election with v votes and determine the minimum cost to do so.
First, we need to make sure every other party ends up with fewer than v votes. To do this, we should bribe enough people in every party to get them down to v - 1 votes or fewer. We can do this greedily by bribing the cheapest people in the party.
After that if we have v votes (or more), we are done. Otherwise, we should repeatedly bribe the cheapest voters remaining until we get to v. Note that we can do this in O(n) time rather than by using an O(n) selection algorithm such as nth_element, though this wasn't necessary to pass the problem.
Finally, simply loop over all possible values of v and take the minimum cost across all of them for an O(n2) solution.
In fact it is even possible to solve the problem in . Here is a solution using ternary search on v: 41534204
Let . Let's define the function d(i) = ai - ai + m. We are looking for i such that d(i) = 0. Notice that since |ai - ai + 1| = 1, d(i) - d(i + 1) must be - 2, 0, or 2.
First query for the value of d(1). If it is odd, then every d(i) is odd due to our property above, so the answer is - 1. Otherwise every value d(i) is even. Notice that d(m + 1) = am + 1 - a1 = - d(1). This means that one of d(1) and d(m + 1) is a positive even value, and the other is a negative even value. Since consecutive values can only differ by - 2, 0, or 2, there must be an index i in between 1 and m + 1 that satisfies d(i) = 0, and we can use binary search to find this index.
The obvious solution for this problem is O(n3), which can actually be squeezed in the time limit if you're careful; e.g., 41488961 and 41491248. However the real solution is , which I'll describe here:
Since the area of a triangle is , if we picked two of the n points as our base, we would know exactly what height we needed in order to make a triangle with the goal area. In particular, if we had our points sorted by distance to this segment, we could use binary search to determine whether or not there was such a point in time.
We can perform a rotational sweep on the set of points, which lets us set up this height-sorted list for every segment in order to solve the problem. (Imagine smoothly rotating the points clockwise, stopping whenever any two points are perfectly lined up horizontally.)
To do this we can take all n2 segments and sort them by angle. We also initialize our sorted list of points by y, breaking ties by x. We then iterate through our sorted segment list, swapping two points each time in order to maintain the height-sorted list. Finally we do two binary searches per segment to find if there are any points at the appropriate height (one above and one below).
Note that we can perform all these computations in integers only by using cross products. See the code below for details. Also, kudos to the problem writers for adding the guarantee that "no three cities lie on the same line," which helps keep the code cleaner without changing the key idea of the problem.
Unfortunately I don't know the solutions for C or E. If you do, leave a comment!