ChristmasLightsFixing
SRM 796 · 2020-12-21 · by misof
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
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.
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.
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.
50
7
Returns: {6 }
The first seven steps are checks of {0}, {1}, {2}, {3}, {4}, {5}, and {6}.
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]
1
1
Returns: {0 }
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ChristmasLightsFixing with a public method vector<int> fixingTime(int N, long long step) · 88 test cases · 2 s / 256 MB per case