patternMinor
Minimum cost problem of breaking containers in $O(n\log n)$
Viewed 0 times
problemlogminimumbreakingcontainerscost
Problem
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<c_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.
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<c_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.
Solution
To solve this problem in $O(n\log n)$, 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
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(n\log n)$.
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
- Calculate $b_i$.
- Add $p_i$ to $cost$.
- Add $b_i$ to the mean-heap and heapify it.
- While $b_j
- If $cost
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(n\log n)$.
Context
StackExchange Computer Science Q#132764, answer score: 2
Revisions (0)
No revisions yet.