There are many problems statement with this written.Actually what does mean by it from the view of time complexity?
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
There are many problems statement with this written.Actually what does mean by it from the view of time complexity?
Name |
---|
Take an example:
https://codeforces.net/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
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.
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.