What do you think of the time complexity of the following code?
multiset<int> S;
for (int i = 0, x; i < n; ++i) {
cin >> x;
S.insert(x);
}
for (int i = 0, x; i < n; ++i) {
cin >> x;
cout << S.count(x) << " ";
}
For me, I thought it should be $$$O(n \log n)$$$ until yesterday, because I thought STL implemented it by adding a field count to set, but actually this code can be as bad as $$$O(n^2)$$$, because the time complexity of S.count(x) is $$$O(\log n + k)$$$ instead of $$$O(\log n)$$$, where $$$k$$$ is the number of occurrences of x in S.
The solution is to use map in this case:
map<int, int> M;
for (int i = 0, x; i < n; ++i) {
cin >> x;
M[x] += 1;
}
for (int i = 0, x; i < n; ++i) {
cin >> x;
cout << M.count(x) ? M[x] : 0 << " ";
}
I've stepped into this trap in yesterday's educational round, my solution of D was hacked because of this. I could become master if I didn't made that mistake :(
I guess this shouldn't be too surprising, since you're counting occurrences of an item (and a multiset is effectively a balanced binary search tree with duplicates allowed). One way to do this with a treap, is to perform two split operations so that one of your treaps has all elements equal to $$$x$$$, and then outputing the size. I'd imagine a C++ STL BBST generally wouldn't have that kind of functionality.
Edit: I think post brings up a good point since
.count()is often used to check the existence of something, so this is a trap people should watch out for (credit to bitset for bringing this up to me).if it was set (not multiset), I think using count to see if it's there or not is totally fine.
multiset is overpowered don’t say anything bad about my love >~<
I thought, that
std::stack.pop()returns last (removed) element.C++ users, why
std::stack.pop_top()doesn't exist? Do you really like writing 2 func_calls instead of 1?Because that is how optimization works. If we just copy from
top()as a reference, that turns out as one copy. However if we were to makepop_top(), we would no longer have that element we needed as a reference. So we need to copy once first, and return that, and outside the function there is another copy. Do we like using 2 copies instead of 1? Probably not.Excessive copies can be solved by using
std::move. The function can be easily implemented in the library like this:RVO will ensure that no copies are ever made.
I always use
.countas it's O(N).Yeah, a common trap.
A way to think about it is: why doesn't multiset just add a count for equal items? Recall that a multiset can store arbitrary objects with arbitrary comparison operation, not just integers. For example, you can have a class for contest participants, and use a multiset to order participants by their current rating. But they are still individual participants, each with their handle and other data. You can't replace the whole class by just the value you use to compare them, and count the occurrences of that value.
If you wish a count, you can make that wish explicit in your program by using map (value -> count).
Notice that proving that it works in $$$O(k + \log n)$$$, and not in $$$O(k \cdot \log n)$$$ is a nice little exercise to check your understanding of balanced binary search trees.
Can't we just say that we are applying binary search to find the pointers, lower_bound pointer and upper_bound pointer (in O(lg(n)), and then we are just finding the distance between the pointers, since the set is not indexed we can only do this in O(k) where k is the actual distance (number of occurrences of the element). So, it will be O(lg n + k).
Q1 : We can do this in O(lg(n)) using ordered_set (which can tell the index; the number of elements less than this element)?
Kindly share your proof / s as well.
How would you find a distance between two pointers in $$$O(k)$$$? That's exactly the question. I claim that in general for an std::set it is not possible. One needs to go to the next pointer one-by-one, and each step takes $$$O(\log n)$$$ time. So why is it $$$O(k + \log n)$$$, and not $$$O(k \cdot \log n)$$$?
It takes O(k), resource : https://www.geeksforgeeks.org/stddistance-in-c/
Its written in the time complexity that O(1) for those which have random access and else O(n).
Actually, I don't think each step takes O(lg(n)).
I wouldn't believe everything that is written on geekforgeek. I am pretty sure it takes $$$O(k + \log n)$$$ time. Because, for example,
it++takes $$$O(\log n)$$$ time, and not constant. And well, that's exactly what my question is: WHY it works in this time :)Would this be a good summary of the proof?
Let $$$T$$$ be part of the BBST containing $$$a$$$, $$$b$$$, $$$\text{lca}(a,b)$$$, and the stuffs. Basically the things passed through while searching from $$$a$$$ to $$$b$$$ manually. Now the complexity of a call of
distance(a,b)is bounded by the complexity of DFS on $$$T$$$. The size of $$$T$$$ is bounded by $$$\mathcal{O}(dist+\log n)$$$. So the number of edges passed is bounded by $$$\mathcal{O}(dist + \log n)$$$. QED.I know that there are a lot of things omitted here but I guess here's the gist of it. Refer to some BBST invariants I forgot wherever possible.
I think you're right, yes. But the fact that the size of this subtree is limited is exactly the place where you need to apply some knowledge of how BBSTs work.
Honestly I would have argued that the size of that subtree is limited to $$$\mathcal{O}(dist+height)$$$ for any general BST. It's just that the painful case exists such that the height is $$$\mathcal{O}(n)$$$, where $$$a$$$ and $$$b$$$ exists on the rightmost node of the left subtree and the leftmost node of the right subtree, so $$$size=\mathcal{O}(dist)$$$ simply does not hold here.
UPD: Just came up with idea to prove this. A walk from $$$a$$$ to $$$b$$$ is very structured, in fact it is really just Subtree->Path->Subtree. The path is of length $$$\mathcal{O}(height)$$$, and the two subtrees are of size $$$\mathcal{O}(dist)$$$. So this proves it.
Whenever I had to check if an element was present in a set I used .count() instead of find() and one day I used the same on a multiset and got TLE, I also learned it the hard way :)
You may use lower bound (or/and upper bound) for counting in multiset. That will be in log n (hopefully I'm correct)
Recall that STL can't calculate the distance of two iterators of a (multi)set in constant time.
Phh sorry and thank you. I need to look it up.
Counting can be done using a map but I tried to act smart by using count as find function to avoid !=s.end() though I still use count instead of find in sets
Indeed .