Statistics

Problem Statement for "BagOfHolding"

Problem Statement

You are in possesion of a special Bag of Holding. You can put any items in this bag that you want and it never becomes bulkier or heavier. Whenever you want to take something out of the bag you just reach in and pull it out, if it isn't obscured by other items. Whenever you put an item in the bag, it will obscure all items already in the bag that are as small or smaller than it, preventing you from pulling those items out of the bag.

You have quite a few items that you want to keep in the bag, and you are wondering if you put all the items in the bag randomly, what are the odds that you'll be able to reach a certain item. Clearly you will only be able to reach that item if no items as big or bigger than it were put into the bag after it, and the ordering of items smaller than the item in question doesn't matter. Create a class BagOfHolding with a method oddsReachable that takes a int[] sizes, which contains the sizes of each item, and an int item, which is the index of the item in sizes that you are concerned with (the first item in the sizes is item 0), and returns a double that is the percent chance that you will be able to reach that item if you put all the items into the bag at random.

Definition

Class:
BagOfHolding
Method:
oddsReachable
Parameters:
int[], int
Returns:
double
Method signature:
double oddsReachable(int[] sizes, int item)
(be sure your method is public)

Constraints

  • sizes will contain between 1 and 10 elements, inclusive.
  • Every element of sizes will be between 1 and 10000, inclusive.
  • item will be between 0 and the number of elements in sizes-1, inclusive.

Examples

  1. {1,2,3}

    1

    Returns: 0.5

    There are six orders in which these items could be put in the bag: {1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1}. We want to be able to reach the item with a size of 2, and we will be able to in 3 of the 6 orderings, so we return .5.

  2. {1,2,3}

    2

    Returns: 1.0

    Same items, but this time we want to be able to reach the item with a size of 3. Since it is larger than all of the other items we will always be able to reach it, so we return 1.

  3. {1,1,2,3}

    2

    Returns: 0.5

    Like example 0, but now there is another item of size 1. Remember that {1,1,2,3} can be two different orderings, since there are two distinct items of size 1.

  4. {1,2,3,4,5,6,7,8,9,10}

    4

    Returns: 0.16666666666666666

  5. {1,2,3,4,5,6,7,8,9,10}

    0

    Returns: 0.1

  6. {1,2,3,4,5,6,7,8,9,10}

    0

    Returns: 0.1

  7. {1,2,3,4,5,6,7,8,9,10}

    5

    Returns: 0.2

  8. {1,2,3,4,5,6,7,8,9,10}

    9

    Returns: 1.0

  9. {1,10,100,1000,10000,1,10,100,1000,10000}

    3

    Returns: 0.25

  10. {10000,9000,8000,7000,6000,5000,4000,3000,2000,1000}

    3

    Returns: 0.25

  11. {1}

    0

    Returns: 1.0

  12. {10000}

    0

    Returns: 1.0

  13. {1576,4085,2782,5475,900,9953,6186,7887}

    7

    Returns: 0.5

  14. {7867,5852,5289,8322,9367,520,8053}

    3

    Returns: 0.5

  15. {1073,522,4399,1616}

    0

    Returns: 0.3333333333333333

  16. {3707,8316,153,1282,7623}

    0

    Returns: 0.3333333333333333

  17. {6686,3123,9780,5105,1866}

    1

    Returns: 0.25

  18. {6525,214,3835,8652,9593,2066,55,6248,2213,5758}

    6

    Returns: 0.1

  19. {7729,2266,3263,7984,3181}

    0

    Returns: 0.5

  20. {156,1817,2754,3863,9160,6677}

    1

    Returns: 0.2

  21. {8404,8097,6762,7519,2480,8045,8294}

    6

    Returns: 0.5

  22. {1689,1570,2119,1944,9797,7822,6563}

    0

    Returns: 0.16666666666666666

  23. {656,6925,9654,3099,5036}

    2

    Returns: 1.0

  24. {2839,7640,4117,3806,6259,7796}

    4

    Returns: 0.3333333333333333

  25. {3792,8397,6070,1691}

    3

    Returns: 0.25

  26. {4466,8999,2376,1781,3278,7923,2020,8401,7850,47}

    5

    Returns: 0.3333333333333333

  27. {8518,7499,8268,4937,7554,8551,2616}

    6

    Returns: 0.14285714285714285

  28. {1651,1028,8993,7498,7119,2352,3021,7510}

    2

    Returns: 1.0

  29. {5874,6199,7944,9349,6142,9123,4644,7105}

    1

    Returns: 0.2

  30. {1901,4934,5899,8972,3481,1122,711,3720}

    4

    Returns: 0.2

  31. {8083,3220,8209,58,9951,96,4861,2246,3307}

    3

    Returns: 0.1111111111111111

  32. {343,3864,1189,7038,3299,1364,5825,7994}

    6

    Returns: 0.3333333333333333

  33. {2669,5014,1243,2908,2089,7250,151,4456,7301}

    8

    Returns: 1.0

  34. {7892,3297,9866,1071,3776,4365,166}

    4

    Returns: 0.25

  35. {3305,8626,6471,1928,9845,2254,179,372}

    0

    Returns: 0.25

  36. {9037,1478,4011,6940,8505,5250,8823,4904}

    4

    Returns: 0.3333333333333333

  37. {2739,612,5937,3594,4991,6720,9485,6822,603,8124}

    4

    Returns: 0.16666666666666666

  38. { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }

    4

    Returns: 0.16666666666666666

  39. { 1, 1, 2, 3 }

    2

    Returns: 0.5

  40. { 1, 2, 3, 4, 5, 6, 6, 6, 7, 8 }

    6

    Returns: 0.2

  41. { 1, 2, 3 }

    1

    Returns: 0.5

  42. { 1, 1, 2, 3 }

    1

    Returns: 0.25

  43. { 1, 2, 2 }

    2

    Returns: 0.5

  44. { 2, 5, 3, 4, 9, 9, 9, 9, 9, 9 }

    0

    Returns: 0.1

  45. { 1, 1, 1, 1, 1 }

    1

    Returns: 0.2

  46. { 1, 2, 3, 2 }

    1

    Returns: 0.3333333333333333

  47. { 2, 2, 2, 2 }

    0

    Returns: 0.25

  48. { 5, 5, 5, 5 }

    3

    Returns: 0.25

  49. { 5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }

    6

    Returns: 0.1

  50. { 1, 1, 2, 3 }

    0

    Returns: 0.25

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: