# Minimum cost problem of breaking containers in $O(n\log n)$

Can anyone kindly give me some hint on solving this?

There are $$n$$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with capacity $$c_i$$ and initial water $$a_i$$ ($$a_i). In case of breakage of any container, all the water inside it will pour into the container below. Each container will break if the water inside it is more than its capacity. On the other hand, we can always break a container manually by paying the cost $$p_i$$.

Provide an algorithm to find the minimum cost to break the $$n$$th container in $$O(n\log n)$$. Using a binary heap may be useful.

• Start with containers 1, 2, and 3. – greybeard Nov 28 '20 at 23:05
• @greybeard you mean using induction? – Maria Nov 29 '20 at 5:15
• Not literally, but ("constructive") proofs, algorithms and programs do have things in common. Depending on point of view, there are different paradigms suggesting themselves with the problem presented above. Alternatively called algorithm or programming paradigms. If solution of above problem has been an assignment in an educative context, chances are one of them has been a topic recently. – greybeard Nov 29 '20 at 8:23
• @greybeard can you please provide more details acording to edit? – Maria Nov 29 '20 at 10:08
• Isn't $O(n)$ possible with dynamic programming (following the hint of @greybeard)? How does a binary heap help? The last paragraph almost feels like disinformation to me. – orlp Nov 29 '20 at 14:49

To solve this problem in $$O(nlogn)$$, We can use a min-heap.

Consider $$s_i = \Sigma_{k=i}^{n}{a_k}$$ and $$b_i = s_i + c_i - a_i$$. You can see that if $$b_i - s_j < 0$$ for $$j < i$$, by starting from $$j$$ and breaking every container from $$j$$ to $$i$$, container $$i$$ will break by the amount of water from the containers $$j$$ to $$i$$.

First set $$cost = 0$$ and $$min = p_i$$. Then do the following from $$n$$ to $$1$$:

1. Calculate $$s_i$$.
2. Calculate $$b_i$$.
3. Add $$p_i$$ to $$cost$$.
4. Add $$b_i$$ to the mean-heap and heapify it.
5. While $$b_j - s_i < 0$$ ($$b_j$$ is the root of the heap): Remove the root and subtract $$p_j$$ from $$cost$$.
6. If $$cost < min$$, update $$min$$.

At every container, we know that if we start from that container, we need to break some of them and the rest will break by the water. When we remove a container from the heap, we can be sure that if we start from that container, the removed container will break by itself, and the total cost will be to break the rest, so we can subtract the cost of breaking the removed container from the total cost.

Since the while loop is run once for each container, and the for loop runs n times, the total time will be $$O(nlogn)$$.