Statistics

Problem Statement for "DigitByDigit"

Problem Statement

You have reached the final round of a game show, and it is time to determine the amount of your prize. The number of digits, n, in the amount has been determined based on your earlier performance during the game. You will be presented with a board containing n blank spaces and given n randomly-generated digits. You will be allowed to place each digit, one at a time, in any unoccupied space you want. You must decide where to place each digit before you see the next, and once you place a digit you cannot move it. After all n digits have been placed, the resulting n-digit number will be the value of your prize.

For example, assume you have earned a three-digit prize. If the first digit generated were a 2, you might choose to place that in the rightmost space, hoping that the next two digits will be larger. If the second digit were a 8, you might choose to place that in the leftmost space, because you would only regret that decision in the relatively unlikely event that the final digit is a 9. If the third digit were a 6, you would place that in the last remaining space (the middle), and your final prize would be 862.

You will be given the state of the number you are forming digit-by-digit as a String digits, possibly already in progress. This String will contain one character for each space on the board: '0' through '9', inclusive, indicate digits that have already been placed, and a '_' indicates a blank space on the board. Assuming you play optimally in order to maximize your expected winnings, return the expected value of the prize you will win.

At each step, each of the digits 0 through 9 will be presented to you with equal probability. Note that the digits already placed may not be the result of optimal play, but you should assume that you will play to maximize your expected winnings from this point forward.

Definition

Class:
DigitByDigit
Method:
expectedScore
Parameters:
String
Returns:
double
Method signature:
double expectedScore(String digits)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • digits will contain between 1 and 50 characters, inclusive.
  • digits will contain only the characters '_' and '0' through '9', inclusive.

Examples

  1. "_0"

    Returns: 45.0

    There is only one blank space, so you will only have one more digit to place. The final result will either be 0, 10, 20, 30, 40, 50, 60, 70, 80, or 90. The expected value, 45, is the average of these.

  2. "__"

    Returns: 60.75

    The highest expected value is achieved by putting the first digit in the left spot if it is 5, 6, 7, 8, or 9, and putting it in the right spot if it is 0, 1, 2, 3, or 4. The expected value can be computed as: 5/10 * ((5+6+7+8+9)/5 * 10 + 4.5 ) + 5/10 * (4.5 * 10 + (0+1+2+3+4)/5) Any deviation from this strategy would result in a lower expected value.

  3. "_55_"

    Returns: 6303.25

  4. "____0000000000000000"

    Returns: 7.482735000000001E19

  5. "___6__3___"

    Returns: 8.604871517066002E9

  6. "__________"

    Returns: 8.882477600592714E9

  7. "0"

    Returns: 0.0

  8. "99999999999999999999999999999999999999999999999999"

    Returns: 1.0E50

  9. "____________________"

    Returns: 9.583251637922008E19

  10. "__________________________________________________"

    Returns: 9.97547673335543E49

  11. "0000000000_0000000000_0000000000_0000000000_000000"

    Returns: 6.915000000052848E39

  12. "_0_1_2_3_4_5_6_7_8_9_"

    Returns: 8.25430304569466E20

  13. "_"

    Returns: 4.5

  14. "7"

    Returns: 7.0

  15. "_9999999999999999999999999999999999999999999999999"

    Returns: 5.499999999999999E49

  16. "000000000000000000000000000000000000000000000_____"

    Returns: 78733.8045

  17. "014922___5____1_067_____4__1__2__2609___0"

    Returns: 1.4922965298599258E39

  18. "3__4__7_9_9____4___1_8261__________8942____3_30"

    Returns: 3.978085430911233E46

  19. "4_90___7___6__4______3_0___3___9___4__0__"

    Returns: 4.978616073320793E40

  20. "__7_9__8_____2_40_79_3970505____12_8___1__"

    Returns: 9.677911562683919E41

  21. "4_4523____8____8____61___46_______4700__5_____"

    Returns: 4.934143033348244E45

  22. "75515____8_9072_____0__3109_0____120______663"

    Returns: 7.551596866800043E44

  23. "_2__0__0_1046__3___89__72__5_90_11_________06"

    Returns: 9.123415002373696E44

  24. "232__3_3_16__80_____05_______7_23_4__73__"

    Returns: 2.329665131664449E40

  25. "____6_6_0__2_2__2_05___2_______6_____1___30_2_"

    Returns: 9.865892534146287E45

  26. "2__5_6_91___5___5_0_12__21___809____075_2"

    Returns: 2.9626980551878684E40

  27. "6_________1____3_007_7_6332__63058____839___4___"

    Returns: 6.980463156205806E47

  28. "8_____89__90__52_055997__9___3_40544_7__13____"

    Returns: 8.968660222874899E45

  29. "9_136__________6713_5_864___5_25546_26_5___8"

    Returns: 9.887913607994664E43

  30. "60_______90________5_2___2_0__6875__1_47__210_1"

    Returns: 6.098046317496375E46

  31. "__________9_6__7_66_125__6_3__4__0_________32_3_"

    Returns: 9.878123262401342E47

  32. "1_5_7_______2____2__3____8_5__06_____2_____7"

    Returns: 1.950446342293424E43

  33. "47_7____11_______9_08___64__4_41_747_6_____"

    Returns: 4.7962418026116257E42

  34. "80_9_6__549_5__1__72___5_77____1__2_22_9__7_"

    Returns: 8.097816375698759E43

  35. "09___8_______81____7____55______0__1__58_1"

    Returns: 9.982237062532665E40

  36. "4_4_2_7____3________63_94_____22___5____7_"

    Returns: 4.936511274998553E41

  37. "0_________________2_____________________________5_"

    Returns: 9.967457214015187E48

  38. "___________9_____________________________________1"

    Returns: 9.970386079696278E49

  39. "__________________________________________________"

    Returns: 9.97547673335543E49

  40. "__________"

    Returns: 8.882477600592714E9

  41. "00000000000000000000______________________________"

    Returns: 9.838245760580156E29

  42. "________97__________________________________13____"

    Returns: 9.964238685059565E49

  43. "__________4_________6__________3__________"

    Returns: 9.930795910791479E41

  44. "8_____________________________________3__________1"

    Returns: 8.996745721401515E49

  45. "_______1______2____0_____3_______0______6____9____"

    Returns: 9.952543290329455E49

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: