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:
https://mirror.codeforces.com/contest/1670/submission/156104237
https://mirror.codeforces.com/contest/1670/submission/156111007
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.
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_stdioif you're not familiar, and/or just browse passing solutions).Thanks for your help, this was very useful!