CheeseRolling | Topcoder Archive

Problem Statement

N people (where N is a power of 2) are taking part in a single-elimination tournament in cheese rolling. The diagram below illustrates the structure of the tournament bracket.

The people entering the tournament are numbered from 0 to N-1. For each potential cheese rolling match you know who would win the match. You are given this information encoded as a String[] wins with N elements, each containing N characters. For each valid i and j, wins[i][j] is 'Y' if person i beats person j. Otherwise, wins[i][j] is 'N'. The relation is not necessarily transitive: it may be the case that person i beats person j, person j beats person k, and person k beats person i.

There are N! (N factorial) ways to assign the people to positions in the bracket. Different assignments may produce a different winner of the tournament. Return a long[] with N elements. For each valid i, element i of the return value should be the exact number of assignments for which person i wins the tournament.

Definition

Class:: CheeseRolling
Method:: waysToWin
Parameters:: String[]
Returns:: long[]
Method signature:: long[] waysToWin(String[] wins)
(be sure your method is public)

Constraints

N will be between 2 and 16, inclusive.
N will be a power of 2.
wins will contain exactly N elements.
Each element of wins will have a length of exactly N.
Each element of wins will be composed of the characters 'Y' and 'N'.
For each i from 0 to N-1, wins[i][i] = 'N'.
For all distinct integers i and j from 0 to N-1, exactly one of wins[i][j] and wins[j][i] will be 'Y'.

Examples

```
{"NN",
 "YN"}
```
```
Returns: {0, 2 }
```
There are 2 ways to assign the players: Player 0 goes to position 0 and player 1 goes to position 1. Player 1 goes to position 0 and player 0 goes to position 1. In both assignments, player 1 will win the match against player 0 because wins[1][0] = 'Y'.

{"NYNY",
 "NNYN",
 "YNNY",
 "NYNN"}

Returns: {8, 0, 16, 0 }

{"NYNYNYNY",
 "NNYNYNYY",
 "YNNNNNNN",
 "NYYNNYNY",
 "YNYYNYYY",
 "NYYNNNNN",
 "YNYYNYNN",
 "NNYNNYYN"}

Returns: {4096, 8960, 0, 2048, 23808, 0, 1408, 0 }

{"NYNNNNYYNYYNNYNN",
 "NNNNNNNNNYYNYYNY",
 "YYNYYNNNNYYYYYYN",
 "YYNNYYYNYNNYYYNY",
 "YYNNNYYNYYNNNNYY",
 "YYYNNNNYYNNYYNYN",
 "NYYNNYNYNYNYYYYN",
 "NYYYYNNNYYNYNYYY",
 "YYYNNNYNNYYYYNNN",
 "NNNYNYNNNNNNYYNY",
 "NNNYYYYYNYNYYYNN",
 "YYNNYNNNNYNNYNNY",
 "YNNNYNNYNNNNNYNN",
 "NNNNYYNNYNNYNNYY",
 "YYNYNNNNYYYYYNNN",
 "YNYNNYYNYNYNYNYN"}

Returns: {331616878592, 37267079168, 2426798866432, 2606831599616, 994941665280, 1162501849088, 1888166674432, 4632734203904, 832881524736, 84707409920, 3007127748608, 55490052096, 17818550272, 254672666624, 629921447936, 1959311671296 }

{"NYYYYYYYYYYYYYYY",
 "NNYYYYYYYYYYYYYY",
 "NNNYYYYYYYYYYYYY",
 "NNNNYYYYYYYYYYYY",
 "NNNNNYYYYYYYYYYY",
 "NNNNNNYYYYYYYYYY",
 "NNNNNNNYYYYYYYYY",
 "NNNNNNNNYYYYYYYY",
 "NNNNNNNNNYYYYYYY",
 "NNNNNNNNNNYYYYYY",
 "NNNNNNNNNNNYYYYY",
 "NNNNNNNNNNNNYYYY",
 "NNNNNNNNNNNNNYYY",
 "NNNNNNNNNNNNNNYY",
 "NNNNNNNNNNNNNNNY",
 "NNNNNNNNNNNNNNNN"}

Returns: {20922789888000, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }

Player 0 wins no matter how the positions are assigned, so the answer is 16! = 20922789888000.

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.