 # TRIP - Always timeout

http://www.codechef.com/problems/TRIP/

I don’t know why. I have tried my solution on my computer with 1,000,000 random N and got it done in 0.0075 seconds. The time limitation is 2 seconds for this problem, but I always get timeout.

``````#include <iostream>

using namespace std;

int main()
{
int n, m;

// Get N and M
cin >> n >> m;

// Create 3 array of N size for storing
// - Distance, Minimal Number of Step, Number of Way
int* way = new int[n];
int* dist = new int[n];
int* step = new int[n];

// Fill the input
std::ios::sync_with_stdio(false);
for(int i = 0; i < n; i++) {
cin >> dist[i];
step[i] = 0;
}

way = 1;

// Calculate the number of way and step
for(int i = 0; i < n; i++) {
int next = step[i] + 1;

int max_dist = dist[i] + m;
int j = i + 1;

while ((dist[j] <= max_dist) && (j < n)) {
if (step[j] == 0) {
step[j] = next;
way[j] = way[i];
} else if (step[j] == next) {
way[j] = (way[j] + way[i]) % 1000000007;
} else if (step[j] > next) {
step[j] = next;
way[j] = way[i];
}

j++;
}
}

cout << step[n-1] - 1 << " " << way[n-1] << endl;

return 0;
}``````

In worst case, if you check smartly, the complexity of your code will be approximately O(n^2). N begin <= 10^6 will give TLE. Even though you are generating random test cases but it doesn’t mean that your code is correct.

1 Like