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

×

GAMEBALL - Editorial

PROBLEM LINK:

Practice
Contest

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.

This question is marked "community wiki".

asked 29 May '17, 10:20

pkacprzak's gravatar image

5★pkacprzak ♦♦
75485097
accept rate: 12%

edited 30 May '17, 12:18

admin's gravatar image

0★admin ♦♦
19.8k350498541


A* also worked for this problem where the heuristic function is the number of balls left.

Implementation: https://www.codechef.com/viewsolution/13855737

link

answered 29 May '17, 15:55

mightymercado's gravatar image

4★mightymercado
2816
accept rate: 11%

edited 29 May '17, 15:56

That's nice. Did you measure how many operations it makes on average board?

(29 May '17, 22:50) pkacprzak ♦♦5★

Solutions do not displaying by links.

link

answered 29 May '17, 16:15

batura_dima's gravatar image

5★batura_dima
1264
accept rate: 5%

1

They'll be updated soon. Meanwhile, you can see my solution here: https://www.codechef.com/viewsolution/13835244

(29 May '17, 22:48) pkacprzak ♦♦5★

The links to the solutions show Access Denied...

link

answered 29 May '17, 19:02

yashdodeja's gravatar image

0★yashdodeja
1
accept rate: 0%

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.

link

answered 30 May '17, 00:00

ajecc's gravatar image

3★ajecc
1
accept rate: 0%

What is the answer when n,m = 1?

link

answered 02 Jun '17, 12:14

kirakira's gravatar image

3★kirakira
1
accept rate: 0%

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:

×15,852
×2,657
×850
×485
×7

question asked: 29 May '17, 10:20

question was seen: 1,692 times

last updated: 02 Jun '17, 12:14