abba5's blog

TLE because of sort using rbegin
By abba5, history, 4 years ago, In English

I was trying to submit this -> Remove Max Number of Edges to Keep Graph Fully Traversable question.
but I got TLE because of sort using rbegin 

sort( edges.rbegin(), edges.rend())

but after change with comparator funtction code got accepted. 

sort(edges.begin(), edges.end(), [&](vector <int> &a, vector <int> &b){
            return a[0] > b[0];
        });

Submission Using rbegin

Submission Using comparator

I tried to run this in local and got similar performance but when I used some different build command I got 2x time difference for $$$N = 10^5$$$

Build command:

  1. g++ a.cpp

  2. g++ -std=c++17 -Wshadow -Wall -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG -DLOCAL a.cpp

output using 1st build command:

0.0290290006s
0.0652360022s

output using 2nd build command:

0.9816750288s
2.1033749580s

Following code I used for bench-marking.

Bench-marking code

Can anyone explain why this time difference happening?
Will this happen in code-forces also?

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

Comments Comments (3)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +4 Vote: I do not like it

same thing happened to me last month..... was using sort(vector.rbegin(),vector.rend()) and got tle.....after the contest i used sort(vector.begin(),vector.end(),greater()) and then got AC... i used to thought that complexity of both sorting is same

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

Can anyone explain why this time difference happening?

It is happening because you have used the compile flags without knowing what they do.
-D_GLIBCXX_DEBUG: it inserts some debug / sanity checks that can really slow your code down. For example, you may get $$$O(n)$$$ complexity for std::binary_serach.
And you forgot the most important flag -O2. With -O2 both of them takes same time.

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

That's why I prefer using comparators

→ Reply