ConstructorU taught me a lesson

Revision en1, by shiny_shine, 2024-02-03 12:14:21

Abstract

  1. Never apply a binary search on std::list.
  2. If you want to make a custom _Comp function for std::set , write down as many instructions to distinguish elements in the set as possible. When I was solving one of the problems in the ConstructorU's Open Cup's Practice Round, I wrote this
lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){
    return x[p[a]]<x[p[b]];
}),idx);

when lst is a std::list . I will insert a permutation with a size about $$$2\times 10^5$$$ in it.

But after I waited for a half minute, I killed the process.

So I took a look in the file stl_algobase.h , then deep in the file stl_iterator_base_funcs.h , I found the function __advance which drives lower_bound and other binary-search functions designed for containers with bidirectional iterators:

template<typename _BidirectionalIterator, typename _Distance>
    inline _GLIBCXX14_CONSTEXPR void
    __advance(_BidirectionalIterator& __i, _Distance __n,
	      bidirectional_iterator_tag)
    {
      // concept requirements
      __glibcxx_function_requires(_BidirectionalIteratorConcept<
				  _BidirectionalIterator>)
      if (__n > 0)
        while (__n--)
	  ++__i;
      else
        while (__n++)
	  --__i;
    }

I was shocked because its time complexity is $$$O(n)$$$ .

Considered that vector may solve this problem but have a higher time complexity when massively insert elements in the front of it, I used set instead, and modified the lambda function I wrote above to the _Comp function of it.

It passed the sample, but it got a Wrong verdict.

When I tried to debug, I was confused when I saw that the set said $$$4=5$$$ . Then, I found that $$$x[p[4]]=x[p[5]]$$$ in my input.

So I modified the function _Comp a bit to this:

lst.insert(lower_bound(lst.begin(),lst.end(),idx,[&](int a,int b){
    if(x[p[a]]^x[p[b]])return x[p[a]]<x[p[b]];
    return a<b;
}),idx);

Then, it passed the test.

Thanks ConstructorU, you taught me a great lesson.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English shiny_shine 2024-02-03 12:31:11 63
en5 English shiny_shine 2024-02-03 12:17:06 0 (published)
en4 English shiny_shine 2024-02-03 12:16:38 24 Tiny change: '.\n\n[cut]\n\nDetail' -> '.\n\n[cut] I think it's important.\n\nDetail'
en3 English shiny_shine 2024-02-03 12:16:05 50
en2 English shiny_shine 2024-02-03 12:15:28 24 Tiny change: '.\n\n[cut]\n\nWhen I' -> '.\n\n[cut] I think it's important.\n\nWhen I'
en1 English shiny_shine 2024-02-03 12:14:21 2168 Initial revision (saved to drafts)