Get Time

   Problem Statement  

 Problem Statement for DancingForever

Problem Statement

    There are n boys and n girls in a dancing room. Boys are numbered 0 through n-1. Girls are also numbered 0 through n-1. Each boy loves one or more girls. You are given a String x with n*n characters. For each i and j, x[i*n+j] is either 'Y' or 'N'. Here, 'Y' means that boy i loves girl j and 'N' means that he does not love her.

Whenever a song starts playing, some couples go dance. Obviously, all couples dancing in the same dance must be pairwise disjoint. Each dancing couple must consist of a boy and a girl the boy loves.

After a dance, each boy who danced looks at all the girls that did not dance. If that set of girls contains some girls he loves, he will choose one such girl G. The boy will then abandon his current dance partner and he will go ask girl G for the next dance.

We are interested in a dance with the following properties:
  • There was at least one dancing couple.
  • After the dance, none of the boys wanted to change their dance partners.

If there is no such dance, return {-1}. (Formally, return a int[] containing a single element: the value -1.) Otherwise, choose any valid dance and output its description in the format specified below. Any valid solution will be accepted.

A dance can be described by a sequence of dancing pairs, each in the order (boy,girl). The correct return value is a int[] obtained by concatenating these pairs. For example, the return value {4, 7, 0, 1} represents a dance where boy 4 danced with girl 7 and boy 0 danced with girl 1.


Method signature:int[] getStablePairs(String x)
(be sure your method is public)


-n will be between 1 and 100, inclusive.
-x will contain exactly n*n characters.
-Each character in x will be 'Y' or 'N'.
-For each i, at least one of the characters x[n*i] to x[n*(i+1)-1] will be 'Y'.


Returns: {0, 0, 1, 1, 2, 2, 3, 3 }
Whenever a perfect matching exists, it is a valid solution: as all girls are dancing, no boy will want to change his partner.
Returns: {1, 0, 2, 1 }
There are multiple valid solutions. Here are some of them: {0, 0}, {0, 0, 1, 1}, {0, 0, 2, 1}, {1, 0, 2, 1}, and {1, 1, 2, 0}.
Returns: {1, 0, 2, 2 }
Note that there may be girls who aren't loved by any boy.
Returns: {3, 3, 4, 4 }
Returns: {0, 0 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 658 Round 1 - Division I, Level Three