Statistics

Problem Statement for "EllysJuice"

Problem Statement

Elly's memories of last night's sleepover with her friends are rather blurry. She recalls that they played a game involving drinking orange and apple juice. In the beginning there were two identical bottles. One contained a gallon of orange juice, the other a gallon of apple juice. The game was played in turns, starting with turn zero. In even-numbered turns (turn 0, 2, 4, ...) the current player drank half of the remaining orange juice. In odd-numbered turns (turn 1, 3, 5, ...) the current player drank half of the remaining apple juice. The winner of the game is the player who drank the greatest total amount of liquid during the game. If multiple players are tied for the greatest amount, there is no winner.

For example, consider a game consisting of five turns. Suppose that the players to drink were, in order, Elly, Kriss, Stancho, Elly, and Stancho. (That is, Elly and Stancho both drank twice: Elly in turns 0 and 3, Stancho in turns 2 and 4.) In this game, Elly drank 0.75 gallons of liquid (0.5 gallons of orange juice and 0.25 of apple juice), Kriss drank 0.5 gallons of apple juice, and Stancho drank 0.375 gallons of orange juice (0.25 gallons in turn 2 and another 0.125 gallons in turn 4). In this game Elly would be the winner.

Elly knows all the people who played the game yesterday, and for each of them the number of times they drank. However, she remembers nothing about the order in which the players drank.

You are given a String[] players, containing the names of all players. If a player's name is contained X times in players that means that he or she drank exactly X times during the game. Determine all people who could have possibly won the game (for some particular order of turns). Return their names as a lexicographically sorted String[]. The return value should only contain each of the names once.

Definition

Class:
EllysJuice
Method:
getWinners
Parameters:
String[]
Returns:
String[]
Method signature:
String[] getWinners(String[] players)
(be sure your method is public)

Notes

  • A sequence of distinct Strings is sorted if each element is lexicographically smaller than all the ones following it.
  • String A is lexicographically smaller than String B if A contains smaller character at the first index where they differ. If there is no index where they differ, the shorter one is lexicographically smaller. For example "ariadne" is smaller than "elly", "abc" is smaller than "abd", "aaa" is smaller than "aaaaa", and "czzzzzzz" is smaller than "kaaaaaaa".

Constraints

  • players will contain between 1 and 8 elements, inclusive.
  • Each element of players will contain between 1 and 20 characters, inclusive.
  • Each element of players will consist only of lowercase English letters ('a'-'z').

Examples

  1. { "elly", "kriss", "stancho", "elly", "stancho" }

    Returns: {"elly", "stancho" }

    Elly would win for the order given in the problem statement. If Stancho and Elly swapped all their turns, Stancho would win the game. Kriss cannot win.

  2. {"torb", "elly", "stancho", "kriss"}

    Returns: { }

    In any valid game two of the four players would be tied for the lead (with half a gallon each).

  3. {"elly", "elly", "elly", "elly", "elly"}

    Returns: {"elly" }

    Since she was the only player, apparently she won.

  4. { "ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "elly" }

    Returns: {"ariadne", "elly", "stancho" }

    Although Stancho has drunk three times, there are orderings in which someone else wins.

  5. {"elly"}

    Returns: {"elly" }

    A sole winner.

  6. {"this", "test", "is", "really", "really", "evil"}

    Returns: {"really" }

  7. {"kriss", "elly", "kriss", "kriss", "elly", "kriss", "kriss", "kriss"}

    Returns: {"elly", "kriss" }

  8. {"aaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaab", "aaaaaaaaaaaaaaaaaaac", "aaaaaaaaaaaaaaaaaaad", "aaaaaaaaaaaaaaaaaaae", "aaaaaaaaaaaaaaaaaaaf", "aaaaaaaaaaaaaaaaaaag", "aaaaaaaaaaaaaaaaaaah"}

    Returns: { }

  9. {"aaaaaaaaaaaaaaaaaaaa", "aaaaaaaaaaaaaaaaaaab", "aaaaaaaaaaaaaaaaaaac", "aaaaaaaaaaaaaaaaaaad", "aaaaaaaaaaaaaaaaaaae", "aaaaaaaaaaaaaaaaaaaf", "aaaaaaaaaaaaaaaaaaag", "aaaaaaaaaaaaaaaaaaaa"}

    Returns: {"aaaaaaaaaaaaaaaaaaaa" }

  10. {"a", "aa", "aaa", "aaaa", "aaaa", "aaa", "aa", "a"}

    Returns: {"a", "aa", "aaa", "aaaa" }

  11. {"elly", "elly", "ariadne", "ariadne", "stancho", "stancho", "esprit", "esprit"}

    Returns: {"ariadne", "elly", "esprit", "stancho" }

  12. {"elly", "ariadne"}

    Returns: { }

  13. {"elly", "elly"}

    Returns: {"elly" }

  14. {"elly", "ariadne", "elly", "ariadne", "elly", "ariadne", "elly", "ariadne"}

    Returns: {"ariadne", "elly" }

  15. {"a", "b", "c", "a", "b", "c", "d", "nooooooooooooooooooo"}

    Returns: {"a", "b", "c" }

  16. {"ellie", "ellie", "ellie"}

    Returns: {"ellie" }

  17. {"torb", "torb", "torb", "torb", "elly", "torb"}

    Returns: {"torb" }

  18. {"ellie", "topcoder", "topcoder"}

    Returns: {"topcoder" }

  19. {"torb", "kriss", "esprit"}

    Returns: { }

  20. {"elly", "torb", "kriss", "ellie", "topcoder", "elly", "topcoder"}

    Returns: {"elly", "topcoder" }

  21. {"ellie", "topcoder", "kriss", "kriss", "ellie"}

    Returns: {"ellie", "kriss" }

  22. {"ellie", "ellie", "topcoder", "elly"}

    Returns: {"ellie" }

  23. {"topcoder", "torb", "elly"}

    Returns: { }

  24. {"esprit", "kriss", "ariadne", "ellie", "ellie", "ellie"}

    Returns: {"ellie" }

  25. {"torb", "esprit", "ariadne", "stancho", "topcoder", "stancho", "elly"}

    Returns: {"stancho" }

  26. {"stancho", "ariadne", "torb", "torb", "torb", "torb", "stancho", "ariadne"}

    Returns: {"ariadne", "stancho", "torb" }

  27. {"topcoder", "torb", "topcoder"}

    Returns: {"topcoder" }

  28. {"stancho", "torb", "stancho"}

    Returns: {"stancho" }

  29. {"elly", "kriss", "elly", "elly", "ariadne"}

    Returns: {"elly" }

  30. {"esprit", "stancho", "ellie"}

    Returns: { }

  31. {"ariadne", "ariadne", "esprit", "esprit"}

    Returns: {"ariadne", "esprit" }

  32. {"esprit", "esprit", "esprit", "ariadne", "esprit"}

    Returns: {"esprit" }

  33. {"elly", "elly", "torb", "esprit", "topcoder", "kriss", "topcoder", "ellie"}

    Returns: {"elly", "topcoder" }

  34. {"topcoder", "ellie", "topcoder"}

    Returns: {"topcoder" }

  35. {"elly", "torb", "elly", "esprit"}

    Returns: {"elly" }

  36. {"esprit", "topcoder", "topcoder", "esprit", "torb", "esprit", "kriss"}

    Returns: {"esprit", "topcoder" }

  37. {"ellie", "torb", "esprit", "esprit", "ellie", "torb"}

    Returns: {"ellie", "esprit", "torb" }

  38. {"elly", "ellie", "elly", "kriss", "ariadne", "elly", "ariadne", "ariadne"}

    Returns: {"ariadne", "elly" }

  39. {"esprit", "elly", "ellie", "ellie", "esprit", "ellie"}

    Returns: {"ellie", "esprit" }

  40. {"kriss", "esprit", "esprit", "kriss"}

    Returns: {"esprit", "kriss" }

  41. {"ariadne", "esprit", "stancho", "stancho", "ariadne", "stancho", "esprit", "elly"}

    Returns: {"ariadne", "esprit", "stancho" }

  42. {"topcoder", "topcoder", "elly", "topcoder", "stancho", "ariadne", "elly", "esprit"}

    Returns: {"elly", "topcoder" }

  43. {"elly", "esprit", "esprit"}

    Returns: {"esprit" }

  44. {"topcoder", "elly", "topcoder", "elly", "ariadne", "ariadne", "elly", "elly"}

    Returns: {"ariadne", "elly", "topcoder" }

  45. {"torb", "torb", "ariadne", "torb", "esprit", "esprit", "esprit", "ariadne"}

    Returns: {"ariadne", "esprit", "torb" }

  46. {"elly", "torb", "torb", "torb"}

    Returns: {"torb" }

  47. {"ellie", "stancho", "ariadne", "topcoder", "ariadne", "ellie"}

    Returns: {"ariadne", "ellie" }

  48. {"kriss", "esprit", "esprit"}

    Returns: {"esprit" }

  49. {"topcoder", "elly", "elly", "kriss", "esprit"}

    Returns: {"elly" }

  50. {"topcoder", "elly", "torb", "ellie", "ellie", "torb"}

    Returns: {"ellie", "torb" }

  51. {"esprit", "topcoder", "elly", "esprit", "ellie", "elly"}

    Returns: {"elly", "esprit" }

  52. {"elly", "topcoder", "ariadne", "elly"}

    Returns: {"elly" }

  53. {"stancho", "elly", "elly", "stancho", "elly"}

    Returns: {"elly", "stancho" }

  54. {"stancho", "ellie", "ellie"}

    Returns: {"ellie" }

  55. {"topcoder", "ariadne", "ariadne", "topcoder"}

    Returns: {"ariadne", "topcoder" }

  56. {"topcoder", "topcoder", "topcoder", "elly", "topcoder"}

    Returns: {"topcoder" }

  57. {"elly", "elly", "kriss", "elly", "stancho", "torb", "stancho"}

    Returns: {"elly", "stancho" }

  58. {"torb", "esprit", "kriss", "esprit", "elly", "torb", "esprit", "ellie"}

    Returns: {"esprit", "torb" }

  59. {"kriss", "ellie", "esprit", "ariadne", "ariadne"}

    Returns: {"ariadne" }

  60. {"ellie", "ellie", "ellie", "stancho"}

    Returns: {"ellie" }

  61. {"a" }

    Returns: {"a" }

  62. {"ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "elly" }

    Returns: {"ariadne", "elly", "stancho" }

  63. {"e", "c", "d", "d", "d", "a", "e", "a" }

    Returns: {"a", "d", "e" }

  64. {"y" }

    Returns: {"y" }

  65. {"assd" }

    Returns: {"assd" }

  66. {"qwe" }

    Returns: {"qwe" }

  67. {"x" }

    Returns: {"x" }

  68. {"b", "b", "b", "b", "a", "a", "a", "a" }

    Returns: {"a", "b" }

  69. {"abc" }

    Returns: {"abc" }

  70. {"ivan" }

    Returns: {"ivan" }

  71. {"aa" }

    Returns: {"aa" }

  72. {"elly" }

    Returns: {"elly" }

  73. {"b", "b", "a", "a" }

    Returns: {"a", "b" }

  74. {"f" }

    Returns: {"f" }

  75. {"bb", "aa" }

    Returns: { }

  76. {"dz", "az", "az", "dz", "dz" }

    Returns: {"az", "dz" }

  77. {"aaa" }

    Returns: {"aaa" }

  78. {"b", "b", "c", "a", "a" }

    Returns: {"a", "b" }

  79. {"sara" }

    Returns: {"sara" }

  80. {"name" }

    Returns: {"name" }

  81. {"e" }

    Returns: {"e" }

  82. {"ariadne", "elly", "ariadne", "stancho", "stancho", "kriss", "stancho", "stancho" }

    Returns: {"ariadne", "stancho" }

  83. {"bb", "bb", "bb", "aa", "aa", "aa" }

    Returns: {"aa", "bb" }

  84. {"seraph" }

    Returns: {"seraph" }

  85. {"test" }

    Returns: {"test" }

  86. {"ff", "ee", "dd", "cc", "aa", "aa", "aa", "aa" }

    Returns: {"aa" }

  87. {"z", "z", "a", "a" }

    Returns: {"a", "z" }

  88. {"a", "a", "b", "b", "c", "c", "d", "d" }

    Returns: {"a", "b", "c", "d" }

  89. {"somename" }

    Returns: {"somename" }

  90. {"all", "all", "bee" }

    Returns: {"all" }

  91. {"aaaaaa" }

    Returns: {"aaaaaa" }

  92. {"zzzzzzzzzzzzzzzzzzzz", "zzzzzzzzzzzzzzzzzzzz", "zzzzzzzzzzzzzzzzzzzz", "a" }

    Returns: {"zzzzzzzzzzzzzzzzzzzz" }

  93. {"a", "b" }

    Returns: { }

  94. {"ann" }

    Returns: {"ann" }

  95. {"quang" }

    Returns: {"quang" }

  96. {"c", "b", "a", "a" }

    Returns: {"a" }

  97. {"a", "a", "c", "a", "b", "a", "b", "c" }

    Returns: {"a", "b", "c" }

  98. {"a", "a", "b" }

    Returns: {"a" }

  99. {"afda" }

    Returns: {"afda" }

  100. {"g", "f", "e", "d", "c", "b", "a", "a" }

    Returns: {"a" }

  101. {"a", "a", "b", "b" }

    Returns: {"a", "b" }

  102. {"a", "a", "b", "b", "b", "b", "b", "b" }

    Returns: {"a", "b" }

  103. {"c", "c", "a", "a", "a", "b", "b" }

    Returns: {"a", "b", "c" }

  104. {"kriss" }

    Returns: {"kriss" }

  105. {"aa", "bb" }

    Returns: { }

  106. {"z" }

    Returns: {"z" }

  107. {"b", "b", "b", "a", "a", "a" }

    Returns: {"a", "b" }

  108. {"a", "a", "a", "b", "b" }

    Returns: {"a", "b" }

  109. {"c", "c", "b", "b" }

    Returns: {"b", "c" }

  110. {"a", "a", "b", "c", "d" }

    Returns: {"a" }

  111. {"stancho", "stancho", "kriss", "elly", "elly" }

    Returns: {"elly", "stancho" }

  112. {"e", "a", "v" }

    Returns: { }

  113. {"z", "y", "x", "a", "a" }

    Returns: {"a" }

  114. {"b" }

    Returns: {"b" }

  115. {"a", "b", "a", "b" }

    Returns: {"a", "b" }

  116. {"a", "a", "a", "a", "b", "b" }

    Returns: {"a", "b" }

  117. {"abc", "abc", "cde", "cde", "cde", "cde", "cde" }

    Returns: {"abc", "cde" }

  118. {"ariadne" }

    Returns: {"ariadne" }

  119. {"e", "a" }

    Returns: { }

  120. {"aaaaa", "aaaa", "aaa", "aa", "aa", "aaaaaa", "aaaa", "aaaa" }

    Returns: {"aa", "aaaa" }

  121. {"z", "z", "y", "x", "x", "x" }

    Returns: {"x", "z" }

  122. {"b", "b", "b", "a", "a" }

    Returns: {"a", "b" }

  123. {"a", "d", "b", "c", "b", "c", "d", "a" }

    Returns: {"a", "b", "c", "d" }

  124. {"z", "z", "y", "y", "a", "a" }

    Returns: {"a", "y", "z" }

  125. {"b", "b", "b", "b", "b", "a", "a" }

    Returns: {"a", "b" }

  126. {"banana" }

    Returns: {"banana" }

  127. {"one", "one", "three", "four", "five", "six", "seven", "eight" }

    Returns: {"one" }

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: