God damnit, again not getting notifications for comments marked as spoilers.

I tested your solution and the one I'm using currently. Yours is very fast for many tests; well, it takes about the same time to do 1 test as doing 10000. 

Now, I'm doing only about 100 tests here, and for that amount, the one that's currently up seems to be about 2 to 3 times faster.

I didn't want to make the tests too much harder to not fail most of the current solutions; there was a single one I targeted, though, due to hardcoding. The current tests are at the limit of performance to not timeout most solutions.

Do you think I should make the tests harder? It feels kind of unfair to me, as I myself would probably have been unable to solve it without looking at the current solutions. However, I could if it made for a more interesting challenge.

What's considered a 3kyu has really changed over time.

I've just come up with a blazingly fast solution to this problem; it's about 10 times faster than any of the previous solutions, and it's able to complete all the tests in a second.

I actually have to thank Lachesism and Voile. I basically put together the best parts of their solutions and some of mine to make this beast.

I adjusted the test cases to allow all previous solutions to still pass. It would feel unfair to force people to come up with something I wasn't able to do myself originally.

However, this time around, just printing the results takes 1.1 seconds. I believe that's very acceptable.

Well, there's no happiness without suffering; congrats on solving!

Though you're making me question whether I should add a barrier against hardcoding...

I hate that comments marked as spoiler don't show up in the notifications, thanks for explaining.

What the what? Out of all the solutions, this is the one I understand the least.

Why not keeping some look-up tables on referee side to compute intermediate results faster?
It can give more time to players or it can be used to raise the upper bound.

Nice, this was hard. My head hurts...

Quite nice and funny kata.

Really, I have no chance to optimise Python ( or the math ) enough to ever solve it.

I feel like if you tried to solve the kata you'd understand better (I know you won't).

Those are really small Big-O differences, yes. For practical purposes, O(log n) is not often even distinguishable from O(1).

Please don't link directly to the trainer. :P

The differences are Big-O optimizations, it's just that they're kind of small. I'm not entirelly sure of the time complexity, but the ideia it to optimize from about O(sqrt(n) log(n)) to sqrt(n) or sqrt(n) log(n) to sqrt(n) log(log(n)).

From my tests, the optimizations that only changed the solution by a constant factor didn't make a significant difference in passing.

If there was more time the differences would be clearer, but 12 seconds isn't much.

Part of the fun is finding this ultra optimized solution and is sort of the characteristics of the kata.

I see it as somewhat like this kata, where the proper solution is faster time complexity wise, but it takes a large n to see that and even so is hard to spot.

I'll still mention it in the description though