CheeseRolling

SRM 663 · 2015-06-30 · by zxqfl

SRM 663 · 2015-06-30 · by zxqfl · Dynamic Programming

Show categories

Class Name: CheeseRolling

Return Type: long[]

Method Name: waysToWin

Arg Types: (vector<string>)

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.

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.

Submissions are judged against all 29 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CheeseRolling with a public method vector<long long> waysToWin(vector<string> wins) · 29 test cases · 2 s / 256 MB per case