Unexpected TLE


  • 3
    M

    I'm not certain this code produces the correct answer, however I was surprised to get TLE. I originally was using push_back on the vector, but even with a size initializer to avoid multiple heap allocations it still takes too long on the input (9999,9998). On my machine, this code runs in about 8 microseconds, or about 2.5 clocks per n, so I don't really know what's going on here.

    vector<int> constructArray(int n, int k) {
        vector<int> ret(n);
        int d = n - 1;
        int c = 1;
        bool low = true;
        int idx = 0;
        ret[idx++] = c;
        for (int i = 0; i < k - 1; i++)
        {
            if (low) c += d--;
            else c -= d--;
            ret[idx++] = c;
            low = !low;
        }
        for (int i = k; i < n; i++)
        {
            if (low) c++;
            else c--;
            ret[idx++] = c;
        }
        return ret;
    }
    

    Edit:
    I even tried alexander's "Clean Code 4-liner" solution and it takes over 8 times as long, mostly spent in vector-realloc.

    Edit 2:
    Ok so I just resubmitted this code as-is and it was accepted... Wouldn't have impacted my ranking in the contest much, but still I'd like to know what might have caused TLE in the first place. In case it matters, my submissions were all within about 10 minutes of the end of the contest.


  • -1
    G
    This post is deleted!

  • 0

    I'm somewhat part of the team and was able to look into this.

    You had three contest submissions. Your first two should've gotten "Wrong Answer" (because your result included negative numbers) and the third should've gotten "Accepted".

    All your submissions by themselves were fast. You got "Time Limit Exceeded" because the judge code which checks the results was slow. For wrong results like those of your first two submissions it was extra slow, causing certain TLE. For correct results it was still slow, with a possibility of being too slow (due to variations in runtime). So your third submission got TLE because the judge happened to be slower than average that time. And your resubmission of it now got accepted because the judge happened to be fast enough that time.

    The judge code has now been fixed (i.e., made not slow) but I was told the contest results will stand as there aren't enough resources to change this (and I think it's not clear what would be the best way to "fix" the situation).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.