Problem Link
Author: David Stolp
Tester: Misha Chorniy
Editorialist: Bhuvnesh Jain
Difficulty
Challenge Problem
Prerequisites
BFS, Optimisations
Problem
You 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.
Explanation
Trivial solution
As we need to remove the items in the order (1, 2, 3, ....), we can just place the items in the clockwise or counter-clockwise 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 Solution
One of the main ideas is that there’s no need to write a separate solver for the pick-up phase versus the drop-off phase. Once you have an algorithm for the drop-off phase, you can run the same algorithm but with the reverse pick-up 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 counter-clockwise 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 drop-off 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 pseudo-code for it.
# Assume solve_grid returns string containing the required steps
def update_ans(s, length, ans):
if len(s) < length:
length = len(s)
ans = s
overall_timer = 0
length = 10**18
ans = ""
s = solve_clockwise()
update_ans()
s = solve_counter_clockwise()
update_ans()
s = solve_spiral()
update_ans()
# Other grid you want to try
TLE = 5.0 - 0.1
TLE_CUT = 2.0
timer = 0
while timer < TLE_CUT:
# generate random grid
s = solve_random_grid()
update_ans()
timer = 0
while timer < TLE_CUT:
# Swap some random poisitons in optimal grid so far
s = solve_improved_grid()
update_ans()
while overall_timer < TLE:
# Maybe try some more iterations of random grid or random swapping
print ans
You can look at the author’s implementation for more details.
Feel free to share your approach, if it was somewhat different.
Solution Links
Setter’s optimised solution can be found here.
Setter’s trivial solution can be found here.