Editorial for Wesley's Anger Contest 4 Problem 2 - Squirrel Election


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

Subtask 1

Since the number of votes needed to take any province is always the same, it's always optimal to take the provinces with greatest number of points.

Thus, a greedy solution suffices for this subtask.

Time Complexity: \mathcal{O}(N \cdot \log{N})

Subtask 2

Let C(i)= \left \lfloor{ \frac{v_i}{2}} \right \rfloor +1

Let P= \sum_{i=1}^N p_i

Let f(i, j) be the minimum cost needed to secure j points using the first i provinces. f(i, j) can be defined recursively as \min( f(i - 1, j), f(i - 1, j - p_i) + C(i) ) with a base case of f(0, 0) = 0.

The final answer is simply \min_{i= \left\lfloor{\frac{P}{2}} \right\rfloor + 1}^{P} f(N, i).

Time Complexity: \mathcal{O}(N \cdot P)

Another similar problem: Knapsack 2

It is also possible to blackbox the knapsack algorithm used in Knapsack 1 by having the value of the items be equal to \lfloor{}\frac{v_i}{2}\rfloor{} + 1 and the weight of the items equal p_i. The answer in this case is equal to (\sum_{i=1}^N (\lfloor{} \frac{v_i}{2} \rfloor{} +1)) - dp[\lfloor{}\frac{\sum_{i=1}^N p_i}{2}\rfloor{} + 1]


Comments

There are no comments at the moment.