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 the 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]$$