PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
The request that the distance has to decrease with every pass is a very nice property although it might seem like a complication at first. Begin by sorting the cells by their distance to the storage. Now you can take a dynamic programming approach. Define f(i,j) as the cost of moving an item to the storage from position (i,j). You can compute f(i,j) from the previously computed costs of other closer positions which are within the passing range. You could simply scan the entire passing range and get a complexity O(N * M * D^2), which is too slow. But this query operation “which solution within passing range is the cheapest?” can be done faster with a data structure that supports updates and range queries in logarithmic time. A 2-dimensional segment tree is a good candidate. You have to pay some attention to equidistant cells. Process them in batches and perform the updates of the data structure at the end of the batch. The intended time complexity for this problem was O(N * M *(log D)^2). The timelimit is a bit on the strict side to prevent solutions with 1-dimensional segment trees, which would iterate over all rows within the passing range and perform 1-dimensional range queries within a row.
However, many contestants came up with a different solution. It is based on Dijsktra’s shortest path algorithm with some optimizations. The important thing to notice is that all edges in the graph have the same weight. Therefore, when you process a node and insert adjacent nodes into priority queue, you will never have to update them again so you can simply remove them. You can maintain a sorted list of cells for each row and when you update some cell and push it into priority queue, you can also delete it from its row list. For small passing range D you only have to iterate over a few rows. This solution also works for large D. The cell lists will shrink rapidly because you will be deleting big rectangular chunks of cells with each update.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here