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

Автор techwiz911, история, 9 лет назад, По-английски

I was attempting the following question 310D

Here is my submission that timed-out TLE

And here is my submission that was accepted AC

As you may have observed, the only change I made from the TLE code to AC code was

  it=lower_bound(s.begin(),s.end(),mp(lo,o));

to

  it=s.lower_bound(mp(lo,o));

where "it" is a set iterator.

Just changing this, the time on Test #11 was reduced from >3000ms to 264ms. Can any one shed some light on why this happened? Thank you.

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

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I think without be sure that the first runs in 0(N), and the second in O(logN).

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

    Okay. But why the change in behaviour for the same function? I mean what goes behind the curtains?

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

See complexity of these methods 1 2

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

    Thanks a lot. Glad I got to know this now, getting TLE in a contest because of this would have hurt.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Actually you will find everything about C++ in this site. So, you can always check anything there.

http://www.cplusplus.com/

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

The key is, that the lower_bound in the algorithm package has no knowledge about the internal structure of set. It can do a binary search for random access containers, but not for set. For set, it has to go through all elements step by step.

On the other hand, set's lower_bound can leverage its knowledge about its internal structure, and can do it log n runtime.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    One minor technical detail is that the lower_bound function from algorithm actually always does a binary search.

    It's just that for forward iterators such as set::iterator that are not random access iterators advance(iterator,constant) is slow. More precisely, you need roughly k operations to advance an iterator by k, and this is what makes the total time complexity linear instead of logarithmic.

    (Hence, lower_bound on a container that only has forward iterators will usually be a bit slower than find.)