DancingForever
SRM 658 · 2015-05-01 · by cgy4ever
SRM 658 · 2015-05-01 · by cgy4ever · Graph Theory
Problem Statement
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:
If there is no such dance, return {-1}. (Formally, return aint[] 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 aint[] 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.
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
A dance can be described by a sequence of dancing pairs, each in the order (boy,girl). The correct return value is a
Constraints
- 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'.
Examples
0)
"YYNNNYYNNNYYYNNY"
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.
1)
"YNNNYYNNYYNNNNYY"
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}.
2)
"YNYYNYYNY"
Returns: {1, 0, 2, 2 }
Note that there may be girls who aren't loved by any boy.
3)
"YYYNNYYYNNNNNYYNNNYYNNNYY"
Returns: {3, 3, 4, 4 }
4)
"Y"
Returns: {0, 0 }
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DancingForever with a public method vector<int> getStablePairs(string x) · 103 test cases · 2 s / 256 MB per case