The last codeforces round was one of my worst. It took me a very very long time to code A. Then I read B, got an O(Nlog2(N)) solution. I thought it maybe too much (ironically after the contest some magical O(N2) solutions passed) and I spent the whole contest trying to optimize it to an O(NlogN) solution but failed. At the last 10 minutes I thought to give it a shot but it was too late to write a quick bug-free solution. I didn't even read C which was a problem I've faced before.
Anyway, after the contest I've submitted both an O(Nlog2(N)) and an O(NlogN) solutions 12199582 12199737, The O(NlogN) solution passed in 46 ms which was pretty okay, but, the other solution passed in 78 ms! which is about 1.7 times of the O(NlogN) solution. I've faced some problems before where O(Nlog2(N)) was too much (e.g. 514D - R2D2 and Droid Army). Even when an O(Nlog2(N)) passes it takes a lot of time (e.g. 11843275).
First, how does the O(Nlog2(N)) passes in such small time? and generally how to determine whether the O(Nlog2(N)) approach is good for a problem or not? (without coding and testing of course).