Блог пользователя teejorob

Help required for explanation of TLE in this case
Автор teejorob, история, 4 часа назад, По-английски

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?

  • Проголосовать: нравится
  • -6
  • Проголосовать: не нравится

»
3 часа назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 часа назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
    • »
      »
      »
      3 часа назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        3 часа назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить