radoslav11's blog

Coding library.
By radoslav11, history, 7 years ago, In English

Hello everyone!

I have been collecting (from different places) and writing codes for some time now and I decided to share them with you. Here is a link to the coding library which I have been using.

The coding library contains Online MO's algorithm, different variations of segment trees, Dynamic Convex Hull trick, variations of LiChao segment tree and many other.

Tomorrow I'll probably add my implementations of Link/Cut tree, K-D tree, some other dp optimizations and persistent treap.

I really hope that the coding library will be helpful for some of you.

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

»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For LiChao_parabolic.cpp, can two parabolas have more than one intersection?

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

    Unfortunately this implementation works only if every pair of parabolas has at most one intersection. I'm thinking on adding descriptions for all codes (what they do, required constraints and etc.) and I'll probably do it next weekend.

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

What's a LiChao segment tree? I wouldn't normally ask but this is one of the 2 posts that I could find while searching on google that mention it and I didn't really understand from the other one, so, as this post is more recent, this is the only place I could ask

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

    Link.

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

      I know its a tedious task but it would be great if you could write a proper blog on LiChao segment tree and applications of it (in English).

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

Can you please explain what "AP" means for a segment tree? I couldn't quite figure it out; it looks like a regular segment tree to me.

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

Not as cool as the blog about Nearest Neighbour.

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

Where is your implementation for link cut?

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

Here is a bug: In file: Link
In line: 65

You are declaring int ans = 0, and then taking minimum as ans = min(ans, par_mn[u][l]).

The declaration should be int ans = INT_MAX;

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

It looks really helpful to thousands of coders.

New Algorithm Suggestion:

  • Dynamic Connectivity (I've seen a problem from Russian Camp that can be solved very easily by this algorithm)
  • SA-IS (Sometimes creating Suffix Array in O(N log^2 N) is too slow and gets TLE without exception)
  • Tangent point on convex polygon (In O(log N). I've seen but I couldn't solve it at ICPC WF 2016)
  • 3D geometry algorithms, especially 3D convex hull (It was required in one round in OpenCup this year)
  • Dominator Tree (I've seen several times in programming contests. Sounds difficult but more common than 3D geometry.)
  • Tree Decomposition (I don't know if there're problems requiring this algorithm, but I saw the similar problem before)
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Can you elaborate what you mean by Tree Decomposition? Centroid decomposition of tree?

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

      No. This is.

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

        Which algorithm related to tree decompositions would you want to use in competitive programming? I wouldn't believe that any contest problem would require you to compute optimal tree decomposition in general graph and the best algorithm for it usable in competitive programming is O(poly(n)2n). I have seen three problems where knowledge about tree decompositions/clique trees/chordal graphs could be useful but prewritten algorithms would not have been useful in these cases.

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

          How about 668F? (VK Cup 2016 Round 2)

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

            I haven't seen the problem before, but it seems like this is the type of problem where prior knowledge of concepts related to tree decompositions could be useful. I don't see how any prewritten algorithm could help in this problem.

            → Reply