SAT2020's blog

Codeforces #788 Question B: Confused by TLE
By SAT2020, history, 2 years ago, In English

Hi All,

I recently competed in Codeforces Round #788 (Div. 2). I was confused by Question B, in which I got two TLE failed submissions. I managed to eke out a solution almost two hours in, but it just barely passed the time constraints, with a runtime of ~900 ms on a 1-second limit. The reason I'm confused is this: from my perspective, my initial solutions were O(n)log(n) (using a set) and O(n) (using a hashmap), and both failed the pre-tests with only 2*10^5 inputs. In addition, from what I can see my final solution is also O(n) (using a character-mapping array), and it just barely passed the tests. I've linked my 3 solutions in this post, and would highly appreciate any feedback on why my solutions were so slow, and how I can improve for the future.

Thank you

Successful:

Failed:

If you're wondering about the differences between these submissions, the primary change I made was the data structure used to represent "special" characters. In the successful submission, I used an array ("letters"), while in the failed solutions I used a set and a map (both named "v") respectively.

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

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

After experimenting with my solution, it seems like it's just because you're using iostreams without having performed the necessary rituals beforehand (read up on ios_base::sync_with_stdio if you're not familiar, and/or just browse passing solutions).

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

    Thanks for your help, this was very useful!

    → Reply