The Thirsty Crow

Problem Statement


There are N pots. Every pot has some water in it. They may be
partially
filled. So there is a Overflow Number O associated with
every pot which tell how many minimum stone pieces are require for
that pot to overflow. So if for a pot O-value is 5 it means minimum 5
stone pieces should be put in that pot to make it overflow.


Initially a crow watched those pots and by seeing the water level he
anticipated O-value correctly for every pot (that is he knew O1 to
On). But when he came back in evening he found that every pot is
painted from outside and he is not able to know which pot has what
O-value. The Crow wants some K pots to overflow so that he can serve
his child appropriately. For overflowing the pots he needs to search
for the stones in forest (assume that every stone has same size).


He wants to use minimum number of stones to overflow the K pots. But
he doesn't know now which pot has what O-value. So the task is to find
out the minimum number of stones that the crow requires to make the K
pots overflow in the worst case.


Input Specification:

• A array O corresponding to O-value of N pots {O1, O2, ....... , On}

• Number of pots

• K -value ( number of pots which the crow wants to overflow)

Output Specification:


Minimum number of stones required to make K pots overflow in worst
case or -1 if input is invalid.


Example:


Let's say there are two pots:

• Pot 1 has O value of 5 , O1= 5

• Pot 2 has O value of 58, O2= 58

Let's say the crow wants to make one of the pots overflow. If he
knows which pot has what O-value he would simply search for 5 stones
and put them in pot 1 to make it overflow. But in a real case he
doesn't know which pot has what O-value so just 5 stones may not
always work. However he does know that one pot has O-value 5 and other
has 58. So even in the worst case he can make one of the pot overflow
just by usin

Doesn't work on all cases

Consider a test case with 2 pots: 5, 7 and k=1. Your program will return 10, thinking that the crow must fill both pots with 5 stones. But actually the crow should just fill one pot with 7 stones, making the answer 7.

Alternative algorithms

I think that there are two strategies for eliminating a single pot:

-
Fill one pot with enough stones to fill the biggest pot.

-
Fill all pots each with enough stones to fill the smallest pot. This guarantees that the smallest pot will be filled.

Now, to fill \$k\$ pots, you can't just do the greedy strategy of "for the next pot, pick the minimum stones for case #1 and case #2". That is because case #1 only eliminates one pot from contention, but case #2 also fills all the other pots with some stones, which could have benefits for future iterations.

I can imagine a brute force solution that recursively tries both strategies at each step, but that would take \$O(2^k)\$ time. There is most likely a better way of doing this. Perhaps a linear time solution would be:

For each i in 0..k: Try filling i largest pots with strategy #1, and the k-i smallest pots with strategy #2. Then pick the i that required the least stones and that is the answer.

I haven't thought enough about the problem to know if the above algorithm actually produces the correct answer.

Another consideration

Consider a test case with 3 pots: 5, 5, 20 and k=1. In this case, the answer should be 10 and not 15, because after filling two pots with 5 stones, it is guaranteed to have filled one of the pots of size 5. So this should be considered when using strategy #2 above.

StackExchange Code Review Q#136165, answer score: 4