huzaifa242's blog

Vector Implementation gives TLE/MLE where as Set implementation Gives AC.
By huzaifa242, history, 6 years ago, In English

In past few days I have faced this problem very frequently. Implementing same Logic with set gives AC where as vector implementation gives TLE OR MLE.

Question 1

TLE Solution

AC Solution

I just changed the set implementation to set in order to check the running time.

Question 2

MLE Solution

AC SOlution

Above is the example of MLE v/s AC.

If anyone could tell me what I am mising...

Thanks in Advance.

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

»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

q.erase(q.begin()) in vector is O(n)

Edit: to be more specific, it is linear on the number of elements after the erased element, so it's O(1) if you erase from the end of the vector only.

set is O(log(n)) wherever the element is

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

    OKay. But Why MLE in second case??

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

      Im not sure, but there are differences between the 2 codes other than set/vector swap.

      Maybe that led to the loop not finishing correctly.

      → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

For the second one (MLE) you are pushing repeated elements so it becomes exponential. With set that doesn't matter because a set has unique elements. Your vector solution passes if you sort and use unique to remove repeated elements. http://mirror.codeforces.com/contest/1072/submission/45192350

→ Reply