Problem statement:

You have a lightbulb for an interval of $N$ seconds, where $N$ is given. At time 0, the lightbulb switches on, and at time $N$, it switches off, regardless of any switches. From time 1 to time $N-1$ you have a maximum of $N-2$ switches in the form of an array called switches, which turn the lightbulb to the opposite of what it currently is i.e. if it's on it'll turn off and vice versa. For example, suppose $N = 8$ and switches $[1,2]$. The lightbulb will switch on at time 0, a switch at time 1 will turn it off, a switch at time 2 will turn it on, and it'll remain on until time 8, when it turns off. Hence, the time it remains on is equal to $1-0 + 8-2 = 7$.

Now suppose you have to insert a switch in this interval, where there is not already a switch present. What is the maximum time the lightbulb remains on once you insert the switch. For example, in the above case, the solution would be 6 since inserting a switch at time 7 keeps the time the lightbulb spends on maximum. Since $1-0 + 7-2 = 6$, the answer is 6.

I solved this using a brute force solution, using the reasoning that if you insert a switch at time $k$, the states of the lightbulb before this wouldn't be affected, and the states of the lightbulb from time $k$ to time $N$ will be reversed, and hence you can find the time it spends on after time $k$ by $(N - k) - t$, where $t$ is the time it would spend on from time $k$ to $N$ without the inserted switch. Hence, I can calculate the time the lightbulb would spend on for each time position of the inserted switch and maximize it. However, since calculating the time the lightbulb spends on is $O(n)$ operations and I go through all possible positions, my solution is $O(n^2)$ and this caused my code to time out for some test cases.

Can someone propose a better solution?


Your solution is already O(N). You just don't have to recompute the complete light time for all position.

Compute once the full light time L0 before insertion.

Then as you are looping on positions, you keep an accumulator B of the light time before the tested position. And you know you have L0-B after...

So at position t, you have: L(t) = B + (N-t) - (L0-B)

NB: you even can skip L0 pre-computation as your accumulator B will be L0 at end of the loop and L(t)+L0 has the same maximum than L(t).


Let's call the array of switches $a$ and let's add two elements to the array at the beginning we add 0 and at the end we add 100.
We now want to insert an element between two consecutive elements to maximise the length the bulb is turned on.
Let's make the following observations:

Note1 If a[i+1] = a[i] + 1, two consecutive elements have consecutive values. In this case we can't add anything between them.

Note2 The optimal value we add between $a[i]$ and $a[i + 1]$ for some $i$ is either equal to $a[i] + 1$ or to $a[i+1] - 1$.
Proof. Assuming the claim is not true, there is an optimal value strictly between $a[i]+1$ and $a[i+1]-1$. However, if the bulb is turned off in this interval we can push it back to $a[i]+1$ increasing the length of the turned on pulp in this interval without effecting the others. On the other hand if the bulb is turned on, we push it right to $a[i+1]-1$ increasing the length of turned on pulp in this interval.

So now we can loop over the array, and for each $i$, if $a[i] \neq a[i+1]-1$, we try to add the value $a[i]+1$ and the value $a[i+1]-1$, these are 2*(n-1) tries in total where n is the number of elements in the array (including 0 and n), which is linear in the number of the switches. We only have to show that we can do each step in constant time.
So let's say we already have the array, and we want to check the total value after adding a switch at position $k$. Let's pre-process the array and calculate and building the following 2 arrays in linear time:
1. The length of light-on since the begin.
2. The length of light-off from now till the end.
We can do that in two loops over the array using prefix-/suffix-sums.
Now when adding a switch between $a[i]$ and $a[i+1]$ with time stamp $k \in (a[i], a[i+1])$, the total value of on-light will be total value of on light from the begin to $i$ + the total off-light from $a[i+1]$ till the end + the total on-light in the interval between $a[i]$ and a[i+1] after adding $k$ (Which is either $k - a[i]$ or $a[i+1] - k$ depending on the original status of the interval).
Summary, In total we preprocess the array in $O(n)$, we do linear number of checks $O(n)$ and each in constant time in total we have $O(n) + O(n) * O(1) = O(n)$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.