FoxAndClassroom: TopCoder Problem 12811

[The problem appeared in TopCoder SRM 594 (Div-2, Level-1)]
Problem link: http://community.topcoder.com/stat?c=problem_statement&pm=12811

Problem Statement:
Fox Ciel is now in high school. The seats in her classroom are arranged into an n by m matrix. The rows are numbered from 0 to n-1 (front to back) and the columns from 0 to m-1 (left to right).
At the beginning, Ciel can choose any of the seats. Then, at the end of each week Ciel will shift one row to the back and one column to the right, wrapping around whenever necessary. Formally, if her current seat is in row r and column c, then her seat next week will be the one in row ((r+1) modulo n) and column ((c+1) modulo m).
Fox Ciel now wonders whether she can sit in all the seats in the classroom if she follows the above procedure. As we already mentioned, she can start in any of the seats. Also, she can attend the school for as many weeks as she wants to. Return “Possible” if she can sit in all the seats and “Impossible” otherwise.

Definition:
Class: FoxAndClassroom
Method: ableTo
Parameters: int, int
Returns: String
Method signature: String ableTo(int n, int m)

Constraints:
1. n will be between 2 and 10, inclusive.
2. m will be between 2 and 10, inclusive.

Solution Idea:
Very simple, if you use a set. While moving to the next cell, we have to check that if she has already visited that cell or not. And repeat the procedure for all possible start points (ableTo_slow function).

Now we can improve it, when starting the next run of checking if we put a condition that only start if the start point is already not part of any previous visited points (ableTo function).

Solution Gist:

Advertisements

Tagged: , , , , ,

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 )

Google+ photo

You are commenting using your Google+ 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 )

Connecting to %s

%d bloggers like this: