Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### tezk's blog

By tezk, history, 16 months ago,

I tried to solve 1801C-Music Festival. First I also compress the albums as the editorial solution, then normalize all the coolness value to avoid the case the maximum of $a_i$ is too big, then sort the albums in increasing order of the track with maximum coolness. This got me TLE at test case 25

In short, I have a

vector<vector<int>> a(n);


The sort function is

sort(a.begin(), a.end(), [&] (auto a1, auto a2) {
return (a1.back() < a2.back());
});


Instead of sorting, create a map to store the position of albums with each maximum coolness pass

I didn't know about this, so I'm curious what's the time complexity of the sort function in this case ?

• +17

 » 16 months ago, # | ← Rev. 2 →   +32 I think it's O(n^2log(n)) because in the sorting lambda you are passing the vectors by value not by reference, so you make a copy of the 2 vectors for every comparison which is O(n) per comparison. Changing auto to auto& gives AC
•  » » 16 months ago, # ^ |   +8 Interesting. Thanks a lot !
 » 16 months ago, # |   -8 If I were to bet, given the quite strict TL, I’m not sure I agree with aymanrs ‘s hypothesis. I’ve never seen a counter-test where passing vectors by value would degenerate complexity (I conjecture that it’s $O(\log n)$ comparisons per element, yielding correct complexity). Can someone indicate one such test or a strategy to build it and prove me I’m blatantly wrong?However, I do think that the reason why passing by value is slow here and passing by reference is not is memory allocation (one allocates a linear amount of memory, the other allocates linearithmic memory). This adds a condiderate constant factor to the solution.
•  » » 16 months ago, # ^ |   +8 one big vector + many small?
•  » » » 16 months ago, # ^ | ← Rev. 3 →   0 Still, you would need to build a test case where the big vector gets compared with $\omega(\log n)$ elements, which is non-trivial as far as I'm aware (without digging into the intrinsics of how the std::sort algorithm works).
•  » » » » 16 months ago, # ^ |   -37 if you will use merge sort, complexity will be O((sum len)* log(n)). It's because every element used in comparator O(log(n)) times.But std::sort using quick sort algorithm. It's pick element and put lower element at begin and bigger element at end. Then recursive sort. So, if we will pick long vector it will be compared O(len(curr arr)) size.
•  » » » » » 16 months ago, # ^ |   -29 you may use stable_sort: [sorry, can't add link, because my submissions are hidden in this contest, but you can try it by yourself] it's working in O(n log^2 n), but only O (log^2 n) comparisons for every element. So total will be O((sum len) * log^2 n)
•  » » » » » » 16 months ago, # ^ |   -26 hmm, ok, my words are true until C++11since C++11 it's using other one algotihm: https://github.com/gcc-mirror/gcc/blob/d9375e490072d1aae73a93949aa158fcd2a27018/libstdc%2B%2B-v3/include/bits/stl_algo.h#L1950is using aditional functionhttps://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-USERS-4.4/a00978.html#7db47762a47726a861b61ecddd91e12eIt's using not a random element, but median of first, middle and last element and then split by this element.So, in this case, first element is a median what will be found in first execution. You can random_shuffle array and get AC too. [also can't give a link for submission, but you also can check it by yourself. Add random_shuffle(a.begin(), a.end()); before sort]
•  » » » » » » » 16 months ago, # ^ |   -40 So, I think it's a good hack: std::random_shuffle array before sorting to minimize chance of picking big element by separator.But also it's a good hack: using references in your functions)
•  » » » » » » » » 16 months ago, # ^ |   -31 also, if you have a question: why std::sort using such type of sorting instead of merge sort?It's all because of additional memory. If you want to sort elements in-place, you have to use in-place merging. It's not really hard algorithm of merging in O(n log (n)), but if you want to do it in O(n) — good luck, have fun. It's a really hard algorithm with big constant. you can read this article: https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwi3gd-o_Oz9AhVXyYsKHffiDW4QFnoECCQQAQ&url=https%3A%2F%2Fnms.kcl.ac.uk%2Finformatics%2Ftechreports%2Fpapers%2FTR-04-05.pdf&usg=AOvVaw3SELuk7H9SIx22TdHTn9ft
•  » » » » » » » » » 16 months ago, # ^ |   -31 Also you can use make_heap and sort_heap for sorting in place. It’s also unstable, and working O(n log n), but in real life some slower when sort.
•  » » » » » » » » » 16 months ago, # ^ |   +48 I think you should have edited the first comment instead of continuing to reply to it.
•  » » » » » » » » » 16 months ago, # ^ |   +27 I have some misunderstanding…Why did you downvote this thread? It's a lot of interesting things about C++ standards, compilers, algorithms, and features of competitive programming.Only because of a lot of messages? Lol?What difference for you: read one big message or some small ones?If you have questions, or you didn't agree – you can write it here… You're just downvoting an interesting thread and what all.Maybe because it's too hard for your Specialist brain? LMAO.I hope you will be Expert one day…
•  » » » » » » » » » 16 months ago, # ^ |   +24 Sometimes I cant understand codeforces's users, tbh
•  » » 16 months ago, # ^ |   0 As @oversolver said, the test case that got me TLE has 1 big vector and many small one. I have verified that it really is the sorting that kill my solution
•  » » » 16 months ago, # ^ |   +11 I never said otherwise. I was debating whether it's because the complexity becomes quadratic or the constant factor is too big.
•  » » » » 16 months ago, # ^ |   +13 just tested some cases and seems like std::sort make no more than log comparisons per item.and talking about auto vs auto& in comparator generally, I have lot of experience even with pair where reference gives major performance
•  » » » » 16 months ago, # ^ | ← Rev. 9 →   +27 When n is sufficiently large, sorting an ordered array causes the second element to be compared $\Theta(n)$ times. (However, I am still don't know how to construct it so that it reaches the complexity of $\Theta(n^2\log n)$) Code#include using namespace std; int a[10001]; int cmp(int x,int y) { a[x]++;a[y]++; return x Q; for(int i=1;i<=10000;++i) Q.push_back(i); sort(Q.begin(),Q.end(),cmp); for(int i=1;i<=10000;++i) cerr << a[i] << ' '; } If you do random_shuffle first and then sort, then the complexity is also correct. But I don't think there is a sorting algorithm that can do $O(\log n)$ comparisons with worst-case luck.upd: here's a sorting algorithm named "Bitonic Sort" can do $\Theta(\log n)$ comparisons for each element with worst-case luck.
•  » » 16 months ago, # ^ | ← Rev. 3 →   +26 Let's keep things simple and assume std::sort is a merge sort algorithm. For the merge sort algorithm conjecture that it's $O(logN)$ comparison per element is blatantly wrong. It has a total $O(N*logN)$ comparison, but nowhere guaranteed that it's $O(logN)$ comparisons per element. Here is one such trivial counter-test case. SpoilerInf | 1 | 2 3 | 4 5 6 7 | 8 9 10 11 12 13 14 15 | ... Inf will be compared with all elements.I do not want to dig into the intrinsics of how the std::sort algorithm works. What I know is std::stable_sort is implemented using merge sort. Here is a working example
•  » » » 16 months ago, # ^ |   +3 JFYI: you can merge two arrays with O(log(n)) comparison for every element.then you have two arrays A and B just do binary search how many element you have to use from A until first B element. It will be work in O(log(ans)), ans then you will move this elements in O(ans), so total is O(ans).To do it you can firstly check all powers of two until first negative result and then search between $2^i$ and $2^{i+1}$Total will be O(n)
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   +16 I never claimed all algorithms have $O(N)$ for an element. I just claimed native textbook code for merge sort can take $O(N)$ per element.Also, can you elaborate more on your analysis?Either I do not understand your algorithm, or it's $O(log^2N)$ comparisons per element, with the overall complexity being $O(N*log^2N)$Merge sort has $O(logN)$ layers, and if we use your algorithm as an immediate step, it will take $O(log 2^i)$ comparisons on $i$ step, totalling $log^2(N)$ per element.
•  » » » » » 16 months ago, # ^ |   +3 I told about merge component only. In merge sort — yes, it will be $O(log^2(N))$ comparisons per element.
•  » » » 16 months ago, # ^ |   0 Yes, that's indeed true. But for randomized quick sort on the other hand, the number of comparisons seems to be $O(\log n)$ per element on average.Proof: An element $i$ will be compared to any other element: when $i$ is a pivot (expected number of comparisons is $\sum{P(\text{sequence has }l\text{ elements}) \cdot l \cdot 1/l}$ = $1$) when $i$ is compared to a pivot (expected number of comparisons is equal to expected depth, which is $O(\log n)$). As far as I'm aware, std::sort is more like quick-sort than merge-sort, so I thought maybe it behaves similarly.
•  » » » » 16 months ago, # ^ | ← Rev. 2 →   0 about std::sort — I wrote a thread under your previous comment. It downvoted a lot (Lol), but you can open comments.https://codeforces.com/blog/entry/114167?#comment-1014962
•  » » » » 16 months ago, # ^ | ← Rev. 5 →   +8 If I'm the problem setter, here is one way I will try to hack quick-sort solutions.Here, $N$ is up to $200000$. Let's add $100$ vectors of length $1000$ each, rest $100000$ vectors with length $1$. For a particular test case, these large vectors get picked up as the first pivot with probability $0.001$. Add 100 such test cases, and the probability of avoiding TLE is $(1-0.001)^{100} = 0.904$; it's too risky when only one submission will be evaluated during system tests. It might work for educational rounds where people can make $10$ submissions. Parameters can be tweaked. Works well when sum is up to 2e6.
•  » » » » » 16 months ago, # ^ |   -8 And what's wrong with having a pivot of length 1000? Only 100 comparisons on each level of recursion will look through all these 1000 elements, other comparisons will stop at length 1.
•  » » » » » » 16 months ago, # ^ | ← Rev. 3 →   0 The comparator in the blog copies instead of pass-by reference. So it will make 1e5 copies of vector length 1000. Will probably tle for sumN 2e5. A sure shot tle if sumN is raised to 2e6.