Problem LinkAuthor: David Stolp Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyChallenge Problem PrerequisitesBFS, Optimisations ProblemYou are given a grid and the order in which some items are coming. You need to place the items on the grid first and then remove them from the grid in the order $(1, 2, 3, ...)$. There are steps mentioned in the problem statement which can be used to move inside the grid, pick up an item or drop an item. You aim is to output a string containing the steps you will take and the objective is to minimise the length of this string. ExplanationTrivial solutionAs we need to remove the items in the order $(1, 2, 3, ....)$, we can just place the items in the clockwise or counterclockwise direction of the grid. So, the grid may look like 0 1 2 3 4 9 8 7 6 5 10 11 12 13 14 ..... or 0 5 6 11 1 4 7 10 2 3 8 9 .... Optimised SolutionOne of the main ideas is that there's no need to write a separate solver for the pickup phase versus the dropoff phase. Once you have an algorithm for the dropoff phase, you can run the same algorithm but with the reverse pickup order, and then do a sort of reversal on the result to get a sequence of instructions for filling the warehouse. Then it's a matter of assigning shipment locations so that most shipments have a direct path to the entrance in both phases. For designing the algorithm for drop off phase, some sort of BFS/DFS on the grid will be helpful as it will help us to find the shortest path from given cell to the initial one. This problem can be treated as finding the shortest path from cell $(r, c)$ to cell $(0, 0)$ where some cells are blocked in between as some items are placed there. Some optimisations like changing the items in adjacent cells while finding the path can be helpful and optimise the solution further. Another idea was to decide on how the grid should look like in the beginning. Apart from trivial clockwise and counterclockwise ones shown above, spiral placement of items in the grid and ones used by author and gorre_morre can be other options. Author's grid placement idea can be found in this solution below. Gorre_morre's grid placement idea can be found in his solution here If your placement and dropoff phase algorithm is efficient enough, you can even try multiple iterations of it using some random grids and optimise your code further. Even more, changing some random locations and swapping some in the optimal grid you find after some iterations can boost your score. Below is a pseudocode for it.
You can look at the author's implementation for more details. Feel free to share your approach, if it was somewhat different. Solution LinksSetter's optimised solution can be found here. Setter's trivial solution can be found here.
This question is marked "community wiki".
asked 12 Jun '18, 09:11

One of the nice things about this problem was the the better you fill up the warehouse, the easier it was to get the boxes out. My idea was to look at the input and then decide where to put every box. Suppose we have $C=R=4$ and the boxes come in the order $11,7,1,9,3,4,5,6,10,13,8,14,2,12,15$. The basic idea: The improved idea: This is a pretty nice strategy as it only uses at most $O(R+C)$ characters more than the optimal solution. answered 12 Jun '18, 18:12
