Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×

Swayam78's blog

Need Help : Why my N*N*log(N) soln fails for N=1000,

By Swayam78, history, 23 months ago, In English

Why My NNLog(N) soln got tle for 3rd Q , When N= 1000 , It should work , https://leetcode.com/problems/smallest-substring-with-identical-characters-i/solutions/6172861/need-help-why-2-n-n-log-n-solution-not-passed/ , Can anybody help.

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
22 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I had similar idea, but was getting TLE. Try switching the dimensions of your vector. TLE Code AC Code

Why TLE? Leetcode runs 1000s of testcases for different values of n in a tight timelimit.

Why vector of size n * 2 gives TLE but 2 * n doesn't? Cache friendliness :)

→ Reply
  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Ok. Thanks, But still ,If it is having correct TC according to given constraint , It should work I think, Because 2*1e7 operation are performed.

    → Reply
    • »
      »
      »
      22 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      Leetcode has a "combined" time limit for all the testcases in a problem. If you try to add the TLE test case to sample testcases and run it — it will work fine. But if you run 10s of such large testcases, it will cross the time limit, hence the TLE when running all testcases.

      → Reply
  • »
    »
    22 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Thank you Bhai , I checked 2*n solution worked.

    → Reply