ANUWTA - Editorial

PROBLEM LINK:

Practice
Contest

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 + 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).

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

5 Likes

Why (n*(n+1))/2 +n is not working…??? (Not able to understand even after reading the editorial)

4 Likes

Here is my solution : http://www.codechef.com/viewsolution/5186377
I still didn’t get why am I getting a wrong answer. I have used (2n)+(n(n-1))/2 instead of (n+1)*(n+2)/2-1
and I find both of them are equivalent.
So can anyone explain me why it is a wrong answer?

A more simple answer is : (N*(N+3))/2. by observing the pattern in DP.
ACed solution

1 Like

Can anyone please explain … I used the same approach and used lld while printing link text

1 Like

getting WA .please help.

http://www.codechef.com/viewsolution/5196157

1 Like

thnx ahmedtai

1 Like

This is also working. Even simpler

#include
using namespace std;

int main() {
int N,T,ans;
cin>>T;
while(T–)
{
cin>>N;
ans = N;
while(N!=0)
{
ans = ans + N;
N–;
}
cout<<ans<<endl;
}
}

1 Like

please help me
http://www.codechef.com/ide

1 Like

link https://ideone.com/Iv7a4K

1 Like

Why is Dynamic Programming solution giving TLE?

#include<bits/stdc++.h>
using namespace std;
long long int arr[100001];

inline void scani(int *a){
register char c=0;
while (c<33) c=getchar();
*a=0;
while (c>33)
{
*a=a10+c-‘0’;
c=getchar();
}
}

int main(void)
{
int t,i,n;
scani(&t);
arr[0]=0;
arr[1]=2;
arr[2]=5;
while(t–)
{
scani(&n);
for(i=3;i<=n;++i)
{
arr*=i+i+1+arr[i-2];
}
printf("%lld
",arr[n]);
}
}

@aijajkhan see this solution -> https://www.codechef.com/viewsolution/10045155
Here i precomputed the cost of all the lights from 0 to 10^5. Then displayed them as the value is entered.

I’m getting TLE inspite of using DP.Please help.
here’s the link to my solution:
https://www.codechef.com/viewsolution/10871878

overflow ??

???

you must have used int datatype which will not work.

It’s because of overflow, n has upper limit as 10^5 so n^n will give you 10^10 which we can not hold in int data type, use long or long long for this purpose.

you are using %d in scanf, but 10^5 is beyond limits of int. see http://www.cplusplus.com/reference/climits/

1 Like

U dint bracket the n*(n+3) . In your solution, n+3 gets divided by 2 first and then multiplied by n . But what if n+3 isn’t even divisible by 2? You should first multiply n and n+3 and then divide by 2.

2 Likes

Take n as unsigned long long or typecast them to long long while calculating as unsigned long long ans=((long long)n*(long long) (n+3))/2;

1 Like