Statistics

Problem Statement for "ChristmasLightsFixing"

Problem Statement

Monika is going to put Christmas lights on her Christmas tree.

The lights are just a single wire with N colorful light bulbs in a row. We will number the light bulbs 0 to N-1 along the wire. An electrician would call this type of connection "in series". This way of connecting the light bulbs has the property that as long as at least one light bulb is defective, the whole chain is off - the current does not flow and all light bulbs are off.

The problem with Christmas lights is that while they are in the closet during the year, some of the light bulbs usually stop working. Come Christmas, you take the lights out of the closet, put them on the tree, plug them in, and... nothing happens. You then have to locate and replace the broken bulbs.


There are various ways to tell whether a bulb is bad, but Monika does not know any of them. The way she tests whether exactly the light bulbs from the set S are defective is by temporarily replacing them with new light bulbs. If this makes the chain light up, the problem is fixed. If not, she removes the new light bulbs and returns the light bulbs from set S back to their original sockets. (Thus, at the end of each test the Christmas lights are back in their exact original form.)


Monika does not want to waste new light bulbs. Thus, during testing she proceeds as follows: first she tests each individual light bulb, then she tests each pair of light bulbs, then each set of 3, then sets of 4, and so on.

To make sure that she does not skip some set of light bulbs, she tests the sets of each fixed size in lexicographic order. (See Notes for a definition if you don't know what that is.) For example, if N=5, she will test the sets of three light bulbs in the following order: {0,1,2}, {0,1,3}, {0,1,4}, {0,2,3}, {0,2,4}, {0,3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}.


You are given the int N: the number of light bulbs in the Christmas lights. You are also given the long step. Suppose we number all sets of light bulbs starting from 1 in the order in which Monika tests them. Find and return the set of light bulbs that will get the number step.

Definition

Class:
ChristmasLightsFixing
Method:
fixingTime
Parameters:
int, long
Returns:
int[]
Method signature:
int[] fixingTime(int N, long step)
(be sure your method is public)

Notes

  • A set of light bulbs is always written as a sequence in ascending order. For example, if Monika is testing the light bulbs 3, 7, and 1, she is testing the set {1, 3, 7}.
  • Given two sequences X and Y of the same length, we say that X is lexicographically smaller than Y if X has a smaller value than Y at the smallest index at which they differ.
  • For example, if X = {1, 3, 7, 12, 23} and Y = {1, 3, 8, 10, 99}, X is smaller than Y because X[0] = Y[0] = 1, X[1] = Y[1] = 3, and X[2] < Y[2] because 7 < 8.

Constraints

  • N will be between 1 and 50, inclusive.
  • step will be between 1 and 2N-1, inclusive.

Examples

  1. 5

    16

    Returns: {0, 1, 2 }

    Tests 1-5 involve testing a single light bulb. Tests 6-15 involve testing a pair of light bulbs. Test 16 is the first test in which Monika tests three light bulbs. The tested set is the lexicographically smallest among all those sets.

  2. 40

    1099511627775

    Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39 }

    This value of step equals 240-1. The very last set tested is always the set containing all N light bulbs.

  3. 50

    7

    Returns: {6 }

    The first seven steps are checks of {0}, {1}, {2}, {3}, {4}, {5}, and {6}.

  4. 7

    47

    Returns: {1, 2, 6 }

    Here is the full numbered list of checks in the order Monika performs them for N = 7: 1:[0] 2:[1] 3:[2] 4:[3] 5:[4] 6:[5] 7:[6] 8:[0, 1] 9:[0, 2] 10:[0, 3] 11:[0, 4] 12:[0, 5] 13:[0, 6] 14:[1, 2] 15:[1, 3] 16:[1, 4] 17:[1, 5] 18:[1, 6] 19:[2, 3] 20:[2, 4] 21:[2, 5] 22:[2, 6] 23:[3, 4] 24:[3, 5] 25:[3, 6] 26:[4, 5] 27:[4, 6] 28:[5, 6] 29:[0, 1, 2] 30:[0, 1, 3] 31:[0, 1, 4] 32:[0, 1, 5] 33:[0, 1, 6] 34:[0, 2, 3] 35:[0, 2, 4] 36:[0, 2, 5] 37:[0, 2, 6] 38:[0, 3, 4] 39:[0, 3, 5] 40:[0, 3, 6] 41:[0, 4, 5] 42:[0, 4, 6] 43:[0, 5, 6] 44:[1, 2, 3] 45:[1, 2, 4] 46:[1, 2, 5] 47:[1, 2, 6] 48:[1, 3, 4] 49:[1, 3, 5] 50:[1, 3, 6] 51:[1, 4, 5] 52:[1, 4, 6] 53:[1, 5, 6] 54:[2, 3, 4] 55:[2, 3, 5] 56:[2, 3, 6] 57:[2, 4, 5] 58:[2, 4, 6] 59:[2, 5, 6] 60:[3, 4, 5] 61:[3, 4, 6] 62:[3, 5, 6] 63:[4, 5, 6] 64:[0, 1, 2, 3] 65:[0, 1, 2, 4] 66:[0, 1, 2, 5] 67:[0, 1, 2, 6] 68:[0, 1, 3, 4] 69:[0, 1, 3, 5] 70:[0, 1, 3, 6] 71:[0, 1, 4, 5] 72:[0, 1, 4, 6] 73:[0, 1, 5, 6] 74:[0, 2, 3, 4] 75:[0, 2, 3, 5] 76:[0, 2, 3, 6] 77:[0, 2, 4, 5] 78:[0, 2, 4, 6] 79:[0, 2, 5, 6] 80:[0, 3, 4, 5] 81:[0, 3, 4, 6] 82:[0, 3, 5, 6] 83:[0, 4, 5, 6] 84:[1, 2, 3, 4] 85:[1, 2, 3, 5] 86:[1, 2, 3, 6] 87:[1, 2, 4, 5] 88:[1, 2, 4, 6] 89:[1, 2, 5, 6] 90:[1, 3, 4, 5] 91:[1, 3, 4, 6] 92:[1, 3, 5, 6] 93:[1, 4, 5, 6] 94:[2, 3, 4, 5] 95:[2, 3, 4, 6] 96:[2, 3, 5, 6] 97:[2, 4, 5, 6] 98:[3, 4, 5, 6] 99:[0, 1, 2, 3, 4] 100:[0, 1, 2, 3, 5] 101:[0, 1, 2, 3, 6] 102:[0, 1, 2, 4, 5] 103:[0, 1, 2, 4, 6] 104:[0, 1, 2, 5, 6] 105:[0, 1, 3, 4, 5] 106:[0, 1, 3, 4, 6] 107:[0, 1, 3, 5, 6] 108:[0, 1, 4, 5, 6] 109:[0, 2, 3, 4, 5] 110:[0, 2, 3, 4, 6] 111:[0, 2, 3, 5, 6] 112:[0, 2, 4, 5, 6] 113:[0, 3, 4, 5, 6] 114:[1, 2, 3, 4, 5] 115:[1, 2, 3, 4, 6] 116:[1, 2, 3, 5, 6] 117:[1, 2, 4, 5, 6] 118:[1, 3, 4, 5, 6] 119:[2, 3, 4, 5, 6] 120:[0, 1, 2, 3, 4, 5] 121:[0, 1, 2, 3, 4, 6] 122:[0, 1, 2, 3, 5, 6] 123:[0, 1, 2, 4, 5, 6] 124:[0, 1, 3, 4, 5, 6] 125:[0, 2, 3, 4, 5, 6] 126:[1, 2, 3, 4, 5, 6] 127:[0, 1, 2, 3, 4, 5, 6]

  5. 1

    1

    Returns: {0 }

  6. 2

    1

    Returns: {0 }

  7. 3

    4

    Returns: {0, 1 }

  8. 4

    9

    Returns: {1, 3 }

  9. 5

    15

    Returns: {3, 4 }

  10. 6

    37

    Returns: {1, 4, 5 }

  11. 7

    44

    Returns: {1, 2, 3 }

  12. 8

    66

    Returns: {1, 3, 7 }

  13. 9

    263

    Returns: {0, 1, 2, 4, 7 }

  14. 10

    396

    Returns: {0, 1, 2, 4, 9 }

  15. 11

    804

    Returns: {1, 2, 4, 7, 10 }

  16. 12

    2522

    Returns: {0, 1, 2, 3, 4, 7, 9 }

  17. 13

    336

    Returns: {5, 8, 12 }

  18. 14

    13027

    Returns: {0, 1, 2, 3, 4, 8, 9, 12, 13 }

  19. 15

    13715

    Returns: {1, 2, 7, 9, 11, 12, 14 }

  20. 16

    43164

    Returns: {0, 2, 3, 5, 6, 8, 9, 12, 15 }

  21. 17

    3102

    Returns: {8, 9, 12, 16 }

  22. 18

    250968

    Returns: {0, 1, 2, 3, 5, 6, 7, 9, 10, 12, 14, 15, 17 }

  23. 19

    53717

    Returns: {0, 2, 7, 9, 11, 13, 17 }

  24. 20

    657

    Returns: {2, 14, 16 }

  25. 21

    553243

    Returns: {1, 2, 5, 12, 14, 15, 16, 18, 19 }

  26. 22

    3953759

    Returns: {0, 1, 2, 4, 6, 7, 8, 9, 10, 11, 14, 16, 18, 19, 21 }

  27. 23

    8099815

    Returns: {0, 1, 3, 5, 8, 9, 10, 11, 12, 13, 14, 16, 18, 19, 20, 22 }

  28. 24

    13291660

    Returns: {0, 3, 6, 7, 9, 12, 13, 14, 16, 17, 18, 19, 22, 23 }

  29. 25

    16158230

    Returns: {3, 4, 5, 6, 8, 11, 12, 13, 16, 17, 18, 19 }

  30. 26

    48577259

    Returns: {0, 1, 2, 3, 4, 5, 11, 13, 14, 15, 17, 18, 21, 24, 25 }

  31. 27

    73375192

    Returns: {0, 2, 3, 6, 7, 9, 13, 17, 18, 19, 20, 21, 23, 25 }

  32. 28

    2452361

    Returns: {0, 6, 14, 15, 19, 21, 23, 25 }

  33. 29

    492527401

    Returns: {1, 2, 8, 9, 10, 12, 14, 15, 16, 19, 20, 21, 23, 24, 25, 26, 27, 28 }

  34. 30

    875863263

    Returns: {3, 6, 7, 8, 9, 12, 13, 14, 16, 17, 20, 21, 22, 23, 24, 26, 29 }

  35. 31

    1930025925

    Returns: {0, 4, 6, 7, 10, 11, 13, 14, 18, 19, 20, 21, 22, 25, 26, 27, 28, 29, 30 }

  36. 32

    1355395164

    Returns: {0, 1, 3, 6, 7, 10, 12, 18, 20, 22, 25, 26, 27, 28, 30 }

  37. 33

    2437686899

    Returns: {0, 3, 4, 6, 13, 15, 19, 21, 23, 27, 28, 29, 30, 31, 32 }

  38. 34

    988044145

    Returns: {4, 9, 11, 14, 15, 16, 19, 20, 22, 25, 31, 33 }

  39. 35

    19427294992

    Returns: {0, 5, 6, 9, 12, 13, 15, 17, 19, 20, 21, 22, 23, 24, 25, 29, 31, 34 }

  40. 36

    31607016996

    Returns: {0, 1, 4, 6, 7, 13, 14, 16, 18, 19, 22, 24, 26, 27, 29, 31, 34, 35 }

  41. 37

    34178334466

    Returns: {4, 5, 8, 9, 14, 15, 16, 17, 18, 19, 21, 23, 27, 29, 30, 32 }

  42. 38

    150466723624

    Returns: {2, 5, 8, 9, 10, 11, 13, 14, 17, 18, 20, 23, 24, 27, 28, 31, 33, 34, 37 }

  43. 39

    392449059968

    Returns: {1, 5, 7, 8, 10, 11, 16, 19, 21, 22, 23, 25, 26, 27, 30, 31, 32, 33, 34, 36, 37 }

  44. 40

    389500281984

    Returns: {0, 2, 4, 9, 11, 13, 14, 17, 18, 21, 22, 23, 28, 31, 32, 33, 35, 38, 39 }

  45. 41

    754200447374

    Returns: {1, 5, 6, 9, 11, 14, 21, 22, 25, 26, 29, 30, 31, 32, 34, 35, 36, 37, 38 }

  46. 42

    2527836461737

    Returns: {0, 1, 2, 5, 9, 11, 13, 14, 17, 19, 23, 24, 25, 30, 31, 32, 34, 35, 36, 38, 40, 41 }

  47. 43

    1725554214079

    Returns: {0, 1, 6, 8, 12, 15, 16, 20, 22, 23, 28, 29, 30, 34, 37, 39, 40, 41, 42 }

  48. 44

    13873769227688

    Returns: {0, 1, 3, 4, 5, 6, 7, 10, 11, 13, 16, 20, 22, 24, 25, 26, 27, 28, 29, 32, 33, 35, 37, 40, 43 }

  49. 45

    25657450111121

    Returns: {0, 1, 2, 3, 5, 7, 8, 9, 10, 13, 14, 16, 19, 21, 23, 25, 27, 30, 31, 33, 38, 39, 40, 42, 44 }

  50. 46

    65832893442596

    Returns: {1, 2, 3, 6, 7, 8, 9, 12, 14, 16, 20, 21, 25, 26, 27, 28, 29, 31, 33, 34, 35, 38, 39, 40, 41, 42, 43, 44 }

  51. 47

    17661057043003

    Returns: {0, 1, 2, 6, 8, 9, 12, 14, 19, 20, 24, 25, 26, 27, 34, 37, 38, 40, 42, 44 }

  52. 48

    27570829283139

    Returns: {0, 1, 2, 3, 7, 12, 17, 19, 21, 23, 24, 26, 35, 36, 37, 38, 40, 41, 44, 47 }

  53. 49

    325581554253323

    Returns: {1, 3, 6, 10, 11, 12, 14, 18, 20, 22, 23, 26, 27, 28, 29, 30, 32, 34, 36, 37, 39, 43, 44, 47, 48 }

  54. 50

    572301744682629

    Returns: {1, 2, 4, 5, 7, 13, 14, 16, 18, 19, 20, 21, 25, 26, 27, 28, 29, 31, 32, 38, 39, 41, 44, 47, 48 }

  55. 5

    1

    Returns: {0 }

  56. 5

    2

    Returns: {1 }

  57. 5

    3

    Returns: {2 }

  58. 5

    4

    Returns: {3 }

  59. 5

    5

    Returns: {4 }

  60. 5

    6

    Returns: {0, 1 }

  61. 5

    7

    Returns: {0, 2 }

  62. 5

    8

    Returns: {0, 3 }

  63. 5

    9

    Returns: {0, 4 }

  64. 5

    10

    Returns: {1, 2 }

  65. 5

    11

    Returns: {1, 3 }

  66. 5

    12

    Returns: {1, 4 }

  67. 5

    13

    Returns: {2, 3 }

  68. 5

    14

    Returns: {2, 4 }

  69. 5

    15

    Returns: {3, 4 }

  70. 5

    16

    Returns: {0, 1, 2 }

  71. 5

    17

    Returns: {0, 1, 3 }

  72. 5

    18

    Returns: {0, 1, 4 }

  73. 5

    19

    Returns: {0, 2, 3 }

  74. 5

    20

    Returns: {0, 2, 4 }

  75. 5

    21

    Returns: {0, 3, 4 }

  76. 5

    22

    Returns: {1, 2, 3 }

  77. 5

    23

    Returns: {1, 2, 4 }

  78. 5

    24

    Returns: {1, 3, 4 }

  79. 5

    25

    Returns: {2, 3, 4 }

  80. 5

    26

    Returns: {0, 1, 2, 3 }

  81. 5

    27

    Returns: {0, 1, 2, 4 }

  82. 5

    28

    Returns: {0, 1, 3, 4 }

  83. 5

    29

    Returns: {0, 2, 3, 4 }

  84. 5

    30

    Returns: {1, 2, 3, 4 }

  85. 5

    31

    Returns: {0, 1, 2, 3, 4 }

  86. 50

    1125899906842604

    Returns: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49 }

  87. 40

    846783679826

    Returns: {2, 3, 5, 8, 9, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24, 28, 29, 30, 31, 35, 36, 37 }

  88. 7

    122

    Returns: {0, 1, 2, 3, 5, 6 }

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: