PROBLEM LINK:
Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak
DIFFICULTY:
Medium
PREREQUISITES:
Implementation
PROBLEM:
Given a grid with n rows and m columns, where exactly one cell is empty and all other cells contain a ball. Perform at most 5000 of the below moves to remove all but one ball, or print -1 if this is not possible. Moves are:
Move(A, B) := defined for two adjacent cells A and B, such that there is a ball in A and B is empty. It moves the ball from A to B, so after the operation, the ball is in B and A is empty.
Jump(A, C) := defined for two adjacent cells A and B, such that they are in the same row or column, there is exactly one cell B between them, there are balls in A and B, and C is empty. After the operation, the ball from A is moved to C and the ball in B is removed.
EXPLANATION:
Perhaps there exist many different strategies to solve the problem. I’ll describe the one I used in the contest - yes I was participating, although it’s quite unusual for a participant to write editorials :).
First of all, let’s consider some special cases:
Special Case 1:
When n = 1 and m = 1, the answer is -1, because, by definition, there is no ball in the grid.
Special Case 2:
When n = 1 and m = 2, or n = 2 and m = 1, we don’t have to make any moves, because the grid contains exactly one ball already.
Special Case 3:
When n = 2 and m = 2, then the answer is -1, because initially there are 3 balls in the grid and we are only able to perform Move operations (notice that we need at least 3 rows or at least 3 columns to perform a Jump operation), so there is no way to reduce the number of balls.
Special Case 4:
If n = 1 and m \geq 3, or n \geq 1 and m = 1, we only need to solve the problem for a single row or a single column, and since this will be a subroutine of the general solution described below, we assume that we know how to solve it.
General Case:
After handing the above cases, we have max(n, m) \geq 3 and min(n, m) \geq 2, so we know that we can perform operations of both kinds.
The first observation is that since the maximum number of operations we can perform is 5000, which corresponds to at most 50 operation on average to remove a single ball. After seeing this upper bound I thought that it is so high that we can totally forget about the bound while thinking about the solution and just figure out how to remove all balls but one, and then just verify if we don’t perform too many operations. It turned out that the below strategy uses much fewer moves.
My solution can be divided into several steps:
Step 1
Moving the single empty cell to the upper-left corner of the grid. This should be pretty straightforward as we can just use Move operation to shift the empty cell into that corner. Since now, we can assume that every input differs just in the size of the grid because we always start with the empty cell in the upper-left corner as we moved it there.
Now, the crucial subroutines of my solution: reduceRow(i) and reduceCol(j), which respectively, for row i (column j) containing a single empty cell in its left-most (upper-most) column (row), removes all but one ball from this row (column) and leaves the only remaining ball in the right-most (bottom-most) column (row). For example, reduceRow performed on a row .**** transforms it to ....*
But the question is how to implement these two operations. I will show how to do it for reduceRow (reduceCol is the same idea, only rotate by 90 degrees).
Ok, so we have a row containing a single empty cell in its left-most column and we want to remove all but one ball from this row and have the remaining ball in the right-most column of the row. We are going to do this repetitively performing two consecutive Move operations involving the right-most empty cell and the ball just to the right of it. These two Move operations will be followed by a single Jump operation involving the right-most empty cell and two balls directly preceding it.
For illustrating the concept, let’s consider an example row .**** with 5 columns. For simplicity, I’ll denote Move(j+1, j) to perform Move operation on the j+1-th and the j-th cells of the row, i.e moving the ball from the j+1-th cell to j-th cell. Similarly Jump(j, j+2) will denote the Jump operation performed on j-th and j+2-th cells of the row.
At the beginning, we perform Move(2, 1) followed by Move(3, 2), which result in: **.** After that, we perform Jump(1, 3), which results in ..***, so we removed one ball and all balls remaining to remove form a consecutive segment ending in the right-most column of the row. Since there are still balls to remove, we again perform two Move operations followed by Jump operations. More specifically, we perform Move(3, 2), then Move(4, 3) resulting in ..**., and finally we perform Jump(3, 5), which results in ....* so we got what we wanted.
Operations described above will be very useful in the next steps.
Step 2
In the second step, we want to transform the grid containing only a single empty cell located in the upper-left corner to a grid containing ball only in the bottom-most row and right-most column. In other words, we want to transform the grid:
.*****
******
******
******
to a grid:
.....*
.....*
.....*
******
In order to do that, we perform reduceRow for the first row, resulting in the following grid:
.....*
******
******
******
Now, notice that each column besides the right-most one contains exactly one empty cell, so we can reduce them as well! After performing reduceCol for all these columns we get what we wanted:
.....*
.....*
.....*
******
Step 3
We would like to reduce the remaining row, but there is no empty cell there, so we use a move operation to create one:
.....*
.....*
*....*
.*****
Now, we perform reduceRow on the last row and get:
.....*
.....*
*....*
.....*
Step 4
We would also like to reduce the right-most column, but there is no empty cell there, so we use a move operation to create one:
....*.
.....*
*....*
.....*
And now we perform reduceCol on the right-most column and get:
....*.
......
*.....
.....*
Final step
Now, since there are just 3 balls in the grid, we can move them for example to bottom of the last column (or last row if there are less than 3 columns), so they form a consecutive segment and then use a simple combination of Move and Jump operations to remove last 2 balls leaving a single ball in the grid.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.