Statistics

Problem Statement for "RPSTournament"

Problem Statement

You are organizing a local Rock-Paper-Scissors Tournament, where the best N players in your town will compete for fame and prizes. You have already ranked the participants according to their performance in the qualifying round, so each one of them will have a seed for winning the tournament in the range from 1 to N.

The tournament will be in a knockout format and will consist of multiple rounds. During each round the competitors still left in the competition are randomly paired up with each other. The winners from each game advance to the next round. The great champion is the winner of the final game between the last two remaining players.

The tournament starts soon, and you are preoccupied with some pre-statistics. You estimate that a player with any seed S can win against players with greater seeds, and against ones with lower seeds, if the difference between their seeds is not greater than sqrt(C * S), where C is a constant. Assuming that the outcome of all the played games during the tournament agrees with your estimation, a player can win the tournament if there exists an assignment of games in each of the rounds such that the player can win each round.

You will be given two ints, rounds, denoting the number of rounds, and the constant C. Return the greatest seed of a player that could win the tournament. Note that N, the number of competitors will be N = 2rounds.

Definition

Class:
RPSTournament
Method:
greatestSeed
Parameters:
int, int
Returns:
int
Method signature:
int greatestSeed(int rounds, int C)
(be sure your method is public)

Constraints

  • rounds will be between 1 and 16, inclusive.
  • C will be between 0 and 1500, inclusive.

Examples

  1. 2

    0

    Returns: 1

    There is no room for surprises here. Since nobody can win against a higher-rated opponent, the lowest seed will win the tournament.

  2. 2

    1

    Returns: 4

  3. 3

    1

    Returns: 6

    Player 2 can win against player 1, so both of them can win the final if they are to meet in that phase of the competition. Since players 3 and 4 can beat player 2, they can win the tournament as long as player 2 wins against player 1 somewhere before the final. Finally, players 5 and 6 can beat player 4 in the final, as long as player 4 wins against player 2 in the semifinals and player 2 eliminates player 1 in the first round. It is impossible for players 7 and 8 to win the tournament. We return the greatest seed of those who can win, namely 6.

  4. 3

    2

    Returns: 8

  5. 4

    1

    Returns: 9

  6. 4

    2

    Returns: 14

  7. 4

    3

    Returns: 16

  8. 5

    1

    Returns: 12

  9. 5

    3

    Returns: 28

  10. 5

    4

    Returns: 32

  11. 6

    1

    Returns: 16

  12. 6

    4

    Returns: 47

  13. 6

    5

    Returns: 60

  14. 7

    3

    Returns: 50

  15. 7

    5

    Returns: 80

  16. 7

    9

    Returns: 128

  17. 8

    2

    Returns: 44

  18. 8

    7

    Returns: 139

  19. 8

    14

    Returns: 246

  20. 9

    5

    Returns: 127

  21. 9

    12

    Returns: 277

  22. 9

    20

    Returns: 435

  23. 10

    7

    Returns: 211

  24. 10

    22

    Returns: 593

  25. 10

    35

    Returns: 908

  26. 11

    4

    Returns: 142

  27. 11

    32

    Returns: 1022

  28. 11

    53

    Returns: 1613

  29. 11

    69

    Returns: 2015

  30. 12

    14

    Returns: 575

  31. 12

    57

    Returns: 2105

  32. 12

    94

    Returns: 3242

  33. 12

    121

    Returns: 4063

  34. 13

    25

    Returns: 1151

  35. 13

    56

    Returns: 2461

  36. 13

    107

    Returns: 4387

  37. 13

    165

    Returns: 6486

  38. 13

    202

    Returns: 7820

  39. 14

    9

    Returns: 510

  40. 14

    125

    Returns: 5979

  41. 14

    173

    Returns: 8037

  42. 14

    208

    Returns: 9523

  43. 14

    267

    Returns: 12023

  44. 14

    325

    Returns: 14270

  45. 14

    394

    Returns: 16384

  46. 15

    54

    Returns: 3191

  47. 15

    129

    Returns: 7204

  48. 15

    180

    Returns: 9755

    Watch out for timeout!

  49. 15

    247

    Returns: 13076

  50. 15

    303

    Returns: 15845

  51. 15

    361

    Returns: 18690

  52. 15

    413

    Returns: 20980

  53. 15

    462

    Returns: 23127

  54. 15

    500

    Returns: 24781

  55. 15

    537

    Returns: 26388

  56. 15

    609

    Returns: 29501

  57. 15

    634

    Returns: 30579

  58. 15

    663

    Returns: 31836

  59. 15

    679

    Returns: 32522

  60. 15

    1000

    Returns: 32768

  61. 16

    83

    Returns: 5524

  62. 16

    252

    Returns: 15409

  63. 16

    375

    Returns: 22406

  64. 16

    500

    Returns: 29219

  65. 16

    609

    Returns: 34759

  66. 16

    743

    Returns: 41519

  67. 16

    834

    Returns: 46085

  68. 16

    924

    Returns: 50583

  69. 16

    1000

    Returns: 54373

  70. 16

    1078

    Returns: 58260

  71. 16

    1111

    Returns: 59897

  72. 16

    1164

    Returns: 62532

  73. 16

    1203

    Returns: 64466

  74. 16

    15

    Returns: 1098

  75. 16

    1500

    Returns: 65536

  76. 16

    1399

    Returns: 65536

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: