alphaaditya's blog

Why does use of vector gives TLE while map does not ?
By alphaaditya, history, 41 hour(s) ago, In English

In this submission -> 306874451 as you go through the solve function you will see that I have used 

vector<ll> freq(2e5+1,0);

as you can see it got Time Limit exceeded on test case 2, after replacing the vector with map in the following submission -> 306878312

map<ll,ll> freq;

It got accepted, now according to my knowledge map takes O(log N) time to access its elements while vector takes O(1) time.

So in the worst case scenario shouldn't the vector be better ?

Problem Link -> 1775B - Gardener and the Array

[BTW This is my first blog so please forgive me if I made any mistake.]

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
41 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

In each test case, you are creating a vector of size 2e5. So in total 1e5 test cases* 2e5 size of vector created = 2e10, which will obviously give tle.

Map is dynamic so will never reach the size, even if at worst case, k can be at most 1e5 and in that case t would be 1 as it is guaranteed that sum of k won't cross 1e5.

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

    but then shouldn't it give memory limit exceeded error instead of time limit exceeded ?

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

      Not necessarily — your solution used both too much memory and time, but probably exceeded the TL before the ML

      → Reply
    • »
      »
      »
      40 hours ago, # ^ |
        Vote: I like it +32 Vote: I do not like it

      The arrays created in the test cases doesn't co-exist, once it's done being used, it'll free itself, so no, it'll not MLE.

      However, creating and allocating an array takes $$$\mathcal{O}(n)$$$

      → Reply
      • »
        »
        »
        »
        40 hours ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        Ok so if creating and allocating an array takes O(n) time then for each test case I am creating and allocating 2e5+1 size array so for all the test cases the time complexity could be 1e5 * 2e5 = 2e10 which results in TLE. is this correct ?

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

      Memory of vector is freed when it goes out of scope so mle isn't exceeded. It's just allocation time that's taking a lot of time giving tle.

      → Reply
»
40 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

you are creating a vector of size 2e5+1 this takes a lot of memory, on the other side, each key in the map is inserted dynamically

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

    yes you are right but if it is consuming too much memory shouldn't the error be memory limit exceeded ?

    → Reply
»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro the declaration of the vector had made a complexity of $$$O(TN)$$$。 if you want to use the vector, you have to declare it globaly or just apply for a vector with size $$$N$$$ every time.

→ Reply