brawll's blog

What do they convey?
By brawll, history, 8 months ago, In English

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.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by brawll (previous revision, new revision, compare).

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Basically, that means, that you are able to read input in given time at least. Or i didn't get you?

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Learnt a lot, thanks mate

    → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

if ur solution is O(n) per testcase, sum of the complexities will also be O(n)

→ Reply
»
8 months ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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$$$.

→ Reply