Today, I had spent hours trying to solve problem : (https://codeforces.net/contest/1334/problem/C) and submitted several solutions with an O(n) complexity, but I kept getting a TLE. After some further inspection, I changed from using cin to scanf, and my solution was finally accepted. While it's well-known that scanf is slightly faster than cin, I was surprised by how much of a difference it actually made in this case.
TLE Code : 284211972 Accepted Code : 284212724
This blog may not be overly educational, but I just want to highlight that even a O(n) solution can lead to a TLE error. Understanding this can help you avoid the frustration and wasted time that I experienced.
