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

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";

}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s