The editorial suggests an algorithm which is of O(n^2). But there are at most 100 test cases too. So how can an O(n^2) algorithm work?
n^2 = 10^6
And there are 100 test cases, so 10^8
computations.
I am a beginner, and I’ve heard that we can not process more than 10^7 computations on codechef.
My rule of thumb is 10^8 per second which those constraints satisfy.
This is just an estimate and depends on the algorithm’s constant factor.
I usually don’t take the number of test cases into account unless this number is quite large (1000+). In this case, I assume not all tests will have the worst case limits.
It’s more important to note that n <= 1000 and n^2 = 1 000 000 is a quite normal bound to solve a problem.
The number is 10^8, not 10^7. I had the same misconception.
We must find out who is telling all the beginners that it is 10^7 