rahulkhairwar's blog

SPOJ DQUERY TLE
By rahulkhairwar, history, 8 years ago, In English

I was trying to learn Mo's Algorithm from here and this was one of the suggested problems. But, I'm getting TLE verdict with Java, while my code is very similar to the one that the tutorial's author has written, in C++.

Can someone please tell me what am I doing wrong(slow)? Thanks.

UPDATE : Sorry, forgot to post a link for my code

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by rahulkhairwar (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I did not trace your code, but SPOJ is very strict judge. Some problems are only solvable in C++.

So sometimes no matter how much you optimise your Java's code, it won't pass.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

slow input !?

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I believe your solution should pass as the time complexity is acceptable. But, as many people have already pointed out, SPOJ is pretty strict when it comes to TLEs.

However, there is a faster solution than yours. Try to come up with a solution using BIT.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Same here for my java code too. Tried all kinds of optimizations and gave up. I tried searching those 3 ppl (whose java passed) on codeforces but no luck A couple other similar tight tle problems were also solved by some of the 3.

→ Reply