TRIP - Always timeout

general
1

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[0] = 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;
}
2

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