Statistics

Problem Statement for "SRMIntermissionPhase"

Problem Statement

Mr. Dengklek introduced you to an online programming contest called SRM (Special Round Match)!

The coding phase is over, and you are now in the intermission phase of the contest. There were 3 problems in the contest. The i-th problem is worth between 1 and points[i] points, inclusive, depending on when a solution to the problem was submitted. The total score of a coder is the total points of all problems whose solutions were submitted by the coder.

The contest has a room summary containing a scoreboard of all coders in the contest. The coders in the scoreboard are sorted in decreasing order of their total score. For each coder, the scoreboard shows the points of each problem, or 0 if the coder didn't submit a solution to the problem.

Unfortunately, you lose your internet connection in this intermission 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 with the highest score, description[1] (if any) describes the coder with the second highest score, and so on. Moreover, your friend also tells you that all coders have different total scores.

Return the number of different possible scoreboards that match your friend's description, modulo 1,000,000,007. Your friend's description may be inaccurate, so, if no scoreboards match it, return 0.

Definition

Class:
SRMIntermissionPhase
Method:
countWays
Parameters:
int[], String[]
Returns:
int
Method signature:
int countWays(int[] points, String[] description)
(be sure your method is public)

Constraints

  • points will contain exactly 3 elements.
  • points[0] will be between 25000 and 30000, inclusive.
  • points[1] will be between 45000 and 60000, inclusive.
  • points[2] will be between 90000 and 110000, inclusive.
  • description will contain between 1 and 20 elements, inclusive.
  • Each element of description will contain exactly 3 characters.
  • Each character in description will be 'Y' or 'N'.

Examples

  1. {25000, 50000, 100000}

    {"YNN", "NNN"}

    Returns: 25000

    The first coder's total score can be between 1 and 25000, inclusive (25000 ways). The second coder's total score must be 0 (1 way). So, in total there are 25000 x 1 = 25000 different possible scoreboards.

  2. {30000, 60000, 90000}

    {"NYN", "NYN"}

    Returns: 799969993

    If the first coder's total score is 2, then the second coder's total score must be 1. If the first coder's total score is 3, then the second coder's total score can be 1 or 2. If the first coder's total score is 4, then the second coder's total score can be 1, 2, or 3, and so on. So, there are (1 + 2 + 3 + ... + 59999) mod 1000000007 = 799969993 different possible scoreboards.

  3. {25000, 45000, 110000}

    {"NNN", "YYY"}

    Returns: 0

    The first coder didn't submit anything, but ranked above the second coder who submitted all three problems. It is impossible.

  4. {25600, 51200, 102400}

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNY", "NYN", "NNN"}

    Returns: 867560805

  5. {25000, 45000, 90000}

    {"YYY"}

    Returns: 999291257

  6. {30000, 60000, 110000}

    {"NNN"}

    Returns: 1

  7. {30000, 60000, 110000}

    {"YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY"}

    Returns: 406554591

  8. {30000, 60000, 110000}

    {"NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN", "NNN"}

    Returns: 0

  9. {25825, 57183, 96726}

    {"YYN"}

    Returns: 476750968

  10. {26406, 56734, 106724}

    {"NNY", "YNN"}

    Returns: 469502309

  11. {25021, 55144, 97044}

    {"NYY", "NYN", "YYY"}

    Returns: 54008456

  12. {26488, 46109, 97112}

    {"NYY", "NYN", "YNN", "NNY"}

    Returns: 829089233

  13. {26803, 52189, 95975}

    {"NYY", "YNY", "NYN", "YNN", "NNN"}

    Returns: 131965753

  14. {26471, 49498, 92670}

    {"NNY", "NYN", "NYY", "YNN", "NNY", "YYN"}

    Returns: 525097248

  15. {29404, 48960, 90453}

    {"YNN", "NNY", "YYY", "NYN", "YNY", "YYN", "NYY"}

    Returns: 80020569

  16. {25575, 57034, 101292}

    {"YNN", "NNY", "NNY", "YYN", "YYY", "YNY", "YNY", "NNN"}

    Returns: 264452930

  17. {25154, 46646, 101268}

    {"YYN", "NNY", "NNY", "YNN", "YNY", "YNY", "YNY", "NYY", "NNN"}

    Returns: 490656534

  18. {25275, 46180, 108685}

    {"NYN", "NYY", "NNY", "NYN", "NYY", "YNN", "YYN", "YNN", "NYY", "YYY"}

    Returns: 557585086

  19. {27019, 51679, 99255}

    {"NYY", "YNN", "YYY", "NYY", "NYN", "YNN", "NYY", "YNN", "NYN", "YNN", "NNN"}

    Returns: 581352091

  20. {26738, 52723, 107896}

    {"NYN", "NYY", "YNN", "NNY", "NYN", "YYY", "YNN", "YYN", "YNN", "YNN", "NYY", "YNN"}

    Returns: 621782235

  21. {27667, 46855, 98053}

    {"NNN", "YNN", "YNY", "NNY", "YYN", "NNY", "NYN", "YNY", "YNN", "NYY", "NNY", "YNY", "NYY"}

    Returns: 0

  22. {28222, 52374, 91085}

    {"YNN", "NNY", "NYY", "NNY", "YNN", "NYN", "YNN", "YYY", "NNY", "YYN", "YYY", "NYN", "NYY", "NNY"}

    Returns: 695416133

  23. {25427, 57062, 95581}

    {"YYN", "YNN", "YYN", "NYN", "NYN", "NNY", "NNY", "NYY", "NYY", "NNY", "NYN", "NYN", "NNY", "YNY", "NNY"}

    Returns: 774344459

  24. {28167, 53441, 106710}

    {"NNY", "NYN", "YYY", "NYY", "YNN", "NYY", "NYN", "NYY", "YYY", "YYN", "YNN", "YNN", "NYY", "NYN", "NYN", "YYN"}

    Returns: 242066034

  25. {27735, 48263, 102484}

    {"YYY", "YYY", "NYY", "NYN", "YYY", "NNN", "YYN", "NNY", "YNY", "NYN", "NYN", "NNY", "YNN", "YNY", "YNY", "NYY", "NNY"}

    Returns: 0

  26. {29489, 54514, 94843}

    {"NYN", "YNN", "YYN", "NYY", "YNY", "NYN", "YNN", "YNY", "YYY", "NYY", "YYN", "YNY", "YNN", "NNY", "YYY", "YNY", "NNY", "NYN"}

    Returns: 728546474

  27. {27268, 48881, 92683}

    {"YNN", "NYN", "YYN", "NNY", "NYN", "NYN", "NNN", "YYY", "NNN", "NYY", "NNY", "YNN", "YNY", "NYY", "NNY", "YYN", "NYN", "NYY", "YNN"}

    Returns: 0

  28. {29018, 46800, 92729}

    {"YYY", "YNY", "NYN", "YNY", "YYY", "YYN", "YYY", "NYY", "YYY", "NNY", "NYN", "YYN", "NYN", "NYN", "NNY", "YYY", "YNN", "YYN", "NNY", "NNY"}

    Returns: 285868678

  29. {25600, 51200, 102400 }

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNY", "NYN", "NNY", "NYN", "NNY", "NYN", "NNN" }

    Returns: 406123230

  30. {30000, 60000, 110000 }

    {"YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY" }

    Returns: 406554591

  31. {25600, 51200, 102402 }

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNY", "NYN", "NNN" }

    Returns: 815987873

  32. {30000, 60000, 110000 }

    {"YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YNY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "NYY", "YYY" }

    Returns: 820593981

  33. {30000, 60000, 98888 }

    {"YYY", "YYY", "YYY", "YYY", "YYY", "NYY", "NYY", "NYY", "YYY", "YYY", "NNY", "NNY", "NNY", "NYN", "NYN", "NNY", "NYN", "NYN", "NNY", "NNN" }

    Returns: 294932411

  34. {25600, 51200, 102400 }

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNY", "NYN", "NNN" }

    Returns: 867560805

  35. {25600, 51200, 102400 }

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNN", "NYN", "NNN" }

    Returns: 0

  36. {28000, 47000, 95000 }

    {"NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY", "NYY", "YYY" }

    Returns: 215334087

  37. {30000, 52599, 100255 }

    {"YYY", "YYY" }

    Returns: 118152490

  38. {30000, 60000, 110000 }

    {"YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY" }

    Returns: 572020046

  39. {30000, 60000, 110000 }

    {"YYY" }

    Returns: 998614007

  40. {30000, 60000, 110000 }

    {"YYY", "YYY", "YYY", "NYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYN", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY", "YYY" }

    Returns: 800286985

  41. {25000, 50000, 100000 }

    {"YNN", "NNN", "NNN" }

    Returns: 0

  42. {25600, 51200, 102400 }

    {"NYY", "YNY", "YYY", "YNN", "YYN", "NNY", "NNN", "NNN" }

    Returns: 0

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.
This problem was used for: