Hello All,
Recently I was faced with the following problem:
There are 'M' bulbs which are mounted on an X-axis (horizontal). Each bulb is attached to a switch (located at the same location on the X-axis), which can be used to turn the bulb OFF. The location of the switches are integers on the X-axis (Li). A robot has been assigned the task to switch 'OFF' all the bulbs, which takes a unit amount of time to move a unit distance.
Given coordinates of 'M' bulbs (which are all in ON position initially) and a starting position 'S', the task is to switch off each one of them, such that the total power consumed is minimized. The power consumed by a bulb (in Watts) is equal to the time the bulb has remained 'ON'.
To illustrate with an example, suppose that there are 3 bulbs (A, B, C) located along the X-axis at coordinates 1, 3 and 5 respectively. If the starting position for the robot is 4, the minimal amount of power required to switch all the bulbs off would be 9.
Explanation:
The robot first switches off the bulb C, located at x=5. By the time it reaches 'C' (x=4 to x=5), 3 bulbs have been glowing for 1 second. Power consumption = 3 Watts. Next, the robot turns to the left and switches off bulb 'B'. It would take 2 seconds to reach 'B' from position 'C'. By that time 2 bulbs have been glowing. Power consumption = 4 Watts. The robot would further move to the left, and finally turn 'A' off, which would consume 2 more Watts. Hence, total power consumption = 3 + 4 + 2 = 9 Watts.
Constraints:
1 <= M <= 1000
1 <= Li, S <= 1000000
My Solution:
I came up with the following dynamic programming formulation:
#include <iostream>
#include <cstdio>
#include <climits>
#include <cstring>
#include <vector>
using namespace std;
/**
* dp[i][j][k] = Watts consumed when the bulbs from (i..j) exclusive have been switched off,
* where the current position of the robot is pos[k].
*/
int main()
{
int T, S, N;
cin >> T;
while ( T-- )
{
cin >> N >> S;
int pos[N+1];
pos[0] = 0;
for(int i=1; i<=N; i++)
cin >> pos[i];
int dp[N+2][N+2][N+2];
memset(dp, 0, sizeof(dp));
for(int i=N; i>=0; i--)
for(int j=i-1; j>=0; j--)
dp[0][i][j] = (N-i+1)*(pos[i] - pos[j]) + dp[0][i+1][i];
for(int i=1; i<=N; i++)
for(int j=i+1; j<=N; j++)
dp[i][N+1][j] = i*(pos[j] - pos[i]) + dp[i-1][N+1][i];
for(int i=1; i<=N; i++)
{
for(int j=N; j>i; j--)
{
for(int k=i+1; k<j; k++)
{
int left = (N-j+i+1)*(pos[k] - pos[i]) + dp[i-1][j][i];
int right = (N-j+i+1)*(pos[j] - pos[k]) + dp[i][j+1][j];
dp[i][j][k] = min(left, right);
}
}
}
int curr = 0;
while ( pos[curr] < S )
++curr;
if ( S < pos[1] ) cout << dp[0][2][1] + N*(pos[1] - S) << endl;
else if ( S > pos[N] ) cout << dp[N-1][N+1][N] + N*(S - pos[N]) << endl;
else if ( S == pos[curr] ) cout << dp[curr-1][curr+1][curr] << endl;
else
{
cout << min( N*(pos[curr] - S ) + dp[curr-1][curr+1][curr],
N*(S - pos[curr-1]) + dp[curr-2][curr][curr-1] )
<< endl;
}
}
return 0;
}
However, when I submitted this code to the judge, I got only 60/100. Can someone please tell me what is the problem with this code?
P.S: I have already tried with long long int instead of int.
Thanks!