TopCoder problem "SureThing" used in TCO04 Semifinal 3 (Division I Level Three)

Problem Statement


Various numbers of different-colored (but otherwise identical) marbles are placed in a bag. Marbles are randomly removed from the bag one at a time. You are given the opportunity to guess the color of each marble immediately before it is removed, and with each guess you place a wager. If the color of the marble matches your guess you win the amount of your wager, otherwise you lose that amount.

Each wager can be anywhere from 0 to the total amount of money you have at the time of your wager, inclusive. Your goal is to carefully choose your wagers in order to guarantee yourself the highest possible winnings in the end. Given the total number of marbles of each color initially in the bag and $1.00, determine the greatest amount of money you can guarantee yourself to end up with.

For example, if the bag starts with 1 blue, 1 red, and 1 yellow marble, your best strategy is to wager zero on the first two marbles and then wager everything on the third marble, guaranteeing yourself $2.00 at the end. If you wager anything on either of the first two marbles, there is a chance that you will guess wrong and lose money. Even after doubling your money on the last marble you could end up with less than $2.00. So in this case, the answer is 2.

You can always end up with $2.00 by waiting until there is only one marble left. But often you can do better than that. If the bag begins with 1 blue and 2 red marbles, your best strategy is to bet 1/3 of your money on red. If you are correct (the first marble is red), you will end up with 4/3, bet nothing on the second marble, and then double your money betting on the last marble to 8/3. If you are incorrect (and the first marble is blue) you will have 2/3 left, but you will be able to double your money twice (because you know the last two marbles are both red), thus ending up with 8/3. Notice that you don't care if your first guess is right or wrong -- either outcome leads to ending up with 8/3.



Method signature:double maximum(int[] marbles)
(be sure your method is public)


-Don't worry about betting an integral number of coins. Assume your money is infinitely divisible. Wagers such as 1/3 and sqrt(2) are perfectly legal.
-Your return must have an absolute or relative error less than 1e-9.


-marbles will contain between 1 and 6 elements, inclusive.
-Each element of marbles will be between 1 and 100, inclusive.


{ 1, 1, 1 }
Returns: 2.0
This is the first example in the problem statement.
{1, 2}
Returns: 2.666666666666667
This is the second example in the problem statement.
Returns: 1024.0
With 10 marbles all the same color, you can "guess" correctly 10 times, doubling your money each time.
{26, 26}
Returns: 9.081329549427792
This is the version of the game that you can play with a deck of cards, guessing if each one will be black or red.
{1, 2, 3, 4, 5, 100 }
Returns: 1.6979400579163614E16

Problem url:

Problem stats url:




PabloGilberto , lbackstrom , vorthys

Problem categories:

Dynamic Programming, Math