### I_lOVE_ROMAN's blog

By I_lOVE_ROMAN, history, 6 weeks ago,

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

• +7

 » 6 weeks ago, # | ← Rev. 2 →   +28 Take an example:https://codeforces.com/problemset/problem/1538/CThe 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
 » 6 weeks ago, # |   +41 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.
 » 6 weeks ago, # | ← Rev. 2 →   -12 I used to think , how can someone solve question with 10^4 testcases and 10^5 N ...