WAREHOUS - Editorial

bfs
challenge
editorial
june18
likecs
pieguy

#1

Problem Link

Practice

Contest

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.


#2

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:

Click to view

One easy thing to do is to take the first four boxes and place them in a sorted order against the wall.

\begin{bmatrix} x_{11} & x_{12} & x_{13} & 1 \\ x_{21} & x_{22} & x_{23} & 7 \\ x_{31} & x_{32} & x_{33} & 9 \\ x_{41} & x_{42} & x_{43} & 11 \end{bmatrix}

Then do the same with the next 4 boxes.

\begin{bmatrix} x_{11} & x_{12} & 3 & 1 \\ x_{21} & x_{22} & 4 & 7 \\ x_{31} & x_{32} & 5 & 9 \\ x_{41} & x_{42} & 6 & 11 \end{bmatrix}

The nice thing about this is that once you’ve reached the first value in a column then you can easily get to all other values. But there are some problems with this approach, firstly the 1 is not easily reached and secondly the first row isn’t sorted.

The improved idea:

Click to view

Let’s first decide where every box should be in the end. Start out by deciding that 1 should be placed on x_{12}.

\begin{bmatrix} x_{11} & 1 & x_{13} & x_{14} \\ x_{21} & x_{22} & x_{23} & x_{24} \\ x_{31} & x_{32} & x_{33} & x_{34} \\ x_{41} & x_{42} & x_{43} & x_{44} \end{bmatrix}

Now what is left of the input is 11,7,9,3,4,5,6,10,13,8,14,2,12,15. My next goal is to find x_{13} which should be the smallest out of x_{13},x_{23},x_{33},x_{43},x_{14},x_{24},x_{34},x_{44}. Out of the first eight boxes, we have that 3 is the smallest box. So lets place 3 on on x_{13}.

\begin{bmatrix} x_{11} & 1 & 3 & x_{14} \\ x_{21} & x_{22} & x_{23} & x_{24} \\ x_{31} & x_{32} & x_{33} & x_{34} \\ x_{41} & x_{42} & x_{43} & x_{44} \end{bmatrix}

What is left of the input is 11,7,9,4,5,6,10,13,8,14,2,12,15. Let’s now find x_{14} which should be the smallest of x_{14},x_{24},x_{34},x_{44}. Out of the first four boxes, 4 is the smallest box. So

\begin{bmatrix} x_{11} & 1 & 3 & 4 \\ x_{21} & x_{22} & x_{23} & x_{24} \\ x_{31} & x_{32} & x_{33} & x_{34} \\ x_{41} & x_{42} & x_{43} & x_{44} \end{bmatrix}

We are left with 11,7,9,5,6,10,13,8,14,2,12,15. Now take them 3 at a time and put them in a sorted order against the right side.

\begin{bmatrix} x_{11} & 1 & 3 & 4 \\ x_{21} & x_{22} & 5 & 7 \\ x_{31} & x_{32} & 6 & 9 \\ x_{41} & x_{42} & 10 & 11 \end{bmatrix}

We are left with 13,8,14,2,12,15. So we are done with everything but the last 2 columns. I’m not going to go into detail of how to do the last part but we end up with.

\begin{bmatrix} x_{11} & 1 & 3 & 4 \\ 15 & 2 & 5 & 7 \\ 12 & 8 & 6 & 9 \\ 14 & 13 & 10 & 11 \end{bmatrix}

Some last things to note:
This matrix only shows where I want to put every box, but for the first row there can be a problem as the boxes may not turn up in the input in the correct order (for example if 3 comes before 4). This can be solved by only allowing a box to be placed on x_{i,j} if the box to the right of it has been placed, otherwise temporarily store the box somewhere that it is not in the way, x_{i+1,j-1} happens to work fine for this.

Also note that sometimes it is not possible to end up with such a nice first column as it can happen that x_{i,1} \lt x_{i,2}. That didn’t happen this time, however it is always possible to make the second column sorted and having that x_{i+1,1} \gt x_{i,2}.

This is a pretty nice strategy as it only uses at most O(R+C) characters more than the optimal solution.