So I gave my first CF round yesterday 913 (Div. 3) & I saw these lines
"It is guaranteed that the sum of n over all test cases does not exceed 2*10^5" or
"It is guaranteed that each line contains at least one letter and the sum of the lengths of the lines does not exceed 10^6"
I get it that they are probably trying to convey time limit but still exactly what do they mean (not the literal meaning)/how are they conveying that through that specific number.
Auto comment: topic has been updated by brawll (previous revision, new revision, compare).
Basically, that means, that you are able to read input in given time at least. Or i didn't get you?
Typically, the bounds on the problem indicate something about the worst runtime that a solution can have while staying within the time limits. This bound can help you determine how much you need to optimize your solution. Here is my general rule of thumb:
n <= 10: anything works
n <= 75: O(n^4) probably works
n <= 400: O(n^3) probably works
n <= 7500: O(n^2) probably works
n <= 6*10^6: O(n) probably works
However, some input/outputs on problems give you multiple cases to solve at once. Since each input/output could have something along the lines of 2*10^5 numbers, it would make the problem significantly harder than just solving one case.
By placing this restriction, you can almost ignore the fact that multiple test cases are being run. That is, if your problem is able to run for a single test case that has a bound of 2*10^5, it almost definitely can for split test cases that sum to 2*10^5. The only case where this isn't true is if you need to do significantly large calculation regardless of the size of n, which could cause some issues if there are many test cases.
Learnt a lot, thanks mate
n <= 20 is mostly bitmasks if not ez problems
n <= 500 is n^3 (prolly range dp?)
n <= 5000 is n^2
n <= 1e6 is n
logs could be added to all of the above
n <= 1e7 is to avoid log in most cases
if ur solution is O(n) per testcase, sum of the complexities will also be O(n)
If your solution complexity is $$$O(f(n)) \ge O(n^k), k \in R, k \ge 1, n \in N$$$ per test case with n inputs such that $$$\sum n_i = N \ $$$
Hence, if your solution works on the bound on N, it will work for all test cases within TL
bhai mainu coding pasand hai itni math kithun le aaya. (●'◡'●)
Mainu math zyada pasand ae
Consider this input:
There are at most $$$10^{6}$$$ elements in the input, which means we can only look at each one a constant or logarithmic number of times.
Now suppose we add this line:
Now we can iterate over all pairs of values in the input no problem.
What I'm trying to say is that very often, the complexity is in terms of the size of the data (which might be the sum of some values in the input in this case), and not in terms of a single value, like the variable $$$n$$$.