teejorob's blog

Help required for explanation of TLE in this case
By teejorob, history, 5 hours ago, In English

Question : here

Submission 1 (TLE) : 293404599, used vector of size 2*1e5 for frequency storage for future lookup

Submission 2 (passed) :293423236, used map for same purpose

Can someone explain why I encountered TLE in the first case?

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

»
4 hours ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

This problem is a multiple test case problem, and it has a constraint on the limit of the sum of all $$$k_i$$$, so if you use a map the total number of elements inserted in the map will also not exceed that value. However, if you use a vector of size $$$2 \cdot 10^5$$$, it means you're also having a lot of unused indices which also takes some time to be allocated and initialized. In the worst case, with $$$10^5$$$ test cases, the sum of the size of these vectors will be $$$2 \cdot 10^{10}$$$, which is too large to be created within the time limit.

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

    I was thinking of O(1) lookup using vector compared to map, but as you highlighted the excessive vector creation over test cases, makes sense now. Thanks

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

      If you want to achieve that $$$O(1)$$$ lookup you can do this instead: 293426305

      Make the vector once in the global scope, and initialize each used indices after each test case.

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

        yeah i saw your submission just now, making the vector global and resetting the used indexes after each test case. :D

        → Reply