I_lOVE_ROMAN's blog

What does mean by sum over all test cases is [something ] in cf problems?
By I_lOVE_ROMAN, history, 3 years ago, In English

There are many problems statement with this written.Actually what does mean by it from the view of time complexity?

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

Comments Comments (3)
| Write comment?
»
3 years ago, # |
← Rev. 2   Vote: I like it +28 Vote: I do not like it

Take an example:

https://mirror.codeforces.com/problemset/problem/1538/C

The statement in this problem says: "It is guaranteed that the sum of n overall test cases does not exceed 2*(10^5)." This means that in every pack of test cases, the sum of the variable n in every test cases in that pack will never higher than the number 2*(10^5)

Edit: The time complexity will (maybe) stay the same if the first pack have a big number n and one test case, while the other one has a bunch of test cases with a lot of small numbers n

→ Reply
»
3 years ago, # |
  Vote: I like it +41 Vote: I do not like it

A test is a single file that your program runs on and must answer within the time limit. Often a test is divided into multiple test cases, and your program is still required to answer the entire file in the time limit. So it must answer all test cases of a single file within the time limit.

For example, let's say that $$$n$$$ is at most $$$10^5$$$. And let's say you can answer one test case in $$$O(n)$$$ time.

Without a sum guarantee, the worst case is that every test case has $$$n=10^5$$$, which will make your solution TLE if the number of test cases is a decent size. And if $$$n$$$ is describing the length of an array, you don't even have enough time to read the input.

One solution the authors might do is lower the constraint on $$$n$$$ for each test case just enough so that a slower solution would still fail. This is sometimes done, but it can be a problem when the slow solution isn't that much slower, and you really need a big test case to distinguish them.

Let's say instead the statement says that the sum of $$$n$$$ over all test cases is at most $$$10^5$$$. Now, the $$$O(n)$$$ solution will pass, because the total time is $$$n_1 + \cdots + n_t\le 10^5$$$ where $$$n_i$$$ is the value of $$$n$$$ in the $$$i$$$-th test case of the file. This will also give the author more flexibility to have some tests with a few very large test cases and other tests with a lot of small test cases. And you as the contestant can stop thinking about test cases as long as you have this guarantee about the sum.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

This limit gives you some idea of how fast your method needs to be. Suppose there are up to T = 1000 test cases, in each of which there are up to N = 10^5 items. Without further limits, your solution would need to be able to handle up to T * N = 10^8 items within the time limit. But if you are told that the sum of N over all test cases does not exceed 10^5, then your solution only needs to be fast enough to cover this number of items all together. There may be 1 test case with 10^5 items, or 1000 test cases with an average of 100 items in each test, or any appropriate combination.

→ Reply