Codeforces #788 Question B: Confused by TLE

Revision en1, by SAT2020, 2022-05-07 01:50:31

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.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English SAT2020 2022-05-07 01:50:31 1340 Initial revision (published)