LogitechSellout's blog

Why TLE even though time complexity is ok (DP)?
By LogitechSellout, history, 6 years ago, In English

Hi, I'm pretty new to CF and this is one of my first problems here

Problem Statement: https://codeforces.net/problemset/problem/245/H Basically you want to answer q queries, each stating the number of palidromes between two indicies of a long string

My code: https://codeforces.net/contest/245/submission/53304310

For some reason CF seems to time out, even though time complexity is alright (O(s^2+q)) which is quite odd

Could this because of my programming language? I know that java tends to be slow in these contests

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

Comments Comments (2)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

IO is the bottleneck in your code. If you use buffer your output so it all gets printed at once and not in chunks, then it will pass. As an example, https://codeforces.net/contest/245/submission/53306869

I use StringBuilder to build my output which gets printed in its entirety when I call System.out.print().

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

    Or just use PrintWriter, which is also much faster than system printing.

    → Reply