News

ACM-ICPC Problem for March 7

Here is a link to this week’s problem.

As mentioned in the problem description, the task is to retrieve m items from a set of n items on a conveyor belt. An important restriction is that the belt moves along at a rate of 1 minute per item, and each item takes a certain (positive) number of minutes to retrieve. In addition, the m items to be retrieved must be retrieved in a specific order. The end goal of the problem is to achieve this task in as little time as possible, and the pdf gives a sample input for this problem as well as the solution for this sample input.

The main difficulty in this problem seems to be the issue of navigating between two extremes: taking the next item on the list at the next possible opportunity (obviously a greedy algorithm), or waiting as long as possible to find a copy of the item whose retrieval requires as little time as possible. The first is problematic if, for example, the item takes 20 minutes to retrieve immediately, but 2 minutes later the same item will appear and require only 1 minute. Of course, the second is problematic because it can be costly to wait for an item that might have actually been retrieved earlier.

An initial brute-force solution would be simply to enumerate over all possible ordered combinations of the necessary items on the conveyor belt, but this will scale exponentially with input and will probably time out. A good initial plan of attack seems to be to find all instances of the first item on the list (requiring linear time), and then associate each of these instances (occurring at place k in the belt and taking time t to retrieve) with the number k+t, then find the minimum such value throughout the list.