Topcoder SRM 594 DIV2 250

Problem Statement

In a nutshell, Given a M x N Matrix we have to check whether it is possible to visit all the cells starting from any location.


Moving Direction - If you are in the cell (x,y), you can only move to ( (x+1)%M, (y+1)%N )

You can find a detailed problem description here.

Solution

The simplest one would be a naive solution.  Checking from (0,0) whether it is possible to cover all the cells.

There is also another awesome solution using GCD(Greatest Common Divisor).

IF ( GCD(M,N) == 1 )

Print " POSSIBLE TO VISIT ALL CELLS"

ELSE

Print " IMPOSSIBLE TO VISIT"

Why GCD Works ?

In this problem both row index and column index are increased by 1 at every step. That is the key point.

Total Number of Cells = M x N

Let's start at cell (0,0). At each step, both the index are incremented by 1. So, both the index will converge at LCM(M,N).  This is clearly indicates the point that

Maximum No. of Cells Visited = LCM(M,N)

LCM(M,N) = (M * N) / (GCD(M,N))

Only when GCD(M,N) = 1, LCM(M,N) will be equal to M*N.

Naive Solution

[sourcecode language="cpp"]
class FoxAndClassroom {
public:
string ableTo(int, int);
};

string FoxAndClassroom::ableTo(int n, int m) {
vector< vector<bool> > flag(n+2,vector<bool>(m+2,true));
int x=0,y=0,cnt=0;

while( flag[x][y] )
{
flag[x][y] = false;
cnt++;
x = (x+1)%n;
y = (y+1)%m;
}

if( cnt == (n*m) )
return "Possible";
else
return "Impossible";

}
[/sourcecode]