Problem link : contest
practice
Difficulty : hard
Pre-requisites : Meet in the middle, knapsack
Solution :
Assume that we consider that insteading of owing some powerhouses, we own money corresponding to them too. So we have money equal to initial money + money owned by your power houses.
Now notice K <= 31. Problem turns into a subproblem such that in each connected component, you need to take buy the cheapest powerhouse in it. So your problem turns into knapsack problem.
Here we have to maximize the profit (which is equal to population) and spend the money (equal to weight in knapsack). Simple knapsack algorithm won’t work here. We can make a simple observation that
K is small. Do a meet in the middle kind of approach. Divide the K bags(in knapsack) into K / 2 parts each. Compute all possible profit and weight values for each part in exponential 2^(K / 2) time.
For computing answer for complete knapsack, we can keep a sorted list of sets computed above and for each set make a binary search in other part and compute the answer. You can use upper_bound in c++ too.
For more details, have a look at nicely written tester’s code.
Tester’s solution: link
