Statistics

Problem Statement for "MagicalHats"

Problem Statement

A magician has challenged you to a game of wits. First he shows you some coins. Different coins may have different values. Next he takes some hats and hides all the coins inside the hats, in such a way that no two coins are hidden in the same hat. Finally, he places each of the hats with their respective coin onto some cell of a checkerboard. Now he has given you some guesses. In each guess you may ask the magician to reveal the contents of one of the hats.

After you make your guess, but before he reveals the contents of a hat, the magician may magically reshuffle all coins that are still hidden. That is, he can use a magic spell to redistribute the coins among all hats that still were not revealed, including the hat you just selected. After reshuffling, each hat must again contain at most one coin.

After you make a guess and the magician reshuffles the hidden coins, the hat you selected is flipped upside down (and remains in this state until the end of the game). If it contained a coin, the coin remains in the hat, but it is now visible and the magician cannot move it in the future. If it did not contain a coin, the magician can't ever put a coin into this hat anymore.

Furthermore, the magician has given you one more set of guarantees. At any moment in the game, the following constraints will all be satisfied:
  • For each row, the number of hats in the row plus the number of coins in the row will be an even number.
  • For each column, the number of hats in the column plus the number of coins in the column will be an even number.
You are given a String[] board representing the checkerboard. The j-th character of the i-th element of board is 'H' when there is a hat at row i column j of the checkerboard and '.' otherwise. You are also given an int[] coins representing the different coins that are hidden under hats. You are also given an int numGuesses representing the number of guesses that you get.

At the end of the game you get to keep all the coins that were revealed while playing. Your goal is to maximize the total value of the coins you get. The magician's goal is to minimize the total value of the coins you get. If it is not possible to hide all the coins in coins under the hats on the given board while meeting all the constraints above, return -1. Otherwise, return the total value of coins you'll get, assuming both you and the magician play optimally.

Definition

Class:
MagicalHats
Method:
findMaximumReward
Parameters:
String[], int[], int
Returns:
int
Method signature:
int findMaximumReward(String[] board, int[] coins, int numGuesses)
(be sure your method is public)

Constraints

  • board will contain between 1 and 13 elements, inclusive.
  • Each element of board will contain between 1 and 13 characters, inclusive.
  • Each element of board will contain the same number of characters.
  • Each character of each element of board will be either 'H' or '.'.
  • board will contain at most 13 occurrences of the character 'H'.
  • coins will contains between 1 and 13 elements, inclusive.
  • Each element of coins will be between 1 and 10,000, inclusive.
  • There will always be at least as many 'H' characters in board as elements in coins.
  • numGuesses will be between 1 and the number of 'H' characters in board, inclusive.

Examples

  1. {"H"}

    {1}

    1

    Returns: 1

    One guess for one hat. The reward is just the contents of the hat.

  2. {"HHH", "H.H", "HH."}

    {9}

    1

    Returns: 9

    The only position the 9 coin can possibly be in is the top left corner.

  3. {"HH", "HH"}

    {1,2,3,4}

    3

    Returns: 6

    The magician manages to always give you the worst possible reward regardless of how you guess.

  4. {"HHH", "HHH", "H.H"}

    {13,13,13,13}

    2

    Returns: 13

  5. {"HHH", "HHH", "H.H"}

    {13,13,13,13}

    3

    Returns: 26

  6. {"H.H.", ".H.H", "H.H."}

    {17}

    6

    Returns: -1

  7. {"HHH", "HHH", "H.H"}

    {13,13,13,13}

    1

    Returns: 0

  8. {"HH.....", ".HH....", "..HH...", "...HH..", "....HH.", ".....HH", "......H"}

    {1,3,5,7}

    5

    Returns: -1

  9. {"HH.....", ".HH....", "..HH...", "...HH..", "....HH.", ".....HH", "......H"}

    {101,102}

    3

    Returns: -1

  10. {"HH.", ".HH"};

    {3,3,3,3}

    2

    Returns: 6

  11. {"HH.....", ".HH....", "..HH...", "...HH..", "....HH.", ".....HH", "......H"}

    {1,3,5,7,9,11,13,15,17,19,21,23,25}

    4

    Returns: 16

  12. {"HH.....", ".HH....", "..HH...", "...HH..", "....HH.", ".....HH", "......H"}

    {1,3,5,7,9,11,13,15,17,19,21,23,25}

    13

    Returns: 169

  13. {"H............", ".H...........", "..H..........", "...H.........", "....H........", ".....H.......", "......H......", ".......H.....", "........H....", ".........H...", "..........H..", "...........H.", "............H"}

    {1,3,5,7,9,11,13,15,17,19,21,23,25}

    7

    Returns: 49

  14. {"HHH", "H.H", "HHH", "H.H", "HHH"}

    {3,5,7}

    3

    Returns: 3

  15. {"HHH", "H.H", "HHH", "H.H", "HHH"}

    {33,337,1007,2403,5601,6003,9999}

    5

    Returns: 1377

  16. {"HHH", "H.H", "HHH", "H.H", "HHH"}

    {33,337,1007,2408,5601,6003,10000}

    7

    Returns: 9386

  17. {"HHH", "H.H", "HHH", "H.H", "HHH"}

    {33,66,1007,6003,9999}

    11

    Returns: 17108

  18. {".............", "......H......"}

    {13}

    1

    Returns: 13

  19. {".............", ".............", ".............", ".............", ".............", ".............", "......H......", ".............", ".............", ".............", ".............", ".............", "............."}

    {1}

    1

    Returns: 1

  20. {".............", ".............", ".............", ".............", ".............", ".............", "......H......", ".....HHH.....", "......H......", ".............", ".............", ".............", "............."}

    {999,999,999,9999,999}

    1

    Returns: 999

  21. {".............", ".............", ".............", ".............", ".............", ".............", ".....H.H.....", "......H......", ".....H.H.....", ".............", ".............", ".............", "............."}

    {22}

    3

    Returns: 22

  22. {".............", ".............", ".............", ".............", ".............", ".............", ".....H.H.....", "......H......", ".....H.H.....", ".............", ".............", ".............", "............."}

    {401}

    3

    Returns: 401

  23. {".............", ".............", ".............", ".............", "...H.....H...", "....H...H....", ".....H.H.....", "......H......", ".....H.H.....", "....H...H....", "...H.....H...", ".............", "............."}

    {101}

    1

    Returns: 101

  24. {".H.H.", "H.H.H", ".H.H."}

    {1,3,5}

    3

    Returns: 9

  25. {".H.H.", "H.H.H", ".H.H."}

    {9,9,9,9,9,9,9}

    7

    Returns: 63

  26. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {9,9,9,9,10000}

    2

    Returns: 18

  27. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {1,1,1,1,1,1,1,1,1}

    9

    Returns: 7

  28. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {1,9,9,9,9,11,11,11,11}

    2

    Returns: 10

  29. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {9,9,9,9,9,11,11,11,11}

    5

    Returns: 45

  30. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {9,9,9,9,9,11,11,11,11}

    6

    Returns: 45

  31. {".H.H.H.H.", "H.H.H.H.H", ".H.H.H.H."}

    {9999,9997,9995,9993,9991,9989,9987,9985,9983,9981,9971,9973,9975}

    11

    Returns: 109823

  32. {"....H.....", "...H.H....", "..H.H.H...", "...H.H....", "....H....."} ""}

    {7,3,5,3,1}

    4

    Returns: 12

  33. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {213,33,553,2323,4343}

    4

    Returns: 799

  34. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {1,3,5,7,9,3,55,77,11}

    4

    Returns: 7

  35. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {1,3,5,7,9,3,55,77,11}

    4

    Returns: 7

  36. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {1,3,5,7,9,3,55,77,11}

    7

    Returns: 19

  37. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {1,3,5,7,9,3,55,77,11}

    8

    Returns: 28

  38. {"...H.H...", "...H.H...", "..HHHHH..", "...H.H...", "...H.H..."}

    {1,3,5,7,9,3,55,77,11}

    11

    Returns: 171

  39. {".H...H", "H....H", "H...H.", ".H.HHH"}

    {1,1,1,1,1,3,3,3}

    2

    Returns: -1

  40. {".H...H", "H....H", "H...H.", ".H.HHH"}

    {99,99}

    2

    Returns: 198

  41. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {99}

    2

    Returns: 99

  42. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {9,9,9,9,9,99,99,99,99}

    2

    Returns: 9

  43. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {9,9,9,9,9,99,99,99,99}

    3

    Returns: 18

  44. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {9,9,9,9,9,99,99,99,99}

    4

    Returns: 27

  45. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {9,9,9,9,9,99,99,99,99}

    5

    Returns: 36

  46. {".H...H", "HH...H", "HH.HH.", ".H.HHH"}

    {9,9,9,9,9,99,99,99,99}

    6

    Returns: 45

  47. {"HHH"}

    {1,3,5}

    3

    Returns: 9

  48. {"H", "H", "H"}

    {1,2}

    1

    Returns: -1

  49. {"HHHHHHHHHHHHH"}

    {9999,9997,9995}

    3

    Returns: -1

  50. {"HHHHHHHHHHHHH"}

    {1,1,1,1,1,3,3,3,3,3,5,5,5}

    6

    Returns: 8

  51. {"HHH", "H.H", "HHH"}

    {1,1,1,1}

    1

    Returns: 0

  52. {"HHH", "H.H", "HHH"}

    {1,1,1,1}

    2

    Returns: 1

  53. {"HHH", "H.H", "HHH"}

    {1,1,1,1}

    4

    Returns: 2

  54. {"HHH", "H.H", "HHH"}

    {1,1,1,1}

    5

    Returns: 3

  55. {"HHH", "H.H", "HHH"}

    {1,1,1,1}

    6

    Returns: 4

  56. {"..H..H...H.HH", "..HHH........", "..H..HHH..H..", ".............", ".............", ".............", ".............", ".............", ".............", ".............", ".............", ".............", "............."}

    {689}

    9

    Returns: -1

  57. {"...H.........", ".............", ".H...H......H", ".......H.....", ".............", "............H", ".............", "..H......H...", "........H....", ".......H.....", "..H..........", "............H", "...H........."}

    {545, 84, 132, 220, 340, 344, 634, 120, 38, 990, 400, 144, 572}

    12

    Returns: 3573

  58. {"........HH...", "HH.H.....HH..", ".H.......H..H", ".............", "H..........H.", "............H", ".............", ".............", ".............", ".............", ".............", ".............", "............."}

    {633, 160, 38, 284, 278, 684, 512, 848, 982, 406, 592, 844, 386}

    1

    Returns: 38

  59. {"...........HH", ".......H.....", "...........HH", "......H...H..", "..H..........", ".............", ".............", ".....H......H", "......HH.....", ".H...........", ".............", ".............", "............."}

    {73, 166, 330, 898, 598, 312, 752, 16, 448, 758, 684, 802, 902}

    11

    Returns: 4939

  60. {".............", ".............", ".H.......H...", ".H...H.....H.", "....H........", ".............", ".......H....H", "..HH.H.H.....", "......H......", ".............", ".............", ".............", "............."}

    {321, 502, 4, 332, 142, 576, 110, 142, 998, 4, 40, 500, 564}

    6

    Returns: 442

  61. {".H...H.......", "...H..H......", "......H......", "H.H.....H...H", "......H......", ".....H.......", "........H....", ".....H.......", ".............", ".............", ".............", ".............", "............."}

    {97, 188, 780, 646, 240, 946, 58, 752, 490, 34, 534, 298, 926}

    1

    Returns: 34

  62. {"...........H.", ".H..........H", ".....HH......", ".............", "..HH....H....", "......H......", ".H.......H...", ".....H.......", "..H..........", ".............", ".............", ".............", "............."}

    {453, 946, 178, 640, 534, 32, 160, 920, 564}

    3

    Returns: -1

  63. {"........H....", "....H........", ".............", ".............", ".H....HH...HH", "........H....", "...H.........", "........H.H.H", ".............", ".............", ".............", "....H........", "............."}

    {657, 154, 956, 186, 506, 684, 102}

    11

    Returns: -1

  64. {".............", "..H..HH....H.", ".......H.....", ".H.....H..H..", ".H...........", ".............", "HH......H....", "..H..........", ".............", ".............", ".............", ".............", "............."}

    {653, 32, 402, 8, 472, 580, 316, 54, 904, 282}

    11

    Returns: -1

  65. {"HHH", "HHH", "HHH"}

    {5,9,13,15,17}

    4

    Returns: 14

  66. {"HHH", "HHH", "HHH"}

    {5,9,13,15,17}

    5

    Returns: 27

  67. {"HHH", "HHH", "HHH"}

    {5,9,13,15,17}

    6

    Returns: 42

  68. {"HHH", "HHH", "HHH"}

    {5,9,13,15,17}

    7

    Returns: 59

  69. {"HHH", "HHH", "HHH"}

    {5,9,13,15,17}

    8

    Returns: 59

  70. {"HHH", "HHH", "HHH"}

    {5,9,13,15,10000}

    9

    Returns: 10042

  71. {"HHH", "HHH", "HHH"}

    {10000,10000,10000,10000,10000,10000,10000,10000,10000}

    9

    Returns: 90000

  72. {"HHH.", "HHHH", "HHH."}

    {1001,1,1,1,1,1,1,1,1,1}

    9

    Returns: 9

  73. {"HHH.", "HHHH", "HHH."}

    {3,5,7,9}

    1

    Returns: 3

  74. {"HHH.", "HHHH", "HHH."}

    {3,5,7,9}

    2

    Returns: 3

  75. {"HHH.", "HHHH", "HHH."}

    {3,5,7,9}

    4

    Returns: 8

  76. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,11}

    1

    Returns: 1

  77. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,10000,4,6,8,11}

    3

    Returns: 8

  78. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,11}

    4

    Returns: 4

  79. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,11}

    5

    Returns: 9

  80. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,11}

    6

    Returns: 16

  81. {"HHH.", "HHHH", "HHH."}

    {9,7,5,3,1,11}

    7

    Returns: 25

  82. {".HHH.", "HHHHH", ".HHH."}

    {9,7,5,3,11}

    2

    Returns: 8

  83. {".HHH.", "HHHHH", ".HHH."}

    {9,7,5,3,11}

    5

    Returns: 15

  84. {".HHH.", "HHHHH", ".HHH."}

    {9,7,5,3,11}

    7

    Returns: 24

  85. {".HHH.", "HHHHH", ".HHH."}

    {9,7,5,3,11}

    6

    Returns: 15

  86. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {1,1,1,1,1,1,1,1,1,1,1,1,1}

    1

    Returns: 1

  87. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {1,1,1,1,1,1,1,1,1}

    2

    Returns: 2

  88. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {9,7,5,3,11,13,17}

    1

    Returns: 3

  89. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {9,7,5,3,11,13,17}

    2

    Returns: 8

  90. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {9,7,5,3,11,13,17}

    5

    Returns: 24

  91. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {9,7,5,3,11,13,17}

    6

    Returns: 24

  92. {"..H..", ".HHH.", "HHHHH", ".HHH.", "..H.."}

    {9,7,5,3,11,13,17}

    8

    Returns: 35

  93. {"H.H.H", ".H.H.", "H...H", ".H.H.", "H.H.H"}

    {9999,9999}

    1

    Returns: 0

  94. {"H.H.H", ".H.H.", "H...H", ".H.H.", "H.H.H"}

    {9999,9999}

    2

    Returns: 9999

  95. {"H.H.H", ".H.H.", "H...H", ".H.H.", "H.H.H"}

    {9999,9999}

    3

    Returns: 19998

  96. {"H.H.H", ".H.H.", "H...H", ".H.H.", "H.H.H"}

    {9999,9999}

    9

    Returns: 19998

  97. {"H.H.H", ".H.H.", "H...H", ".H.H.", "H.H.H"}

    {9999,9999,9999,9999,9999,9999}

    6

    Returns: 49995

  98. {"H.H.H", ".H.H.", "H.H.H", ".H.H.", "H.H.H"}

    {7,7,7,7,7,7,7}

    7

    Returns: 35

  99. {"H.H.H", ".H.H.", "H.H.H", ".H.H.", "H.H.H"}

    {1,3,5,7,9}

    3

    Returns: 1

  100. {".HH.H", ".H.H.", "H...H", ".H.H.", "H.HHH"}

    {1,3,5,9,11}

    4

    Returns: 9

  101. {".HH.H", ".H.H.", "H...H", ".H.H.", "H.HHH"}

    {1,3,5,9,11}

    5

    Returns: 18

  102. {"H.H.H", ".H.H.", "H.H.H", ".H.H.", "H.H.H"}

    {1,3,5,7,9}

    5

    Returns: 9

  103. {"HHHH","HHHH","HHH.","..HH"}

    {5691,5122,9927,5599,291}

    13

    Returns: 26630

  104. {"HHHH","HHHH","HHH.","..HH"}

    {5691,5122,9927,5599,291}

    9

    Returns: 26630

  105. {"HHHH","HHHH","HHH.","..HH"}

    {5691,5122,9927,5599,291}

    8

    Returns: 16703

  106. {"HHHH","H.HH","HHH.",".HHH","...."}

    {6920,5348,2014,899,1848}

    13

    Returns: 17029

  107. {"HHH.","HHHH","HH.H","HHH.","...."}

    {4235,4360,3744,5087,8501}

    13

    Returns: 25927

  108. {"HHHHH","HHHHH",".HHH."}

    {5699,3696,5806,9057,3517}

    13

    Returns: 27775

  109. {"HHH","HHH","HHH","HH.","HH."}

    {7236,2738,5991,1489,2818}

    13

    Returns: 20272

  110. {"H.HH","HH.H","H..H","H.HH"}

    {4941,8353,3698,4178,8772,7943,8567}

    6

    Returns: 20760

  111. {"H..H","H..H","HH..","HHHH","H.HH"}

    {8128,4681,2908,8498,8451,6814,3435,8726,8672}

    9

    Returns: 42915

  112. {"HHHH.","HHHH.","HHH.."}

    {4155,8425,8974,4261,9842,9879,6403}

    4

    Returns: 8416

  113. {"HHHH","HHHH",".HHH","H..H"}

    {5063,8062,900,8753,911,7004,3615,2211,9929}

    7

    Returns: 12700

  114. {"H.H","HH.","HHH","H.H"}

    {1492,2288,9019,8273,3646}

    5

    Returns: 7426

  115. {"HHHHH", "HHHHH" }

    {1, 2 }

    1

    Returns: 0

  116. {"H.HH", "HHH.", ".HHH", "HH.H" }

    {5676, 5672, 5684, 5678 }

    5

    Returns: 11348

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: