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

general
,
1

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
2

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
Your Output
~ no response on stdout ~
3

@vijju123, could it be anything related to the size limit on the 2d array named dp? For instance, when I keep the value of MAX_N and MAX_M to their current values and run on my local computer, I get Segmentation Fault(11). So, I generally have to reduce the size of MAX_N and MAX_M to around 10 to get it working on my local computer. HackerRank, may have placed a stricter memory limitation than Codechef

1 Like
4

Just declare all array globally or assign it static. After that it will also compile on hackerrank

1 Like
5

Thanks for your views :slight_smile:

6

Any idea about why the code is giving TLE?

7

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 :slight_smile:

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.