DancingParty | Topcoder Archive

Problem Statement

You are organizing a dance party. The party will be attended by n boys and n girls. There will be several rounds of dancing.

In each round, you divide the guests into n dancing pairs. Each guest must be in exactly one pair, and each pair must contain one boy and one girl. Each boy must dance with a different girl in every round. Some boys and girls like each other and some do not. During the party, each boy agrees to dance with at most k girls he doesn't like. Similarly, each girl agrees to dance with at most k boys she doesn't like.

You are given a String[] likes. The j-th character of likes[i] is 'Y' if the i-th boy and the j-th girl like each other, and 'N' if they don't. Return the maximum number of rounds you can organize.

Definition

Class:: DancingParty
Method:: maxDances
Parameters:: String[], int
Returns:: int
Method signature:: int maxDances(String[] likes, int k)
(be sure your method is public)

Constraints

likes will contain between 1 and 50 elements, inclusive.
Each element of likes will contain exactly n characters, where n is the number of elements in likes.
Each element of likes will contain only the characters 'Y' and 'N'.
k will be between 0 and 50, inclusive.

Examples

```
{"YYY", "YYY", "YYY"}
```
```
0
```
```
Returns: 3
```
Every boy likes every girl, so you can organize 3 rounds.
```
{"YYY", "YYN", "YNY"}
```
```
0
```
```
Returns: 2
```
For example, you can have one round with pairs 1-2, 2-1 and 3-3 and one round with pairs 1-3, 2-2 and 3-1.
```
{"YN", "YN"}
```
```
0
```
```
Returns: 0
```
The second girl doesn't like anybody.
```
{"YN", "YN"}
```
```
1
```
```
Returns: 1
```
The second girl doesn't like anybody again, but this time she agrees to dance with someone she doesn't like once.

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)2024, Topcoder, Inc. All rights reserved.