Statistics

Problem Statement for "DoorsGame"

Problem Statement

John and Gogo are playing Doors Game. This game is played in a building containing a single row of N+1 rooms, numbered 0 through N from left to right. One of the rooms is called the trophy room. There's a door between each pair of adjacent rooms. Each door has a color, and there are 16 possible colors (represented by uppercase letters 'A' through 'P'). All doors are initially closed.

Initially, John is in room 0 and Gogo is in room N. The two players alternate turns, and John gets the first turn. On each turn, the current player chooses a color which hasn't yet been chosen from among the 16 possible colors. All doors, if any, with the chosen color are then opened. At this point, if one of the players can reach the trophy room by walking through only open doors, that player wins and the game ends. If both players can reach the trophy room, the game ends in a draw. If neither player can reach the trophy room, the game continues.

Each player will play according to the following strategy: Each time a player needs to choose a color, he will make make his choice as follows:
  • If it's possible for him to choose a color in such a way that he will be able to win no matter what his opponent does, he will choose such a color. If there are several such colors, he will choose the one among them for which the game will end with the fewest total number of colors chosen, assuming that the opponent aims to maximize the number of colors chosen in the game.
  • Otherwise, if it's possible for him to choose a color in such a way that he will be able to end the game in a draw no matter what his opponent does, he will choose any such color.
  • Otherwise, he will choose a color for which the game will end with the largest total number of colors chosen, assuming that his opponent aims to win while minimizing the total number of colors chosen.
You are given the colors of the doors in the String doors. The i-th character in doors is the color of the door connecting rooms i and i+1. You are also given an int trophy, which denotes the number of the trophy room. If the game ends in a draw, return 0. Otherwise, let X be the number of colors chosen in the game. If John wins, return X. If Gogo wins, return -X.

Definition

Class:
DoorsGame
Method:
determineOutcome
Parameters:
String, int
Returns:
int
Method signature:
int determineOutcome(String doors, int trophy)
(be sure your method is public)

Constraints

  • doors will contain between 2 and 50 characters, inclusive.
  • Each character in doors will be an uppercase letter 'A'-'P'.
  • trophy will be between 1 and N-1, inclusive, where N is the number of characters in doors.

Examples

  1. "ABCD"

    2

    Returns: 3

    There are five rooms, with the trophy room in the middle. John will win after he chooses color A and B.

  2. "ABCC"

    2

    Returns: -2

    In this case, Gogo will win by just choosing color C.

  3. "ABABAB"

    3

    Returns: 0

    When colors A and B have been chosen, both players will be able to reach the trophy room.

  4. "ABAPDCAA"

    5

    Returns: -4

  5. "MOCFDCE"

    3

    Returns: 5

  6. "ABCCDE"

    3

    Returns: 0

  7. "ACC"

    2

    Returns: 0

  8. "ABCDEFGHIJKLMNOP"

    7

    Returns: 13

  9. "ABCDEFGHIJKLMNOP"

    8

    Returns: 15

  10. "ABCDEFGHIJKLMNOP"

    9

    Returns: -14

  11. "ABCDEFGHIJKLMNOP"

    10

    Returns: -12

  12. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    16

    Returns: 0

  13. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    8

    Returns: 15

  14. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    9

    Returns: 0

  15. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    25

    Returns: -14

  16. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    24

    Returns: 0

  17. "PNKCMCHKPBAGAOHACNGAFEPOKGABHMBKHNHJBAHKLPDOJLNPFC"

    40

    Returns: 0

  18. "ABCDEF"

    1

    Returns: 1

  19. "PDBGECCBAGBE"

    10

    Returns: -4

  20. "JKANOBFNGPHOCLBCJCAKEPEIPKAICPKECKKKDPEADMCPDAMIAP"

    20

    Returns: 0

  21. "JOJJJOOJJOOJOJJJOJJJOOJJONNJJJJJNJJJJNJNNNJJJNNNJJ"

    25

    Returns: 0

  22. "NIAEGMBJOKPCLHDFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"

    15

    Returns: -2

  23. "IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIJELFBHNOMCPDGAK"

    35

    Returns: 1

  24. "JPJPHGFJMIEELJKBOPNGABCEDBCHJAEPDKGIBCMIEFDIPFGNLO"

    25

    Returns: 0

  25. "JMPLADFNIKODPMECJGIB"

    10

    Returns: 0

  26. "PHHNBBNHGPNFIOHHFOJBEHOJOLKMDHDLEPDMLIAAPAAHHDHAJK"

    25

    Returns: 0

  27. "KDHHFIMECBHDBINLLKPLALALDKKAOJPPPLAOKLLPIOKEGIPIAP"

    15

    Returns: 0

  28. "FJLNGJMGCENHEAFBFLHAMBMKDKBBKEJMOJBBKOMMJOMJBBMIKD"

    20

    Returns: 0

  29. "HNJDJEMJCMEHFPIMKKOLGNBINBABIGAIGGDNGNAGDLNNAIBANB"

    20

    Returns: -14

  30. "DHODKMNBNDKOHIKKNHHKMPJLFGACBAPEIKKIA"

    20

    Returns: 15

  31. "ABDFBBLBACJJFDDDLCDJFMJMPNHCEOGKNAEI"

    20

    Returns: 13

  32. "HHPDLALMJNOEACMKGDMGNMHPFCEBILCJDB"

    17

    Returns: 0

  33. "JNJMEEMBBKNCPCNKKMNMEBPKNGIDDHHAGOAAIHGFHLGFFODDLL"

    25

    Returns: 15

  34. "GIMOCNAPDLKLDFJDHFHLFKJKFJDKKBLLKJDDJDDLFBDEFLKEKB"

    8

    Returns: 15

  35. "OJHBPEKMNFCLDLCDGCLAIAADDDACICCGFFGKAICKLKIFKKDDII"

    9

    Returns: 0

  36. "NCJIFEHPGDBKHODHKADHBOMHMABLDBOALDDHLDDMHBOLMKAHLO"

    8

    Returns: 15

  37. "LBKPFOANFCACMDHGIEJK"

    1

    Returns: 1

  38. "LBKPFOANFCACMDHGIEJK"

    2

    Returns: 3

  39. "LBKPFOANFCACMDHGIEJK"

    3

    Returns: 5

  40. "LBKPFOANFCACMDHGIEJK"

    4

    Returns: 7

  41. "LBKPFOANFCACMDHGIEJK"

    5

    Returns: 9

  42. "LBKPFOANFCACMDHGIEJK"

    6

    Returns: 11

  43. "LBKPFOANFCACMDHGIEJK"

    7

    Returns: 13

  44. "LBKPFOANFCACMDHGIEJK"

    8

    Returns: 15

  45. "LBKPFOANFCACMDHGIEJK"

    9

    Returns: 15

  46. "LBKPFOANFCACMDHGIEJK"

    10

    Returns: 0

  47. "LBKPFOANFCACMDHGIEJK"

    11

    Returns: 0

  48. "LBKPFOANFCACMDHGIEJK"

    12

    Returns: 0

  49. "LBKPFOANFCACMDHGIEJK"

    13

    Returns: -14

  50. "LBKPFOANFCACMDHGIEJK"

    14

    Returns: -12

  51. "LBKPFOANFCACMDHGIEJK"

    15

    Returns: -10

  52. "LBKPFOANFCACMDHGIEJK"

    16

    Returns: -8

  53. "LBKPFOANFCACMDHGIEJK"

    17

    Returns: -6

  54. "LBKPFOANFCACMDHGIEJK"

    18

    Returns: -4

  55. "LBKPFOANFCACMDHGIEJK"

    19

    Returns: -2

  56. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    1

    Returns: 1

  57. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    2

    Returns: 3

  58. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    3

    Returns: 5

  59. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    4

    Returns: 5

  60. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    5

    Returns: 7

  61. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    6

    Returns: 7

  62. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    7

    Returns: 9

  63. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    8

    Returns: 9

  64. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    9

    Returns: 11

  65. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    10

    Returns: 13

  66. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    11

    Returns: 13

  67. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    12

    Returns: 15

  68. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    13

    Returns: 0

  69. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    14

    Returns: 0

  70. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    15

    Returns: 0

  71. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    16

    Returns: 0

  72. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    17

    Returns: 0

  73. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    18

    Returns: 0

  74. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    19

    Returns: 0

  75. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    20

    Returns: 0

  76. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    21

    Returns: -14

  77. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    22

    Returns: -12

  78. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    23

    Returns: -12

  79. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    24

    Returns: -10

  80. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    25

    Returns: -8

  81. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    26

    Returns: -8

  82. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    27

    Returns: -8

  83. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    28

    Returns: -8

  84. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    29

    Returns: -6

  85. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    30

    Returns: -4

  86. "ACFAPCKKBNNLOOLOJKAAKGCCMHIDHDEI"

    31

    Returns: -2

  87. "ACFAPCKKBNNLLLLOJKAAKGCCMHIDHDEI"

    13

    Returns: 15

  88. "ACFAPCKKBNNLLLLOJKAAKGCCMHIDHDEI"

    14

    Returns: 15

  89. "ACFAPCKKBNNLLLLOJKAAKGCCMHIDHDEI"

    15

    Returns: 15

  90. "ACFAPCKKBNNLLLLOJKAAKGCCMHIDHDEI"

    16

    Returns: 0

  91. "DOLPHINIGLE"

    4

    Returns: 7

  92. "DOLPHINIGLE"

    7

    Returns: -8

  93. "DOLPHINIGLE"

    6

    Returns: 0

  94. "DOLPHINIGLE"

    5

    Returns: 0

  95. "ABCDE"

    3

    Returns: -4

  96. "ABCCD"

    3

    Returns: 0

  97. "ABCCDEFG"

    3

    Returns: 5

  98. "OP"

    1

    Returns: 1

  99. "PP"

    1

    Returns: 0

  100. "IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII"

    37

    Returns: 0

  101. "IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII"

    1

    Returns: 0

  102. "IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII"

    49

    Returns: 0

  103. "ABGAABCD"

    3

    Returns: 0

  104. "ABCEFABD"

    5

    Returns: 0

  105. "ABCDEFGHIJKLMOPEFGHIJKLMOPHIJKLMOAAAAAAAALLMOPEFGH"

    25

    Returns: 0

  106. "ABDCEFGHIJKLMNOPOPAKBJMNFEHI"

    14

    Returns: 0

  107. "ABCDDDDDAPABCDDDDAPABCDDABDAPABCDDDEAPABCDDDDDAP"

    25

    Returns: 0

  108. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP"

    15

    Returns: 0

  109. "AAABCD"

    2

    Returns: 1

  110. "ABCDEHPABCDLMNO"

    7

    Returns: 0

  111. "ABAC"

    2

    Returns: 0

  112. "IPMOFECNMELGIGELPEPLDLLFFPNKHELNDBLCNAMMAGCDHKDJEE"

    1

    Returns: 1

  113. "AJHIDDENMLBJEFFPODFGLMNGHEIJFJBMNLBCDDEDAGFE"

    23

    Returns: 0

  114. "AB"

    1

    Returns: 1

  115. "ABCDEDEFGHK"

    5

    Returns: 0

  116. "ABCDEFCBA"

    6

    Returns: 0

  117. "ABCDEFGHIJKLABCDEFGHIJKLMN"

    12

    Returns: 0

  118. "ABCDEFGHIJKLMNPPNMLKJIHGFEDCBA"

    16

    Returns: 0

  119. "CCCCCCCCCCCCCCABAPDCAACCCCCCCDDDDDDDDDDDCCCCCCCCCC"

    25

    Returns: -4

  120. "ABCA"

    3

    Returns: -2

  121. "OCAJBBLJLDGLMHMOJEONMGHHODCNIDLLGPDKNJIFP"

    14

    Returns: 0

  122. "ABCDAB"

    4

    Returns: 0

  123. "ADBCIFGFGDE"

    7

    Returns: 0

  124. "ABCDBCDEF"

    4

    Returns: 0

  125. "ABCDEFGHIJKLMNOLKJIHGFEDCBA"

    7

    Returns: 13

  126. "ADCCB"

    3

    Returns: 0

  127. "ABCDEFGHIJKLMNOAAAAAABCDEFGHIJKLMNOP"

    18

    Returns: 0

  128. "DOEBMGOCAJBBLJLDGLMHMOJEONMGHHODCNIDLLGPDKN"

    34

    Returns: -14

  129. "AAAAAAACCCCCCCCCCAAABBDEFHIJKLMOPACBBBBBBBB"

    25

    Returns: 11

  130. "ABABC"

    2

    Returns: 0

  131. "ABCDAAAE"

    3

    Returns: 0

  132. "ABAPDEACCCCAAABCDFHIJKLAABB"

    13

    Returns: 11

  133. "ABCDECDE"

    5

    Returns: 0

  134. "PCGDPBNCCHMGNHIJOGFCCOGGIAEAFNOOJHAMCDHFPCDGIAOFNM"

    24

    Returns: 0

  135. "ABCDEFGHIIIIIIIIABCDEFGHIJKLMNOP"

    10

    Returns: 0

  136. "ABCABCD"

    3

    Returns: 0

  137. "ABCDEFGHIJKLMNOPPONMLKJIHGFEDCBAPMNABCDJKIPMED"

    8

    Returns: 15

  138. "ABCDEFGHIJKLMNABCDEFGHIJKLMNOP"

    14

    Returns: 0

  139. "ABDEDEC"

    4

    Returns: 0

  140. "AAAAAAAA"

    7

    Returns: 0

  141. "DABCD"

    4

    Returns: -2

  142. "ABCDEFGABCD"

    7

    Returns: 0

  143. "ABDEDECFG"

    4

    Returns: 0

  144. "ABA"

    2

    Returns: 0

  145. "NGLEEBOCEBBNMHAJOBBBMHOBOHKMLGPIMKMALLCPMEMILMC"

    32

    Returns: 0

  146. "ABCDCDEFG"

    4

    Returns: 0

  147. "ABGHIIHGCDEF"

    5

    Returns: 0

  148. "ABCBCDE"

    3

    Returns: 0

  149. "ABCDEC"

    3

    Returns: 0

  150. "DEPIPJIMAJMAKCHDKJDOLLEHIHFEEDNDGBGBCEDFKMEPLIPOML"

    41

    Returns: -12

  151. "AAAAADBAC"

    7

    Returns: 0

  152. "AAAAAAA"

    2

    Returns: 0

  153. "ABCDEDCE"

    5

    Returns: 0

  154. "ABCDDEFGHI"

    4

    Returns: 7

  155. "ABCDEFGHIJJIH"

    10

    Returns: -6

  156. "ABACBA"

    3

    Returns: 0

  157. "BCDEFGHIJKLMNONOHIJKJOCBCBDJA"

    15

    Returns: 0

  158. "ABA"

    1

    Returns: 1

  159. "ABDCFGFGDE"

    7

    Returns: -6

  160. "ABCAB"

    2

    Returns: 0

  161. "ABCCEFPD"

    5

    Returns: -6

  162. "ABCCBDE"

    3

    Returns: 0

  163. "ABPAKLABKLAKLFEKLALBKGKLHG"

    10

    Returns: 0

  164. "ABCDEABPPPP"

    5

    Returns: 0

  165. "ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPAB"

    25

    Returns: 0

  166. "AIKMMJPEECBOMKDNCMIMBBHGGAHCJHCGFALADHOPFDNCBMGMNM"

    5

    Returns: 7

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: