### brawll's blog

By brawll, history, 3 months ago,

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.

• +1

 » 3 months ago, # |   0 Auto comment: topic has been updated by brawll (previous revision, new revision, compare).
 » 3 months ago, # |   0 Basically, that means, that you are able to read input in given time at least. Or i didn't get you?
 » 3 months ago, # | ← Rev. 2 →   +28 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 worksn <= 75: O(n^4) probably worksn <= 400: O(n^3) probably worksn <= 7500: O(n^2) probably worksn <= 6*10^6: O(n) probably worksHowever, 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.
•  » » 3 months ago, # ^ |   +2 Learnt a lot, thanks mate
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 n <= 20 is mostly bitmasks if not ez problemsn <= 500 is n^3 (prolly range dp?)n <= 5000 is n^2n <= 1e6 is n logs could be added to all of the aboven <= 1e7 is to avoid log in most cases
 » 3 months ago, # |   0 if ur solution is O(n) per testcase, sum of the complexities will also be O(n)
 » 3 months ago, # | ← Rev. 4 →   0 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 \$ $O(TotalTC) = \sum O(f(n_i)) \approx O(\sum f(n_i)) \le O(f(\sum n_i)) = O(f(N))$Hence, if your solution works on the bound on N, it will work for all test cases within TL
•  » » 3 months ago, # ^ |   0 bhai mainu coding pasand hai itni math kithun le aaya. (●'◡'●)
•  » » » 3 months ago, # ^ |   0 Mainu math zyada pasand ae
 » 3 months ago, # | ← Rev. 2 →   0 Consider this input: The first line of the input data contains an integer $n$ ($1 \leq n \leq 10^{2}$).The $i$-th of the following $n$ lines contains an integer $m_i$ ($1 \leq m_i \leq 10^{4}$) followed by $m_i$ integers $a_{i1}, a_{i2}, ..., a_{im_{i}}$ ($1 \leq a_{ij} \leq 10^{9}$). 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: It is guaranteed that the sum of $m_i$ does not exceed $2 \cdot 10^{4}$. 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$.