Statistics

Problem Statement for "OptimalMemoryGame"

Problem Statement

You have a deck of 52 cards. Each card has a single uppercase English letter ('A'-'Z'). Each letter is used exactly twice, so the deck contains 26 pairs of cards.


You are going to use the cards to play the memory game with your friends. You shuffled the deck of cards and placed them onto the table. The cards are arranged into a single row and they are all face-down (i.e., the letters on them are not visible).

The memory game is played in turns. In each turn, the active player starts by selecting one of the cards and turning it over. After seeing the letter on this card, the player then selects and turns over another card. If the two cards are distinct, they are turned face down again and the turn ends. If they form a pair, the player scores a point and takes those cards away from the table. Then, the player gets to repeat the whole process until they either reveal two cards that don't match, or find and remove the last pair of cards.


Some (possibly zero) turns of the game have already been played by other players. It is now your turn to play the game. There are 2*N cards still on the table.

(Note that during the game only pairs of matching cards are removed from the game, and thus it is guaranteed that those 2*N cards contain N pairs of matching cards.)


The String known represents what you currently know about the cards that are still in play. Each character represents one of the cards. If the character is a letter, you are certain that the card has that specific letter. Otherwise, the character is '-' (dash) and it means that you don't know anything about the card. (Maybe you haven't seen it, maybe you just forgot what it was.)


What is the maximum number of pairs you are guaranteed to find this turn, if you play the game optimally (i.e., in a way that maximizes this number)? Calculate and return this number of pairs.

Definition

Class:
OptimalMemoryGame
Method:
findPairs
Parameters:
String
Returns:
int
Method signature:
int findPairs(String known)
(be sure your method is public)

Notes

  • We want to stress that the two cards selected by the player are not selected at the same time. Instead, they are selected and revealed one at a time. When selecting the second card ("looking for a pair"), the player already knows what letter was on the first card they selected, and this information can influence the choice of the second card.

Constraints

  • N will be between 1 and 26, inclusive.
  • known will contain exactly 2*N characters.
  • Each character in known will be an uppercase English letter or a dash.
  • Each letter will appear at most twice in known.
  • There will be at most N distinct letters in known.

Examples

  1. "AEIOUIAEUO"

    Returns: 5

    All ten remaining cards have already been revealed and you know what they are. You can simply collect all pairs, one after another.

  2. "----------"

    Returns: 0

    The best you can do is flip some pair of cards. You aren't guaranteed that they will match. (In fact, it's likely that they won't.) Thus, you aren't guaranteed to find any pairs here, regardless of what strategy you use.

  3. "--------A----E-----IAO----U---"

    Returns: 1

    The pair of As is the only pair you can collect here. After you do so, you may get lucky and find another pair, but this isn't guaranteed to happen.

  4. "-X"

    Returns: 1

    Sometimes we can guarantee to find a pair even if we aren't actually given the positions of both cards in it. For example, here the only unknown card is clearly the second X, and once we know that, we can guarantee that we can find and collect a matching pair.

  5. "--"

    Returns: 1

  6. "-A-E-I-O-U"

    Returns: 5

  7. "-A-E-I-O-U--"

    Returns: 0

  8. "-A-EAIEOIUOU"

    Returns: 6

  9. "RAR-SES-TIT-VOV-WUW-"

    Returns: 10

  10. "DZOQ---G--EK-M--X-NVC-I-Y--WBR-ALJ----HS----T-PU--F-"

    Returns: 26

  11. "T----FH----R---Y---S-OKVP-W--X-CLDH-UI-EGMZ-JBNQ--A-"

    Returns: 26

  12. "LG-KICJ-Q---DT-O--XBVESH-BPIOFFYMTXJN-VLAW-DURMUY-Z-"

    Returns: 26

  13. "KQASIDLTLTUIRHOXN-WGSJRGOEP-NUMFEWCBPDHCJVMQVFYAYXZK"

    Returns: 26

  14. "YYUBOWSFZNVBTNRVGJPLXCQJTIGIMHAOXADKEKREMWLFSDCPZHUQ"

    Returns: 26

  15. "HXIGSSNZ-TXGPBYOLH-JDMJLAPMNRKYUTWZCOREVBCKUVQAWQIDE"

    Returns: 26

  16. "VWWZB-KAORQSRPYOFTLD-TISQJNCJUHMYKLDBMVEEZHFPCXNAIX-"

    Returns: 24

  17. "ABZVAQCKPVU-LTBIHYGWJNDSFZDFOKOWXYCU-PGX-QHEIML-METN"

    Returns: 23

  18. "IKGFLWEMAHL-JARCPESPHD-XOOWBIRNVTUBVTF-MXNKGSDYC-YUJ"

    Returns: 24

  19. "----------------------------------------------------"

    Returns: 0

  20. "D--I--OKQ-"

    Returns: 5

  21. "-FFQ--Q-"

    Returns: 2

  22. "RUZTRT-ZUD"

    Returns: 5

  23. "THR-TH"

    Returns: 3

  24. "IF--FW-IW-"

    Returns: 3

  25. "K---K-----"

    Returns: 1

  26. "HFJ--O---J"

    Returns: 1

  27. "NS---ME-EQ"

    Returns: 5

  28. "------X-"

    Returns: 0

  29. "W-GWI--C"

    Returns: 4

  30. "H-PHP-"

    Returns: 3

  31. "--Q--F-YI-"

    Returns: 0

  32. "----J-"

    Returns: 0

  33. "-----D"

    Returns: 0

  34. "-C-DND"

    Returns: 3

  35. "---Y-F-XAB"

    Returns: 5

  36. "-NY-H-"

    Returns: 3

  37. "--H-----"

    Returns: 0

  38. "-V-T--BH"

    Returns: 4

  39. "RXRDXKKD"

    Returns: 4

  40. "H--H----TL"

    Returns: 1

  41. "E-HHE-XRRX"

    Returns: 5

  42. "-E-G-LV-"

    Returns: 4

  43. "PPYHY-"

    Returns: 3

  44. "-O-EUOXE-X"

    Returns: 3

  45. "NS-F-FSAV-"

    Returns: 5

  46. "DDI-P-"

    Returns: 3

  47. "--I-----"

    Returns: 0

  48. "-GX-SL-H--"

    Returns: 5

  49. "--ZKZE"

    Returns: 3

  50. "--D-Y-GA-EVD-YUCF-ZNT--N"

    Returns: 12

  51. "----------Q---J-B--F"

    Returns: 0

  52. "--GZKGT-MMWDOKDOEZWIET"

    Returns: 9

  53. "--P--R--I--Q--ZX-PO--M-CSF--K-"

    Returns: 1

  54. "SRZ--N--JQAX-----SFR---I----Y--W"

    Returns: 2

  55. "D-AELH-----AREM-YGDH"

    Returns: 4

  56. "------------------------"

    Returns: 0

  57. "G-A----J-O-----N-A-X-S-L"

    Returns: 1

  58. "---K--AFV---------KGZ---HHLL"

    Returns: 3

  59. "CGYH-V-A----GH---------P-K-MSM----"

    Returns: 3

  60. "---KC-AGIO-P-Z---J-NEW--T-M-HB---RD--L"

    Returns: 19

  61. "-B-Y--ZRXGP-F----U-M-B--"

    Returns: 1

  62. "-----N---BBVOQ--W-----QC-----V------"

    Returns: 3

  63. "J--X---LG-TW--TP-WS-----F-KF-J"

    Returns: 4

  64. "-V-Y---N--VC-SM-C-S--N"

    Returns: 4

  65. "SOU-W-O----QVWSYVJT--N-H"

    Returns: 4

  66. "---------D--R-----H----------R------A-"

    Returns: 1

  67. "T--Q-----J-EOA--K-NEA-M-Y----Z-N-----Q"

    Returns: 4

  68. "-S---PK--S-----A--K-A-P---"

    Returns: 4

  69. "--P-UI-------RF-R--YMECTNL-ZG-"

    Returns: 1

  70. "W-VS-O-CQUJBICWJSXHB-PHNPKFIDNKMZYXVYQRGDTO-TZGMUR"

    Returns: 22

  71. "---I---G-Y--BNN-CXJIK--AR-Q--OV-JT--WPMU--"

    Returns: 3

  72. "--A-W-Y---I--K--N---D-O------LV-D---QC-JRXQ-F-RH"

    Returns: 3

  73. "Z-I-V-L-NI--B----NW-SDJBK-WXFF----R--TGCOH-E----"

    Returns: 5

  74. "IW-YKV-TEZ-U---D--C--SXOLAUXFH-FM-B-J--Y---B--"

    Returns: 5

  75. "OA-----R---C-DI--R--------OIPDF-L-H--B-SA---"

    Returns: 5

  76. "-W-J---FQA-ZO-M-B-WRIYLUX-KN-V--S-R-E-PZB-"

    Returns: 21

  77. "--I-------P---X-M----RMZ------DS--Q--------U----C---"

    Returns: 1

  78. "V-OF--ZD-T-C-Q---RJ----W--LBOI-PYASKU-E-S----H-X"

    Returns: 2

  79. "M-OCT--ILFGHUUWRA-K-CX-INYANVSPBJTO--FM-PVXRHL"

    Returns: 15

  80. "U-YH-LF-CVA----WQG----M-F-D-OT-N-AEIKZ-J---J"

    Returns: 3

  81. "--Z-O--WWESZ--T-YK-G-----R--OIVIEHKGT-RQF--AASQ-X--Y"

    Returns: 13

  82. "-Q-O---JH-SZY-CQ--YT-G-----BLN-ED----V--"

    Returns: 2

  83. "IGO-ARTAG-F-QDLS-KH-ZQ-ZJ-S-FDUXBI-UB-X---KVJHYTRYLP"

    Returns: 18

  84. "-WJ--O-L--XF-GK-MV--E----FH-I-A-ZP--S-M--Y---TCY"

    Returns: 3

  85. "-GG----FMN-X----IDTIX-W---MY--VZNW--F-C---"

    Returns: 7

  86. "G--R-DJ---OQAWZ---H--UB--FK-MS--X-P--Y--N-L-CI-E"

    Returns: 24

  87. "A-BEIW---LV-C-PMUEDQ-TR--PO-OSIHJV---BDZ-ZFG--"

    Returns: 8

  88. "-F--T-T--M--R-EN-ZR-M-H-PJ--E----F----------VG"

    Returns: 5

  89. "-EOAUIS-Y-K-PZAQ-QSCDLBZYP-RTHEIURF--DXL--XBT-----KO"

    Returns: 17

  90. "A--A"

    Returns: 2

  91. "-WA-"

    Returns: 2

  92. "--EX-DDY-ACE"

    Returns: 6

  93. "ABCD---D"

    Returns: 4

  94. "AABBCDE---"

    Returns: 5

  95. "BB--"

    Returns: 2

  96. "ABCD----"

    Returns: 4

  97. "-ZZAB-BA"

    Returns: 4

  98. "--AABBCC"

    Returns: 4

  99. "AB--"

    Returns: 2

  100. "--AB"

    Returns: 2

  101. "ABC---"

    Returns: 3

  102. "A-B-BA"

    Returns: 3

  103. "AAIO-K--"

    Returns: 4

  104. "AA--"

    Returns: 2

  105. "Y--X"

    Returns: 2

  106. "ABCAB--C"

    Returns: 4

  107. "AABBCCDDEEFFGG--IIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ"

    Returns: 26

  108. "----ABCD"

    Returns: 4

  109. "AABC--"

    Returns: 3

  110. "AABBCCDD----"

    Returns: 4

  111. "AZ--"

    Returns: 2

  112. "AABCDEF-----"

    Returns: 6

  113. "ABCDE-----"

    Returns: 5

  114. "----AABB"

    Returns: 2

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: