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 \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 = \lfloor P/2 \rfloor + 1}^P f(N, i).

Time Complexity: \mathcal{O}(NP)

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

\displaystyle \left(\sum_{i=1}^N \left(\left\lfloor \frac{v_i}{2} \right\rfloor + 1\right)\right) - dp\left[\left\lfloor \frac{\sum_{i=1}^N p_i}{2} \right\rfloor + 1\right]


Comments

There are no comments at the moment.