Hello,
I was doing this problem and was getting TLE on the last two test cases.
On a whim, I decided to replace my sort() functions with stable_sort(), and the solution passed.
According to this benchmark, stable_sort uses less iterations overall in g++ 5.3.0 and clang++ 3.7.0 than sort on average.
In the problem I sorted a vector<pair<int, pair<int,int>>>, which would take up to three comparisons each time. I considered this a possibility for the lower constant factor of stable_sort for this problem, but was not able to replicate the results.
You can try to submit my solution and it should AC. But if you replace "stable_sort" with "sort" it will TLE.
Does anyone know which types of cases stable_sort can outperform sort?
Edit: Programs are compiled with gcc/g++ 4.8.2 using the "-O2" optimization flag and "-lm" to access the math library, and also "-std=c++0x" to enable support for C++11.
If you mean the column
Iterations(next toTime(ns)andCPU(ns), then you are misinterpreting the benchmark completely. The column says, how often the benchmark was repeated. Not how many cycles / iterations the algorithm uses. In all testsstd::sortwas faster thanstd::stable_sort.Thanks. Do you know any specific case where this is not true? (where stable_sort is faster)
std::sort generally is an Introsort, that first does Quicksort, but might fall back to heapsort (to guarantee worst case O(nlogn) vs O(n^2) of Quicksort). When that fallback happens, it can probably be overall slower than Mergesort (std::stable_sort) from the beginning. Read this for more information on Introsort.
Heapsort and Mergesort have a higher constant factor than Quicksort.
No.
And I also suspect, that in your code
std::sortis not slower thanstd::stable_sort. I haven't read the problem statement, but from what I can see in you solution is that the complexity isO(n*m). This will dominate every sort that you do. So maybe it was just a coincidence, e.g. time limit of 1 sec, and the first time you submitted it run in 1.01 sec, and the second time it run in 0.99 sec.I checked it (twice), and indeed the stable_sort version runs in ~1.95s, so pretty close to TL. But for test 8, stable_sort took 1.15s vs sort 1.35s, seems significant. For test 9, stable_sort 1.6s and sort TLE...
Really strange...
Time limits are usually set with reserve. There is probably better solution. Sorting n*m can be avoided as there no more than n+m unique values. You can sort list of lengths and when you take length iterate over all the edges in that row/column.
I've run it multiple times and the stable_sort solution always manages to squeeze right under the time limit.
Also the complexity is nmlog(nm)
Auto comment: topic has been updated by brdy (previous revision, new revision, compare).
Generally,
stable_sortimplementations make much less comparisons as opposed tosort. It's also possible thatstable_sortdoes less memory moves, but I'm not sure here.