Codechef February Long 2017: INTERVAL. Why am I getting TLE for some test cases?

I am following the same approach explained by @gkcs, here: https://www.youtube.com/watch?v=qB51btVY0Xw

Here is my code solution to the problem:

I am getting TLE for test cases 5 to 9.

#include<bits/stdc++.h>

``````#define MAX_N 300001
#define MAX_M 201

using namespace std;

int main(void) {

long long t, n, m;
long long x;
long long b[MAX_M];
long long c[MAX_N];
long long dp[MAX_N][MAX_M];
long long cum_sum, i, j, optimalScore;

scanf("%lld", &t);

deque<long long> dq;

while (t-- ) {

scanf("%lld%lld",&n, &m);

cum_sum = 0;
for (i = 1; i <= n; i++ ) {
scanf("%lld",&x);
cum_sum += x;
c[i] = cum_sum;
}

for (i = 1; i <= m; i++ ) {
scanf("%lld",&b[i]);
}

long long lastIndex = n - b[m] + 1;

long long cum_start, cum_end;
for (i = 1; i <= lastIndex; i++ ) {
cum_end = c[i + b[m] - 1];
if ( (i-1) >= 1) {
cum_start = c[i - 1];
}
else {
cum_start = 0;
}
dp[i][m] = cum_end - cum_start;
}

for (i = (m-1) ; i >= 1; i-- ) {
lastIndex = n - b[i] + 1;

long long slidingWindowSize = b[i] - b[i+1] - 1;
dq.clear();

for (long long k = 1; k <= slidingWindowSize; k++ ) {

while((!dq.empty()) && ( dp[1+k][i+1] >= dp[dq.back()][i+1] ) ) {
dq.pop_back();
}

dq.push_back(1+k);
}

cum_end = c[1 + b[i] - 1];
cum_start = 0;

dp[1][i] = cum_end - cum_start;

dp[1][i] -= dp[dq.front()][i+1];

for ( j = 2; j <= lastIndex; j++) {

// calc the sum
cum_end = c[j + b[i] - 1];
cum_start = c[j - 1];
dp[j][i] = cum_end - cum_start;

//add the new element to the dq
while ((!dq.empty()) && ( dq.front() < (j+1)) ) {
dq.pop_front();
}

while ( (!dq.empty()) && ( dp[j+slidingWindowSize][i+1] >= dp[dq.back()][i+1] ) ) {
dq.pop_back();
}

dq.push_back(j+slidingWindowSize);

// subtract the max possible score of opponent
dp[j][i] -= dp[dq.front()][i+1];
}
}

optimalScore = dp[1][1];

for (i = 2; i <= lastIndex; i++ ) {
if (dp[i][1] > optimalScore) {
optimalScore = dp[i][1];
}
}
printf("%lld\n",optimalScore);
}

return 0;
}``````
1 Like

Hi Mukund,

I went through the solution, and it seems to be having an O(M*N) time complexity. Have a look at the for loop which evicts front deque elements inside the move loop. The outer one runs M times, and the inner one runs N times in the worst case.

Fixing the deque implementation will give you an AC

Code to look at:

``````for (i = (m-1) ; i >= 1; i-- )
``````

and

``````for ( j = 2; j <= lastIndex; j++) {
``````

Where lastIndex can go upto n +1.

To everyone,

One strange thing I noticed, the code runs perfectly on codechef compiler but it gives run time error at hackerrank compiler. Can anyone shed light on this?

``````Runtime error
Input (stdin) [HACKERRANK COMPILER]
1
8 3
3 7 5 4 9 6 1 3
6 3 1