Statistics

Problem Statement for "ScoreRecomposition"

Problem Statement

You took a test consisting of N questions, each of which has a distinct point value between 1 and N, inclusive, and you have finally received the results. Along with your final score, you are told which questions you answered correctly. However, you are not given the point values that were assigned to the questions. For each correct answer, you received the full point value of the question, and for each wrong answer, you received 0 points. You must determine the minimum possible error of a valid point assignment that would result in the final score that you received. The error of a valid assignment of points is defined as follows: For each question i (where i is a 1-based index), let e(i) = the absolute value of (i minus the point value of the question). The error of the point assignment is the maximum value of e(i).

Given a String questions and an int score, return an int representing the minimum possible error of a valid point assignment. The ith character (where i is a 1-based index) of questions is either 'C', meaning that you answered question i correctly, or 'W', meaning that you answered it wrong. If there is no valid point assignment, return -1.

Definition

Class:
ScoreRecomposition
Method:
minError
Parameters:
String, int
Returns:
int
Method signature:
int minError(String questions, int score)
(be sure your method is public)

Constraints

  • questions will contain exactly N elements, where N is between 1 and 10, inclusive.
  • Each character of questions will be either 'C' or 'W'.
  • score will be between 0 and N*(N+1)/2, inclusive.

Examples

  1. "CCC"

    5

    Returns: -1

    Contact the contest director immediately! Since you answered every question correctly, your score should be 6.

  2. "WCWW"

    4

    Returns: 2

    Obviously, you answered only the 4-point question correctly.

  3. "CWW"

    1

    Returns: 0

    The minimum error occurs when each question i is assigned a point value of i.

  4. "CWCC"

    6

    Returns: 2

    One valid point assignment with the lowest possible error is 1, 4, 2, 3.

  5. "WWCC"

    3

    Returns: 2

  6. "WWWWW"

    0

    Returns: 0

  7. "C"

    1

    Returns: 0

  8. "WWCCWWW"

    19

    Returns: -1

  9. "WWWCCC"

    14

    Returns: 1

  10. "WCWCCCCCW"

    35

    Returns: 2

  11. "CCWCWCWWCW"

    50

    Returns: -1

  12. "WWCCCC"

    18

    Returns: 0

  13. "CWW"

    1

    Returns: 0

  14. "CW"

    2

    Returns: 1

  15. "WWCWCWWCC"

    25

    Returns: 0

  16. "W"

    0

    Returns: 0

  17. "WWCCWWWCWW"

    17

    Returns: 1

  18. "CCCWWCWCC"

    34

    Returns: 2

  19. "WWCW"

    0

    Returns: -1

  20. "CWCCWWCWCC"

    55

    Returns: -1

  21. "CWWCCCCW"

    24

    Returns: 1

  22. "CCCCCWWWW"

    26

    Returns: 4

  23. "CCCCWCCCWC"

    49

    Returns: 4

  24. "CW"

    2

    Returns: 1

  25. "WCWWCWWWC"

    22

    Returns: 3

  26. "WWW"

    0

    Returns: 0

  27. "CWWCWCCWWC"

    37

    Returns: 3

  28. "CWCWC"

    10

    Returns: 1

  29. "CWWC"

    6

    Returns: 1

  30. "CCCCCWCC"

    17

    Returns: -1

  31. "CCWWWCWCWW"

    50

    Returns: -1

  32. "CWC"

    5

    Returns: 1

  33. "CCCCCC"

    21

    Returns: 0

  34. "WCCWWCWCCC"

    40

    Returns: 1

  35. "CCW"

    3

    Returns: 0

  36. "WCCWC"

    14

    Returns: -1

  37. "WC"

    3

    Returns: -1

  38. "WWCWCWWW"

    25

    Returns: -1

  39. "WCW"

    2

    Returns: 0

  40. "WWCCC"

    4

    Returns: -1

  41. "WC"

    3

    Returns: -1

  42. "CWCCWCWCW"

    21

    Returns: 1

  43. "WCWCWC"

    15

    Returns: 2

  44. "WCCCWCCCC"

    38

    Returns: 1

  45. "CCCCWWCC"

    28

    Returns: 2

  46. "CW"

    2

    Returns: 1

  47. "WCWWWWC"

    23

    Returns: -1

  48. "CWC"

    2

    Returns: -1

  49. "CCWWCC"

    1

    Returns: -1

  50. "WWWCC"

    14

    Returns: -1

  51. "CCWWC"

    8

    Returns: 0

  52. "CWCC"

    2

    Returns: -1

  53. "WWCWCC"

    3

    Returns: -1

  54. "CCCWCCCWW"

    6

    Returns: -1

  55. "WCWWWC"

    3

    Returns: 4

  56. "WCWCWWWC"

    4

    Returns: -1

  57. "WCCW"

    2

    Returns: -1

  58. "WWWCCWCWCC"

    52

    Returns: -1

  59. "CW"

    1

    Returns: 0

  60. "WWWCCWWCCW"

    22

    Returns: 2

  61. "CWWWCWCCWW"

    52

    Returns: -1

  62. "CWWC"

    1

    Returns: -1

  63. "CWWWWWWWWW"

    10

    Returns: 9

  64. "CCWCWCCWCW"

    43

    Returns: 5

  65. "WCCWW"

    5

    Returns: 0

  66. "CWWCWCCWWC"

    37

    Returns: 3

  67. "WCWW"

    4

    Returns: 2

  68. "CCCCCC"

    5

    Returns: -1

  69. "C"

    1

    Returns: 0

  70. "WWWWWCCCCC"

    27

    Returns: 4

  71. "WCWCWCWCWC"

    26

    Returns: 1

  72. "WWCCCWWWCC"

    21

    Returns: 3

  73. "CCCCCCCCCC"

    55

    Returns: 0

  74. "WCCW"

    5

    Returns: 0

  75. "WWCCWWCWCC"

    29

    Returns: 2

  76. "CCCCCCCCWW"

    52

    Returns: 8

  77. "CCW"

    5

    Returns: 2

  78. "CWWCWWWCC"

    13

    Returns: 4

  79. "CCWCCWWCCW"

    44

    Returns: 5

  80. "WCCCCCC"

    21

    Returns: 6

  81. "WWWWWWWWCW"

    2

    Returns: 7

  82. "CWCC"

    6

    Returns: 2

  83. "WCWC"

    4

    Returns: 1

  84. "WWWWWC"

    1

    Returns: 5

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: