USACO Bronze January 2023 P2 , Air Cownditioning II

Problems and Contests
#1

Is there an algorithm to solve the problem if the constraints are stricter ? For instance , instead of 10 aircowditioners , how about we had 100 or 1000 ? Do we need to necessarily check all 2^n combinations and find the one that minimizes the cost and simultaneously satisfying the conditions ?

Any help will be appreciated .

Thanks in advance.

1 Like
#2

It turns out that if all p_i=1 it is possible to solve this problem in polynomial time: see E - Bakery