Many questions contain a condition similar to this:
Sum of N doesn’t exceed 10^5 for all test cases.
I can never understand the significance of this line, is there any kind of optimization/catch that the author is usually suggesting here most of the times? Can anyone explain the significance of such a condition in a question? Preferably with an example problem would be better.
@anon42667337, See sum of N doesn’t exceed 10^5 means,
Let’s say for example, for a problem,
CASE 1: if T = 100 and N = 10^5, then, if you iterate over the 10^5 elements, then in the worst case, you will end up doing T * N which is 100*10^5 = 10^7 iterations, which can run smoothly in less than or equal to 1 sec.
Because for ex, in java, 10^7 iterations will run in 1 sec.
Now,
CASE 2: IF T = 10^5 AND N = 10^5, You can’t even linearly iterate over all the elements to find something, because T*N will be 10^10, Hence, they do tell, the sum of N over all test cases will not exceed 10^5 something like that, such that there woudn’t be any TLE, but your solution will be tested against T test cases in a single go.
Also adding to @stupidhelmet’s answer.
Sometimes keeping T high is a necessity (for verifying correctness) as well as we need few test cases when N is huge ( for checking time complexity)
Because to differentiate b/w unptimized O(n) and worst case optimized O(n^2) we need value of N as large as possible.
Also we need multiple test cases to verify correctness.
So to achieve both of these author will keep few values of N high and then he will use many test cases with smaller values of N .
So that it can take advantage of both ( more test cases and big value of N).
Hence author is forced to use constraints like
T=10^5 and N=10^5
And to allow all solutions to pass he will have to keep sigma N over all T <=10^5 or 10^6
I see, thanks for the clarification.