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

×

WAREHOUS - Editorial

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.

This question is marked "community wiki".

asked 12 Jun, 09:11

likecs's gravatar image

6★likecs
3.4k1356
accept rate: 9%

edited 12 Jun, 23:15


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.

link

answered 12 Jun, 18:12

gorre_morre's gravatar image

7★gorre_morre
2723
accept rate: 44%

edited 12 Jun, 18:31

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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:

×14,366
×689
×408
×357
×160
×5

question asked: 12 Jun, 09:11

question was seen: 284 times

last updated: 12 Jun, 23:15