Statistics

Problem Statement for "WeighCoins"

Problem Statement

We have N <= 62 coins. The coins are labeled by the first N characters of the string "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789" (uppercase A-Z, lowercase a-z, digits).

E.g., for N=3 the three coins are 'A', 'B', 'C', and for N=27 we have 26 coins labeled 'A'-'Z' and then a coin labeled 'a'.


As in many other weighing problems, in our setting exactly one of the coins is counterfeit and all others are real. All real coins share the same weight, the counterfeit coin differs. The goal is to determine two things: which coin is counterfeit and whether it's lighter or heavier than the real ones.

We can weigh the coins using a balance scale. When weighing, we can place some coins onto the left scale, other coins onto the right scale, and look what happens. The weighing has three possible results: '<' (left scale is lighter), '=' (both scales have the same weight), and '>' (left scale is heavier).


We have already made some weighings. They are recorded in the String[]s L and R and in the String result. For each valid index i, we placed the coins from L[i] onto the left scale, the coins from R[i] onto the right scale, and we got the outcome result[i].


Compute and return the minimum number of additional weighings needed to determine which coin is counterfeit and whether it's lighter or heavier than the real ones.

Definition

Class:
WeighCoins
Method:
solve
Parameters:
int, String[], String, String[]
Returns:
int
Method signature:
int solve(int N, String[] L, String result, String[] R)
(be sure your method is public)

Notes

  • The weight of each coin is positive.
  • For the given constraints the label and type of the counterfeit coin can always be determined by making all possible weighings, thus the return value always exists.

Constraints

  • N will be between 3 and 62, inclusive.
  • L will have between 0 and 50 elements, inclusive.
  • result and R will each have the same length as L.
  • Each character in L and R will be a valid coin label.
  • For each i, L[i] and R[i] will be disjoint.
  • For each i, L[i] and R[i] will have the same positive length.
  • Each character in result will be less-than, equals, or greater-than.
  • L, R and result will be consistent with at least one possibility for the label and weight of the counterfeit coin.

Examples

  1. 12

    {}

    ""

    {}

    Returns: 3

    This is a well-known puzzle. Solving it in just three weighings is doable but nowhere near easy.

  2. 3

    {"A","A"}

    "<<"

    {"B","C"}

    Returns: 0

    We have three coins. We already did two weighings and we learned A is lighter than both B and C. The only way that's possible is that A is a counterfeit coin and it's lighter than the real ones. As we already have our answer, we don't need any additional weighings.

  3. 12

    {"ABCD"}

    ">"

    {"EFGL"}

    Returns: 2

    This is a useful first step when solving the puzzle from example 0.

  4. 3

    {"B","C","B","C"}

    "===="

    {"C","B","C","B"}

    Returns: 1

    There can be multiple redundant weighings. In this test case we already know that A must be the counterfeit coin, but we still need one more weighing to tell whether it's heavier or lighter than the real ones.

  5. 61

    {}

    ""

    {}

    Returns: 5

  6. 62

    {"1234567890qwerty","QWERTYUIOP","12VB","V"}

    "<=<="

    {"uiopasdfghjklzxc","ASDFGHJKLZ","vbnm","B"}

    Returns: 1

    Either the coin labeled '1' or the coin labeled '2' is counterfeit. Additionally, we are already sure that the counterfeit coin is lighter than the real ones. The search can now be concluded quickly: e.g., weigh coins '1' and '2' against each other and claim that the lighter of the two is the too-light counterfeit.

  7. 3

    {}

    ""

    {}

    Returns: 2

  8. 56

    {}

    ""

    {}

    Returns: 5

  9. 3

    {"A"}

    "="

    {"B"}

    Returns: 1

  10. 62

    {"V"}

    "="

    {"D"}

    Returns: 5

  11. 3

    {"B"}

    ">"

    {"C"}

    Returns: 1

  12. 53

    {"M"}

    ">"

    {"x"}

    Returns: 1

  13. 3

    {"A"}

    "<"

    {"C"}

    Returns: 1

  14. 59

    {"J"}

    "<"

    {"C"}

    Returns: 1

  15. 3

    {"C", "C"}

    "<="

    {"B", "A"}

    Returns: 0

  16. 56

    {"j", "j"}

    "<="

    {"p", "k"}

    Returns: 0

  17. 4

    {"AB"}

    ">"

    {"CD"}

    Returns: 2

  18. 58

    {"hW"}

    ">"

    {"cJ"}

    Returns: 2

  19. 4

    {}

    ""

    {}

    Returns: 3

  20. 56

    {}

    ""

    {}

    Returns: 5

  21. 4

    {"DC"}

    "<"

    {"AB"}

    Returns: 2

  22. 52

    {"TB"}

    "<"

    {"mJ"}

    Returns: 2

  23. 4

    {"A"}

    "<"

    {"C"}

    Returns: 1

  24. 56

    {"P"}

    "<"

    {"Q"}

    Returns: 1

  25. 4

    {"B"}

    "="

    {"D"}

    Returns: 2

  26. 54

    {"L"}

    "="

    {"v"}

    Returns: 5

  27. 5

    {"EA", "D"}

    "<>"

    {"BC", "E"}

    Returns: 0

  28. 58

    {"hH", "p"}

    "<>"

    {"qf", "h"}

    Returns: 0

  29. 5

    {}

    ""

    {}

    Returns: 3

  30. 51

    {}

    ""

    {}

    Returns: 5

  31. 5

    {"DE", "BA"}

    "><"

    {"BC", "CE"}

    Returns: 1

  32. 56

    {"gS", "pM"}

    "><"

    {"pw", "wS"}

    Returns: 1

  33. 5

    {"B"}

    "="

    {"A"}

    Returns: 2

  34. 57

    {"a"}

    "="

    {"A"}

    Returns: 5

  35. 5

    {"BC", "DC"}

    ">>"

    {"EA", "EA"}

    Returns: 1

  36. 57

    {"QZ", "IZ"}

    ">>"

    {"zy", "zy"}

    Returns: 1

  37. 10

    {"AG", "BE"}

    "=="

    {"HJ", "IA"}

    Returns: 2

  38. 59

    {"Ae", "hH"}

    "=="

    {"cZ", "iA"}

    Returns: 5

  39. 10

    {"JIH", "EIC"}

    "<>"

    {"FCD", "BJD"}

    Returns: 1

  40. 62

    {"TEm", "wEJ"}

    "<>"

    {"bJS", "tTS"}

    Returns: 1

  41. 10

    {"ABGHE", "AJGHC"}

    ">>"

    {"DFJCI", "DFBIE"}

    Returns: 2

  42. 50

    {"kfNBq", "keNBu"}

    ">>"

    {"KVeuQ", "KVfQq"}

    Returns: 2

  43. 10

    {"DJ"}

    "="

    {"HF"}

    Returns: 3

  44. 59

    {"Af"}

    "="

    {"tW"}

    Returns: 5

  45. 12

    {"LD"}

    ">"

    {"HK"}

    Returns: 2

  46. 53

    {"cp"}

    ">"

    {"Aa"}

    Returns: 2

  47. 13

    {"GH", "CHJ"}

    "=="

    {"FM", "FGK"}

    Returns: 3

  48. 55

    {"eZ", "dZy"}

    "=="

    {"ED", "Eet"}

    Returns: 5

  49. 13

    {"J", "KJMG"}

    "=="

    {"B", "DAEI"}

    Returns: 2

  50. 59

    {"y", "xym1"}

    "=="

    {"v", "uwdO"}

    Returns: 5

  51. 13

    {"FE", "GDMLI"}

    "><"

    {"MB", "JKBEH"}

    Returns: 1

  52. 57

    {"zF", "1TgVl"}

    "><"

    {"gA", "voAFr"}

    Returns: 1

  53. 13

    {"BJEG", "H"}

    "<="

    {"LFAK", "F"}

    Returns: 2

  54. 50

    {"cTEl", "g"}

    "<="

    {"Xfwr", "f"}

    Returns: 2

  55. 13

    {"JGI", "KC"}

    "=>"

    {"LBE", "EH"}

    Returns: 1

  56. 52

    {"TVv", "fh"}

    "=>"

    {"zug", "gO"}

    Returns: 1

  57. 8

    {}

    ""

    {}

    Returns: 3

  58. 50

    {}

    ""

    {}

    Returns: 5

  59. 12

    {}

    ""

    {}

    Returns: 3

  60. 54

    {}

    ""

    {}

    Returns: 5

  61. 13

    {}

    ""

    {}

    Returns: 4

  62. 59

    {}

    ""

    {}

    Returns: 5

  63. 39

    {}

    ""

    {}

    Returns: 4

  64. 52

    {}

    ""

    {}

    Returns: 5

  65. 40

    {}

    ""

    {}

    Returns: 5

  66. 56

    {}

    ""

    {}

    Returns: 5

  67. 20

    {"O", "LF", "LCDHNPSQA", "LDJETNPOK", "JRKQBA"}

    "==<<="

    {"D", "NQ", "JRGEFOKBM", "CRGHIQBMA", "CDGESF"}

    Returns: 1

  68. 54

    {"E", "xo", "xdUCvKp1O", "xUbPDvKEu", "bFu1AO"}

    "==<<="

    {"U", "v1", "bFVPoEuAZ", "dFVCH1AZO", "dUVPpo"}

    Returns: 1

  69. 20

    {"RLJD", "GETCMASNLQ", "EFAKOJP", "HTD", "EHMKBJ"}

    "=><=>"

    {"CMKB", "HFKRBOIJDP", "GTMILQD", "RIN", "GTFNQD"}

    Returns: 0

  70. 59

    {"QW6Y", "pmTtHuAaWB", "mOuUJ6P", "wTY", "mwHUg6"}

    "=><=>"

    {"tHUg", "wOUQgJI6YP", "pTHIWBY", "QIa", "pTOaBY"}

    Returns: 0

  71. 20

    {"JI", "BHACFG", "DSLCNPM", "K", "SKC"}

    "==<=="

    {"SO", "DRKNQI", "RBAOJEF", "G", "ONG"}

    Returns: 2

  72. 60

    {"HB", "N0LERG", "cwxEUqe", "i", "wiE"}

    "==<=="

    {"wC", "cMiU2B", "MNLCHIR", "G", "CUG"}

    Returns: 2

  73. 20

    {"TSAREFHCOD", "TSAIQBHMGL", "TIBFHNLP", "F", "IRQOGKP"}

    "<>>=>"

    {"IQBNMGKLJP", "REFNCODKJP", "EMCODGKJ", "K", "TABEFHM"}

    Returns: 1

  74. 56

    {"D2pTyXlihR", "D2pUL3lWGf", "DU3Xlofk", "X", "UTLhGmk"}

    "<>>=>"

    {"UL3oWGmfQk", "TyXoihRmQk", "yWihRGmQ", "m", "Dp3yXlW"}

    Returns: 1

  75. 20

    {"RTEHISOQ", "RJIO", "F", "LD", "RKMCSL"}

    ">===<"

    {"BKPMGADN", "PALF", "K", "MA", "TGEANQ"}

    Returns: 1

  76. 58

    {"KGsPqIVh", "KFqV", "z", "er", "KpnNIe"}

    ">===<"

    {"Qptniorv", "toez", "p", "no", "Gisovh"}

    Returns: 1

  77. 30

    {"ILFbMDPTCKZGd", "Qd", "BMYA", "JMHR", "NLBUMQOPT"}

    "<===="

    {"NEJaBURQOSVWc", "TK", "XbRG", "IXUA", "EaFRADCZG"}

    Returns: 2

  78. 59

    {"y5KlD4sBXqRQ1", "m1", "oDfr", "CDkp", "N5oMDmusB"}

    "<===="

    {"NgCLoMpmuv0EI", "Bq", "alpQ", "yaMr", "gLKpr4XRQ"}

    Returns: 2

  79. 30

    {"GdRLcUaZIPJBH", "bdcXOWZDB", "TPJ", "CTbdcUOWFNIPJH", "dcYUMSKH"}

    "<==<<"

    {"CTQEXYOWDFNVA", "CQGaNIMSA", "dRX", "QGERLXYaZDVAKB", "QbROZFAB"}

    Returns: 1

  80. 62

    {"pIhP4GO6AHkVr", "BI4F7y6TV", "dHk", "8dBI4G7yJmAHkr", "I4EG3uMr"}

    "<==<<"

    {"8d2gFE7yTJmzs", "82pOmA3us", "IhF", "2pghPFEO6TzsMV", "2Bh76JsV"}

    Returns: 1

  81. 30

    {"Ja", "EX", "I", "dXSa", "TKOPI"}

    "====="

    {"bS", "QM", "L", "VOCW", "bXCSA"}

    Returns: 3

  82. 55

    {"Jx", "Uh", "f", "ThIx", "mDENf"}

    "====="

    {"uI", "rk", "o", "lESF", "uhSIz"}

    Returns: 4

  83. 30

    {"MWOJTdNC", "YLEIGaBOUSKPQ", "AMYGWaBUJZNKPcV", "MYEIGDWBZPHCcV", "FEGbWBOUTSdNPHc"}

    "=>><>"

    {"AIbRaPHc", "AMFDWRJTdNXCc", "FLEIDbROTSdXHCQ", "FLbRaOUJTSdNKX", "AMYLIDRaJZKXCVQ"}

    Returns: 1

  84. 50

    {"CbXBPgDZ", "uTFHkiVXowfMG", "rCukbiVoBeDfMvd", "CuFHkWbVeMRZvd", "lFkjbVXoPwgDMRv"}

    "=>><>"

    {"rHjciMRv", "rClWbcBPgDNZv", "lTFHWjcXPwgNRZG", "lTjciXoBPwgDfN", "rCuTHWciBefNZdG"}

    Returns: 1

  85. 30

    {"CdaVHYX", "FEVbBIHR", "CEaQbUBYXc", "daQJ", "MHZKX"}

    "<===>"

    {"FELGROZ", "CUGJTDYN", "WFMVLGIRPT", "ESUI", "dEabG"}

    Returns: 0

  86. 53

    {"QKBZPrG", "DNZLxbPF", "QNBWLJxrGs", "KBWT", "YPCOG"}

    "<===>"

    {"DNeuFlC", "QJuTtSrg", "MDYZeubFIt", "NmJb", "KNBLu"}

    Returns: 0

  87. 40

    {"PCc", "RaK", "RmMEaPOKDQnGYce", "RmEkdQCUXJSe", "RhTakFBAKDNnWGYcgfL"}

    "==><>"

    {"kje", "DNH", "TiFINHWCZjlXJgS", "MVIDNHnjYlcL", "mMEibPVIOHCZjUlXJSe"}

    Returns: 2

  88. 53

    {"zpk", "fhA", "fGLjhzqAdrVSYka", "fGjJOrpWvsla", "fBthJcRbAdiVFSYkMom"}

    "==><>"

    {"Jya", "die", "tCcKieFpNywvsMl", "LgKdieVyYwkm", "GLjCTzgKqepNyWwvsla"}

    Returns: 2

  89. 40

    {"QmEAXU"}

    "="

    {"DOBVgG"}

    Returns: 4

  90. 52

    {"PQaAxh"}

    "="

    {"wjrCJX"}

    Returns: 4

  91. 40

    {"HBQ", "Xf", "FcSZiQXlYm", "nOgaIDYdm"}

    "<=<="

    {"KXJ", "OW", "OGEKNMfbUW", "FGHSNZBCb"}

    Returns: 1

  92. 55

    {"Vcn", "Bp", "OIyqsnBuih", "MXNxZYiLh"}

    "<=<="

    {"gBr", "Xb", "XzRgw2ptmb", "OzVywqcGt"}

    Returns: 1

  93. 40

    {"CjFeMdAfKZbEImBSkLhW", "DedaXISiRW"}

    ">="

    {"DlGVaPNOXYgHJUiTQcRn", "ClFNOKmkhn"}

    Returns: 3

  94. 62

    {"nyc1HzuYI6rXPJNeTQW7", "O1zokPeA57"}

    ">="

    {"OpCwoi9tkDx2dsAbUl5f", "npc9tIJTWf"}

    Returns: 3

  95. 40

    {"BOQ", "SHDLG", "ESfKHhabZnmdOIeGFgU", "ESHJbnl", "ESTKPbmXOM", "BAWaDnmOIQlYR", "SiBWKPHJanXVLGRg", "NKDbdIleYFCU", "BfTcMk"}

    "==<=>=><="

    {"iWF", "JabZR", "BNTAjWPJDcXVLMklYRC", "KhcVIYg", "BWJhcVklRU", "ETjKPhZXLkGFC", "NfAhDcbZmOkQeYCU", "SBfAanVLkQGg", "KHanIl"}

    Returns: 0

  96. 57

    {"lIh", "MaXHx", "fMWbaOLoQ1TYIgsxdBK", "fMazo1t", "fMkbqoTFIA", "lEyLX1TIghtNV", "MplybqazL1FnHxVB", "rbXoYgtsNdjK", "lWkJAe"}

    "==<=>=><="

    {"pyd", "zLoQV", "lrkEUyqzXJFnHAetNVj", "bOJngNB", "lyzOJnetVK", "fkUbqOQFHexdj", "rWEOXJoQTIehsNjK", "MlWEL1nHehxB", "baL1gt"}

    Returns: 0

  97. 50

    {}

    ""

    {}

    Returns: 5

  98. 50

    {}

    ""

    {}

    Returns: 5

  99. 50

    {"MxXYEtkdNmsSnTrbPZQeoJVv"}

    "="

    {"qDIHUCOAwLgjRhBWcpliuFGK"}

    Returns: 2

  100. 54

    {"NaBnOwqTxAfbszEiXmuICUoV"}

    "="

    {"PZSJMveykYWl0gFdKrjLcRpt"}

    Returns: 3

  101. 50

    {"HsVKWStb", "fkOHlnsTDBUqZEKAtv", "jiLlMrpdDPqmKRNb"}

    "=><"

    {"iulFdhcw", "jiIJLVrFpaQPXRScwC", "eusVTBXhGESctwCg"}

    Returns: 2

  102. 52

    {"YErkoqjg", "tHwYVTESfxBWUskije", "pAZVFvGmfuWnkROg"}

    "=><"

    {"APVdmczy", "pAQbZrvdGLCuDRqzyJ", "NPErSxDcXsqzjyJK"}

    Returns: 2

  103. 50

    {"TnHipQVq", "sMZkJHwfEhmSoVKWgIvU", "rkTtiCEhoeQKWPGcqbIYU"}

    "=<<"

    {"atdxjAFL", "aOltxDjApNeQuGXcFLqb", "alJnxHDwfjmpSNVuRgFLB"}

    Returns: 3

  104. 60

    {"Fe3BHiIq", "2srnA3UwGTlVfIRMJxZN", "tnF5BvGTfCiRM0yOqzx6N"}

    "=<<"

    {"Q5E7Lubo", "QWP57gLuHkCiSyYOboqz", "QPAe73gUwLlHVkISDJboh"}

    Returns: 3

  105. 50

    {"t", "E", "B", "X", "A", "T", "p", "W", "a", "J", "G", "w", "M", "L", "i", "O", "c", "Q", "Z", "r", "b", "U", "F", "q", "o", "S", "I", "m", "f", "u", "P", "Y", "j", "C", "x", "V", "h", "l", "N", "D", "d", "v", "K", "n", "g", "e", "k", "H"}

    "================================================"

    {"E", "B", "X", "A", "T", "p", "W", "a", "J", "G", "w", "M", "L", "i", "O", "c", "Q", "Z", "r", "b", "U", "F", "q", "o", "S", "I", "m", "f", "u", "P", "Y", "j", "C", "x", "V", "h", "l", "N", "D", "d", "v", "K", "n", "g", "e", "k", "H", "R"}

    Returns: 1

  106. 53

    {"o", "c", "T", "t", "F", "b", "m", "w", "A", "x", "S", "u", "K", "g", "J", "V", "W", "n", "P", "v", "r", "B", "h", "e", "L", "Z", "k", "H", "I", "y", "d", "N", "f", "G", "p", "s", "i", "q", "R", "U", "z", "Y", "Q", "M", "l", "0", "E", "C"}

    "================================================"

    {"c", "T", "t", "F", "b", "m", "w", "A", "x", "S", "u", "K", "g", "J", "V", "W", "n", "P", "v", "r", "B", "h", "e", "L", "Z", "k", "H", "I", "y", "d", "N", "f", "G", "p", "s", "i", "q", "R", "U", "z", "Y", "Q", "M", "l", "0", "E", "C", "j"}

    Returns: 2

  107. 13

    { }

    ""

    { }

    Returns: 4

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: