Today when I took part in the Round #740 solving problem D. Top-Notch Insertions, my submission failed on test 2 without knowing why. After asserting I found that rope contains unwanted contents and I didn't fix the problem during the contest.
However, when I replace all __gnu_cxx::rope.erase(x) into __gnu_cxx::rope.erase(x, 1), my code works fine (idk if it will pass system test or not; at least, it passes asserting that all elements are rolled back to the initial state).
Then! I found it unbelievable to see the following code from here:
Look at the line 2318, comments: Erase, single character.
However, it calls erase(__p, __p + 1);, who will erase __p + 1 characters starting from the position __p.
I found it incredible since it's part of libstdc++. I don't know if there's a way to report such failure. Could anyone tell me if I can do something with it? (or instead, NEVER USE SUCH FUNCTION IN THE FUTURE)
Thank you!
UPD: I've submitted the bug to gcc.
Fortunately, it's quickly replied by Jonathan Wakely. Unfortunately, just exactly as adamant predicted, Jonathan Wakely wrotes:
We should just delete this class, so I don't have to keep fixing bugs in code that nobody uses or cares about.
I didn't even know something like Rope existed. Is this DS very useful at higher levels in CP?
Generally speaking, it's a
listthat can random access. It can be useful when you don't want to implement a balanced search tree.To some extent. See this blog. It's terrifically slow, tho.
Sure. I modified and resubmitted the code, got TLE on $$$m = 2\times 10 ^5$$$.
My submission with
ropepasses right under the time limit with 2.729/3s, if you're interested.Thanks for finding this bug. I will avoid using gnu c++ stuff in the future!
Cool!
I've made a subtle change to your code, 127004930, got a 1.528s result. I remove the pop back operation and copy the whole rope at the beginning of each test case. The assignment operation is $$$O(1)$$$, since it's a persistent structure.
But it's still quite slow. In fact, $$$2\times 10^5$$$ pop back operations had made more than $$$1$$$ second gap between two submissions. If you use one extra operation in the loop, boom -- TLE.
So, consider prepare a splay or treap next time, if the time limit is not as optimistic as this problem.
Wow, thanks!
I never knew that assignment was $$$\mathcal{O}(1)$$$. When you say
it's a persistent structure, do you mean that it creates (amortized $$$\mathcal{O}(\log (\text{size}))$$$) new nodes each time the tree is updated? Like an persistent segment tree? Sorry for asking. I can't for the life of me understand the documentation.And since this is a dynamic tree, I'd imagine that the code is very cancerous. :P
Not amortized but strict (or in expectation?) $$$O(\log (\mathrm{size}))$$$. If I understand the document correctly, it was implemented as something like persistent treap. When you replace the character at position $$$i$$$ for example, it will split the original sequence into $$$[0, i - 1]$$$ and $$$[i + 1, n - 1]$$$, then merge $$$[0, i - 1]$$$, new character, $$$[i + 1, n - 1]$$$ into one. So it only need to implement split and merge to support all kinds of operation, both can be done in $$$O(\log (\mathrm{size}))$$$ time.
Oops, I should have said high-probability $$$\mathcal{O}(\log(\text{size}))$$$ instead of amortized.
Thank you for your help today!
Shocking! Is this just again that the GCC implementation is very poor? My own contest submission passes the time limit pretty easily using Data.Sequence.Seq from the Haskell
containerslibrary, which provides a similar set of features, if I understand correctly.I guess it's because implementation is not as satisfying as we expect C++ to be. However, it's may not be author's fault. The following is my suspicion:
Since rope is a persistent data structure, as a library it needs GC to recycle memory. However, GC is not natural in C++, and I noticed some long code fragments enclosed by
#ifndef __GCto implement a refcount solution, which I guess make it with a large constant and lack of optimization.I am not familiar with FP languages, but I have an impression that FP compilers do heavy & fancy optimizations on data structures to improve its performance, especially on simple structures like maintaining a sequence. BTW, it may also be a way to show the FP's advantage of maintaining a persistent data structure, so it's very likely they do benchmark and focus on these structures.
So, it's quite possible that Haskell over-perform GCC on such task, especially it's a class, by Jonathan Wakely, "nobody uses or cares about".
You can report it on their bugzilla (see this report on pbds, for example), but it would take years to fix and might even end up in Jonathan Wakely or smb else on libstdc++ team suggesting to deprecate these structures as they have little industrial use.
I think loujunjie was the one to provide a fix there, might be you would be interested in this one?
Well, if they decide to delete
rope, it'd be better if they never know the bug since I want to use it (lolI will try to submit the bug to bugzilla. Thank you!
Implement your own rope! And also make sure to make a blog about it ;)
I've submitted a report to bugzilla.
Hope to see the bug fixed in ~10 years I guess, since the last change made to the line is 17 years ago.
Yeah, just as I said, Jonathan Wakely immediately suggested to remove the class :)
You are definitely a prophet! LMAO
NEVER USE SUCH FUNCTION IN THE FUTURE— never use rope in the future, use treap.Auto comment: topic has been updated by -14 (previous revision, new revision, compare).
"NEVER USE SUCH FUNCTION IN THE FUTURE"
We need a rope after a bad round though
I can't debug my own code but this Chinese debuged C++
Sometimes you can't debug your own code because C++ itself has bugs,so you maybe need to debug C++ first before debug your own code just like this Chinese :)
That's clear, but only Chinese people can debug C++