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

# | User | Rating |
---|---|---|

1 | tourist | 3822 |

2 | Benq | 3745 |

3 | ksun48 | 3560 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3532 |

6 | Um_nik | 3489 |

7 | maroonrk | 3424 |

8 | Petr | 3380 |

9 | sunset | 3338 |

10 | ecnerwala | 3336 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 207 |

2 | Errichto | 181 |

2 | awoo | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 172 |

7 | tourist | 172 |

9 | SecondThread | 170 |

10 | rng_58 | 166 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/31/2021 16:18:51 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Take an example:

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

The statement in this problem says: "It is guaranteed that the sum of

noverall test cases does not exceed 2*(10^5)." This means that in every pack of test cases, the sum of the variablenin 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

nand one test case, while the other one has a bunch of test cases with a lot of small numbersnA

testis a single file that your program runs on and must answer within the time limit. Often a test is divided into multipletest 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.

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