MoveAllMarbles
2021 HF Prelim · 2021-03-02 · by misof
Problem Statement
You have a box with a rectangular bottom. The box is divided into a grid of compartments. The grid has R rows and C columns. Rows are numbered from 0 to R-1, columns from 0 to C-1. The compartment in row r, column c will be denoted (r, c).
Initially, all compartments are empty except for one: the compartment (0, 0) contains N marbles.
You want to move all N marbles to the compartment (R-1, C-1). While doing so, you have to follow a set of rules:
- The marbles must be moved in a series of steps.
- In each step you may only move one marble.
- Whenever you move a marble, its new compartment must share a side with its previous compartment. (I.e., one coordinate must remain the same and the other must change by exactly 1.)
- Compartments other than (0, 0) and (R-1, C-1) must never contain more than one marble at the same time.
- You may only put a marble into the destination compartment (R-1, C-1) if the starting compartment (0, 0) is already empty.
- The total number of steps must be as small as possible.
You are given the dimensions R, C of the grid. Construct any valid sequence of steps that transfers all three marbles to the opposite corner of the given grid. Each step can be represented as an array of length 4: the array { oldr, oldc, newr, newc } corresponds to a step in which we moved one of the marbles from (oldr, oldc) to (newr, newc). Construct these 4-element arrays for your sequence of steps and return their concatenation.
Notes
- For the constraints specified below a valid solution always exists.
- Any valid solution will be accepted.
Constraints
- R will be between 1 and 10, inclusive.
- C will be between 1 and 10, inclusive.
- R*C will be at least 3.
- N will be between 1 and 50, inclusive.
- N will not exceed R*C - 2.
2
3
1
Returns: {0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2 }
We have a 2x3 grid and a single marble. The example output describes the following sequence of moves: from (0,0) to (0,1), from (0,1) to (1,1), and from (1,1) to (1,2).
2
3
2
Returns: {0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 1, 0, 0, 2, 1, 2, 1, 0, 1, 1, 1, 1, 1, 2 }
The same grid but now we have two marbles. Let's call them marble A and marble B. The example output describes the following sequence of moves: Marble A from (0,0) to (0,1). Marble A from (0,1) to (0,2). Marble B from (0,0) to (1,0). Marble A from (0,2) to (1,2). Marble B from (1,0) to (1,1). Marble B from (1,1) to (1,2).
6
1
3
Returns: {0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 2, 0, 3, 0, 3, 0, 4, 0, 1, 0, 2, 0, 0, 0, 1, 0, 4, 0, 5, 0, 2, 0, 3, 0, 3, 0, 4, 0, 1, 0, 2, 0, 2, 0, 3, 0, 4, 0, 5, 0, 3, 0, 4, 0, 4, 0, 5, 0 }
A grid with dimensions 6x1, three marbles, and one of many optimal solutions for this input.
1
6
4
Returns: {0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 3, 0, 3, 0, 4, 0, 0, 0, 1, 0, 1, 0, 2, 0, 2, 0, 3, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 1, 0, 4, 0, 5, 0, 3, 0, 4, 0, 4, 0, 5, 0, 2, 0, 3, 0, 3, 0, 4, 0, 4, 0, 5, 0, 1, 0, 2, 0, 2, 0, 3, 0, 3, 0, 4, 0, 4, 0, 5 }
2
2
2
Returns: {0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1 }
Submissions are judged against all 23 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MoveAllMarbles with a public method vector<int> move(int R, int C, int N) · 23 test cases · 2 s / 256 MB per case