SRMSystemTestPhase
SRM 520 · 2011-05-25 · by fushar
Problem Statement
You are now in the system test phase of the contest. There were N coders in the contest. There were 3 problems in the contest. The system has tested all submitted solutions in the contest. For each submitted solution, there are 3 possible outcomes: 'passed', 'failed', and 'challenged'.
The contest has a division summary containing a scoreboard of all coders in the contest. For each coder, the scoreboard shows the outcome of the submitted solution of each problem, or an 'X' if the coder didn't submit a solution to the problem. The coders in the scoreboard are sorted in descending order of the number of passed solutions. If there is a tie, then they are sorted in ascending order of the number of challenged solutions. If there is still a tie, the scoreboard may show them in arbitrary order.
Unfortunately, you lose your internet connection in this system test phase. So, you ask your friend how the scoreboard is currently like. However, your friend only tells you the solutions submitted by each coder. This is given in description. The j-th character of the i-th element of description will be 'Y' if the i-th coder submitted a solution to the j-th problem, or 'N' otherwise. description describes the scoreboard from top to bottom, i.e., description[0] describes the coder in the first position, description[1] (if any) describes the coder in the second position, and so on.
Return the number of different possible scoreboards that match your friend's description, modulo 1,000,000,007.
Constraints
- description will contain between 1 and 50 elements, inclusive.
- Each element of description will contain exactly 3 characters.
- Each character in description will be 'Y' or 'N'.
{"YYY"}
Returns: 27
There are 3 possible outcomes for each solution, so there are 3^3 = 27 different possible scoreboards.
{"YNN",
"NYN"}
Returns: 6
Here are the 6 different scoreboards: +----------------------------------+----------------------------------+ | passed X X | passed X X | | X passed X | X failed X | +----------------------------------+----------------------------------+ | passed X X | failed X X | | X challenged X | X failed X | +----------------------------------+----------------------------------+ | failed X X | challenged X X | | X challenged X | X challenged X | +----------------------------------+----------------------------------+
{"YNN",
"NNN",
"NNY"}
Returns: 4
Here are the 4 different scoreboards: +----------------------------------+----------------------------------+ | passed X X | passed X X | | X X X | X X X | | X X failed | X X challenged | +----------------------------------+----------------------------------+ | failed X X | failed X X | | X X X | X X X | | X X failed | X X challenged | +----------------------------------+----------------------------------+
{"NNN",
"NNN"}
Returns: 1
{"YYY",
"YNY",
"NYY",
"YYN",
"YYY",
"YNN"}
Returns: 15176
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SRMSystemTestPhase with a public method int countWays(vector<string> description) · 86 test cases · 2 s / 256 MB per case