You are not logged in. Please login at www.codechef.com to post your questions!

×

# WAREHOUS - Editorial

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.

Setter's optimised solution can be found here.

Setter's trivial solution can be found here.

This question is marked "community wiki".

asked 12 Jun, 09:11

6★likecs
3.7k1978
accept rate: 9%

 5 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: View Content The improved idea: View Content 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:12 769●2●10 accept rate: 41%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,127
×790
×590
×470
×179
×6

question asked: 12 Jun, 09:11

question was seen: 441 times

last updated: 12 Jun, 23:15