PROBLEM LINK:Author: admin2 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 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 leftmost (uppermost) column (row), removes all but one ball from this row (column) and leaves the only remaining ball in the rightmost (bottommost) column (row). For example, $reduceRow$ performed on a row 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 leftmost column and we want to remove all but one ball from this row and have the remaining ball in the rightmost column of the row. We are going to do this repetitively performing two consecutive $Move$ operations involving the rightmost 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 rightmost empty cell and two balls directly preceding it. For illustrating the concept, let's consider an example row At the beginning, we perform $Move(2, 1)$ followed by $Move(3, 2)$, which result in: Operations described above will be very useful in the next steps. Step 2
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 rightmost 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
Now, we perform $reduceRow$ on the last row and get:
Step 4
And now we perform $reduceCol$ on the rightmost 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:
This question is marked "community wiki".
asked 29 May '17, 10:20

A* also worked for this problem where the heuristic function is the number of balls left. Implementation: https://www.codechef.com/viewsolution/13855737 answered 29 May '17, 15:55

Solutions do not displaying by links. answered 29 May '17, 16:15
1
They'll be updated soon. Meanwhile, you can see my solution here: https://www.codechef.com/viewsolution/13835244
(29 May '17, 22:48)

Can also be solved with simple backtracking: if a ball can destroy another ball you do that move and continue with the backtracking. Else, you move each ball to the adjacent cell if possible and call the backtrack with the grid in that state. You must also be careful not to go back to a previous state. Do this until you have 1 ball left. You can store the steps in a string, for example, because the values in the answer are smaller than 10. answered 30 May '17, 00:00
