Hello Codeforces!
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).
It depends on constant factor in your solution. Using c++ set or map is slow for example but binary search is fast. Sometimes we have log(N), sometimes log(1e9). Base could be 2 or e. Your solution could badly jump on memory or efficiently use cache. For N <= 1e5 complexity O(n sqrt(n)) and O(n log^2 n) sometimes are fast enough, sometimes aren't.
Why only 76ms? Because it's "only" complexity, maybe for every test your program makes only n*log^2(n)/10 operations?
may be your O(Nlog^2(N)) algorithm run fast in jury's test, or your O(Nlog^2(N)) algorithm is merely O(Nlog^2(N)) and your O(Nlog2(N)) algorithm multiply with big constant
I think for this problem, you only get log N levels when N is a power of 2. So the worst case is when N = 65536, which is smaller than 105.
You forgot 2^17=131072.
Oh, right.
I think that this happened because of the bad test cases .. my solution was O(4^(logN)) which is O(n^2) but I was very surprised when I got Accepted :) . I think it passed because I put the odd length as a base case .. but I'm sure that if the length of the 2 strings was power of 2 I would get TLE .
I don't think it's a weak test cases problem, it seems to be a constraints problem. If the time limit was 1 second only, or the length of the string was up to 106 I highly doubt that any brute force solution would pass.
well I believe this contest was my worst ever ! :) Take a look :)