sigma_g's blog

Solution similar to editorial got TLE verdict ("Queries for Number of Palindromes" problem)
By sigma_g, history, 6 years ago, In English

Problem: https://mirror.codeforces.com/contest/245/problem/H

My solution: https://mirror.codeforces.com/contest/245/submission/49911945
Editorial solution: https://mirror.codeforces.com/contest/245/submission/2622404

Both of the codes look exactly the same, and have the same logic. Yet mine is TLE. Could anyone please help me understand why that is the case?

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I guess your solution is not the problem, since the one from the editorial also gives TLE.

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

Just swap cin, cout to scanf, printf. Editorial solution takes TLE too in C++11(14, 17). Maybe old C++ was faster xD.

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

Change endl to "\n" , endl does not tie the output,so your cout.tie() is ineffective.

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

    Thanks! That worked :D

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

    Technically it is not cout.tie(0) that is ineffective, because cout.tie(0) doesn't do anything as cout isn't tied to anything. That line in the code should/could just be removed and nothing will change. Only cin is tied to cout by default, not the other way around.

    The actual reason why endl is bad is because it flushes the output stream while "\n" doesn't.

    However cin.tie(0) is useful because it unties cin from cout, which makes it so cout isn't flushed whenever cin is used.

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

Btw your line cout.tie(0) doesn't do anything. By default cin is tied to cout to guarantee that cout will be flushed before doing input reading, which is something you would want solving interactive problems. But cout is by default not tied to anything, so doing cout.tie(0) doesn't change anything.

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

    Thanks for the information. It was very helpful!

    → Reply