PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Constantine Sokol
Editorialist: Florin Chirica
DIFFICULTY:
Cakewalk
PREREQUISITES:
none
PROBLEM:
There are N + 1 lights, initially turned off. You start from light 0 and move alternatively to right, then to left, then to right and so on to the farthest turned off light. Once you arrive to farthest light, you turn it on. You perform this as long as there is at least one light turned off. To move from light x to light x – 1 or x + 1 you need cost 1. What’s total cost to turn all lights on?
QUICK EXPLANATION
We can use dynamic programming to calculate the answer for all possible n values.
Let dp[n] = total cost to turn off lights from 0 to n.
dp[0] = 0 and dp[1] = 2
The DP recurrence is dp[i] = i + i + 1 + dp[i – 2].
Alternatively, you can notice the answer for a given n is (n + 1) * (n + 2) / 2 - 1.
EXPLANATION
Let us observe
One very useful way to solve problems is to see what happens for a relatively small input. This can lead to key for solving larger ones. Let’s start with n = 1. I’ll mark by -> when you move from a light to an adjacent one (obviously, each time it happens the solution is increased by 1). So, for n = 1, the solution looks like this 0 -> 1 -> 0.
Let’s see what happens for n = 3 now. 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 0 -> 1 -> 2 -> 1. Let’s focus on last 3 elements from the path. The pattern looks the same as the one for n = 1 (the form of the path is the same, except the lights are indexed differently). Is this a coincidence?
Let’s move forward at n = 5.
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 2 -> 3 -> 2. Let’s compare 0 -> 1 -> 2 -> 3 -> 2 -> 1 -> 0 -> 1 -> 2 -> 1 (answer from n = 3) with 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> 2 -> 3 -> 2 (answer after turning on the lamp 0). The form of the path is the same again, except the indexes of the lights are different as well. But as the form of the path is the same, the length will also be the same.
Generalize the observations
Let’s generalize. Suppose you get n lamps. You’ll go first this way 0 -> 1 -> … -> n -> n – 1 -> n – 2 -> … -> 0. We turn right and go to n, then we turn left and go to 0, then we turn right again. In this moment you’ll arrive to lamp 1. In this moment you can notice the form of the path will be the same as having n – 2 lamps (and you can obtain the path by copying the path for n – 2 and adding +1 to all indices… 0 -> 1 -> 0 for n = 1 becomes 1 -> 2 -> 1 for n = 3). Since the path is the same, the distance walked will be exactly the same.
So we get a simple algorithm: suppose we calculated for n – 2. Then, go from lamp 0 to lamp n, go from lamp n to lamp 0, go from lamp 0 to lamp 1 and go like in the solution for n – 2. The length of the path for a given n is n + n + 1 + length of the path for n – 2.
With other words, for calculate answer for a given n, we need to use answer calculated before. This should be the “aha” moment to use dynamic programming (we calculate the current state using previously calculated states).
Apply dynamic programming
Let dp[n] = the length of the path if I have n lamps.
dp[n] = n + n + 1 + dp[n – 2]
For the DP to be complete, we need initialization of it. If I set dp[0] = 0 and dp[1] = 2, then all other elements of dp[] can be calculated.
A one line formula
As a bonus challenge, look at elements of dp. They all have a pattern: dp[n] = (n + 1) * (n + 2) / 2 - 1. This observation isn’t needed to solve this problem, but if author would intend n <= 10^9, then calculating dp elements using a loop wouldn’t pass. As an exercise, try to proof why dp[n] = (n + 1) * (n + 2) / 2 – 1. You’ll probably need a well known fact to do this: the sum 1 + 2 + … + n is equal to n * (n + 1) / 2
Time Complexity
Depending of the approach used, the complexity can be O(T + N) or O(T).