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*(*Nlog*^{2}(*N*)) solution. I thought it maybe too much (ironically after the contest some magical *O*(*N*^{2}) 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*(*Nlog*^{2}(*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*(*Nlog*^{2}(*N*)) was too much (e.g. 514D - R2D2 and Droid Army). Even when an *O*(*Nlog*^{2}(*N*)) passes it takes a lot of time (e.g. 11843275).

First, how does the *O*(*Nlog*^{2}(*N*)) passes in such small time? and generally how to determine whether the *O*(*Nlog*^{2}(*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 10

^{5}.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 10

^{6}I highly doubt that any brute force solution would pass.well I believe this contest was my worst ever ! :) Take a look :)