kuldeep_devulapally's blog

How should we decide the complexity of the code based on input description given?
By kuldeep_devulapally, history, 13 days ago, In English

I have given two input description given for two different problems in codeforces.

Description-1:-

Each test consists of multiple test cases. The first line contains a single integer t (1≤t≤104) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer n (2≤n≤10^5) — the length of the array a.

The second line of each test case contains n integers a1,a2,…,an(0≤ai<n) — the elements of the array a.

It is guaranteed that the sum of n over all test cases does not exceed 10^5.

Description-2:-

The first line contains a single integer t (1≤t≤5⋅104) — the number of test cases.

The only line of each test case contains a single integer n (1≤n≤10^5).

Here my doubt is can we perform O(n) on both the questions or not and performing O(n) operations on 2nd one is getting me TLE. So how should i approach questions based on their complexity?

How important is this line in 1st input description:- It is guaranteed that the sum of n over all test cases does not exceed 10^5.

PS:- Thank You! my doubt has been clarified and what we can understand from this line is the sum of n over all testcases doesn't exceed 10^5 and we can perform O(N) operations on this problem within given time limit so the total numbers inputting will be T+N i.e 10^4+10^5 not T*N i.e 10^4*10^5 which can be done within 1 sec...

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).

→ Reply
»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

I assume you meant to write $$$10^{5}$$$ instead of $$$105$$$, that line is extremely important because then there could be $$$5\cdot10^{4}\cdot10^5 = 5\cdot10^{9}$$$ integers in the input. Reading that under a few seconds is impossible.

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

The line It is guaranteed that the sum of n over all test cases does not exceed 10^5 is a very important line. The line means that there are T integers $$$n_1, n_2, ..., n_T$$$, $$$n_i$$$ being the $$$n$$$ in i-th test case and $$$n_1 + n_2 + ... + n_T <= 10^5$$$. Now, inputting T integers $$$n_1, n_2, ..., n_T$$$ is easy. But, there are $$$n_i$$$ more numbers in the i-th test case but as we know that sum of all $$$n_i <= 10^5$$$, then we are just inputting at most $$$T + 10^5$$$ numbers, which can be easily done in 1 second.

→ Reply
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    So basically the complexity will be O(T+n) not O(t*n)

    → Reply
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah. That line just tells you that you don't need to take test cases into consideration, so you can just solve for T=1 and N having maximal value.

      → Reply
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by kuldeep_devulapally (previous revision, new revision, compare).

→ Reply