sslotin's blog

Another C++ algorithms implementations library
By sslotin, history, 7 years ago, In English

This is my repo. There are many like it, but this one is mine. My repo is my best friend. It is my life. I must master it as I must master my life. Without me, my repo is useless. Without my repo, I am useless. I must maintain my repo true. I must commit faster than my collaborator who is trying to open issue. I must assign issue to him before he assigns issue to me. I will...

I will keep my repo clean and ready, even as I am clean and ready. We will become part of each other. We will...

Before Codeforces, I swear this creed. My repo and myself are the defenders of good solutions. We are the masters of our problemset. We are the saviors of my rating. So be it, until there is no WA, but AC. Amen.

— Maintainer's Creed

Hi. I am sharing my algorithms repository to the community and calling you to test / enrich it. It is designed to be minimalistic and copy-pastable. I use it during live contests. Most of the code is not designed to be standalone — you need to copy and tweak it a bit.

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

Comments Comments (14)
| Write comment?
»
7 years ago, # |
  Vote: I like it +40 Vote: I do not like it

https://github.com/sslotin/algo/blob/master/segtree_dynamic.cpp

Good luck with Memory Limits.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Apart from throwing off lb and rb (and rewriting all functions with 2 more params and a bit more lines to recalculate them) and using int vector instead of pointers (which will be the same on 32-bit CF servers), how would you optimize it?

    You need to sacrifice a lot for memory. I only really struggled with tight ML when solving 2d gcd problem from some past ioi (memory optimization of which was the main point), other problemsetters are not sadistic enough in my experience.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +9 Vote: I do not like it

      Your get_sum creates 4 logX nodes in worst case, while should not do that at all. add creates 2 times more nodes, than it may. With lb, rb and dynamic memory allocation, it's near 7x overhead for algo, that already have O(NlogN) space complexity. It's easy to make your code use 280mb memory (which is more than the usual ML on CF) with only 200K queries: https://www.ideone.com/idLyz6. And that's O(N logN) algo, which is usually may be used with much more queries.

      In my opinion, this is not a good idea to write a library code in such a non-optimal form.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Fair point. I guess I should add memory and performance-optimized versions of it. And maybe also some other data structures where I decided to use 2x more memory/time over writing 2x more code.

        → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does treap work without saving the priority of eacb node?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You can prove by induction that for each subtree (nodes from l to r), each node of it has equal probability of being the root on this segment (try it, really), so this treap is equivalent to treap with priorities. This trick is used for persistent treaps, where, using copies, you can construct a test case where a ton of nodes will eventually be with the same priority. Generating random numbers is way too long, I know. I should split it into persistent treap and usual one (**upd**: done).

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    The treap has random priority. Since one needs priority only in merge operation it's is convenient to generate some random value while merging (line 14). This means that every time you split and merge the treap changes its 'form'. The form itself is irrelevant as logarithmic depth invariant is the only thing we use random priorities for in most cases. It is also a time-memory trade off.

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

For dsu implementation: you don't need to store the size of tree in another array, just for every root save size in the parent array as a negative number.

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

    Wow, that's a cool trick. Not going to use it for clarity of code, but thanks.

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

...alcotree?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is centroid?

→ Reply