I_lOVE_ROMAN's blog

By I_lOVE_ROMAN, history, 6 weeks 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

»
6 weeks ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

Take an example:

https://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

»
6 weeks 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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

I used to think , how can someone solve question with 10^4 testcases and 10^5 N ...