There are N numbers written in an array, ith being f(i). You can choose a segment of array of length K and the minimum number of that segment which is still present will be erased (creating a hole at that location). If there are multiple numbers which are equal to the minimum, all of them are erased. What is the minimum number of times, one must do this operation to erase all the numbers.
You can always try to erase the smallest number first. After choosing which number to erase, interval can be chosen greedily to erase maximum numbers at one go.
We prove following three very intuitive claims :
- There is some optimal solution in which first dish to be cooked is the one
having smallest f(i) value.
- In each turn we could be greedy and cook meal having the smallest f(i) value.
- Once a meal to be cooked has been chosen, interval can be chosen greedily.
Let’s prove claim 1 :
Assume that dish p is the one having least value of f(i). Assume that in optimal
solution, first meal cooked is not the one having smallest f(i) time. Let’s
look at the windows chosen [i1, i1+K-1), [i2, i2+K), [i3, i3+K) … . One of these contains p, say rth is the first window that contains p. If you swap it with a window before it, nothing changes since all the dishes that were cooked
in these two windows would be cooked after the swap as well. By swapping again
and again you can bring it at the front and cost of your solution won’t increase.
Hence we’ve produced another optimal solution in which dish with smallest cooking
time is cooked first. Hence proved
Claim 2 follows from claim 1 naturally, by applying this same argument again and
again after each erase operation.
For proving claim 3, let’s say the smallest cooking time is T and there are K
different meals having this time. By claim 2 above, it is clear that in first few
rounds we would cook all these dishes until they’re all cooked. Now say these
dishes from left to right are d1, d2 … dk. Here it is easy to see that we can
chose intervals greedily i.e fix up an interval with left end at d1 and try to
cook as many dishes as possible in one go only. Then put left end of our
interval on next uncooked dish and so on.
Can be found here.
Setter noted that all dishes having same cooking time can be processed together (spread over a few rounds) and so we don’t need to sort the elements either on cooking time. His algorithm in his own words:
Cook first uncooked meal with least
index from entire array and let’s the
index of this meal is I. then cook
all the meals i which is
I<=i<=I+K and have f(i)=f(I). Repeat this procedure until all meals
Can be found here.