YogeshZT's blog

Upper_bound giving TLE under different approaches
By YogeshZT, history, 4 months ago, In English

I was doing the question 1498B - Box Fitting. Here are my two submissions 271307925 and 271307851. One of the approaches works correctly while other gives TLE. The only difference between them is how I initialize the iterator 'it' using the upper_bound function.

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

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

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

If I am not mistaken, the TLE approach is looking for an upper bound of x in the block of memory delimited by $$$[m.begin, m,end()) $$$, while the AC code actually makes use of multiset::iterator to find the answers.

The TLE approach may work with vectors, but be careful when using it with other data structures.

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

What i have found is that multiset.upper_bound() is faster than upper_bound(multiset.begin(),multiset.end()) and the reason attributed is the fact that multiset.upper_bound is optimized to take advantage of the internal structure of a multiset, which is typically implemented as a balanced binary search tree (e.g., a Red-Black Tree). The member function can directly leverage the tree's properties to perform the lookup efficiently as compared to the general upper_bound function which is from algorithm header file and it is not designed to take advantage of the properties of multiset , which the member upper_bound function does.

You can check this out too if you want : https://stackoverflow.com/questions/64536493/difference-between-set-upper-bound-and-upper-boundset-begin-set-end-stl

Sorry if there is any grammatical error.

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

    Thanks for the answer. So it means there might be more functions which have varied time complexities depending on whether we use them in a way which utilizes the advantage of the data structure we use them with?

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

      most likely all the member function to particular data structures have been implemented in a way to leverage the specific properties of data structure to its use as compared to generic one.

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

lower_bound(b.begin(), b,end(), val) is $$$O(n)$$$,

while b.lower_bound(val) is $$$(\log n)$$$

→ Reply