Блог пользователя radoslav11

Автор radoslav11, история, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +213
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Not as cool as the blog about Nearest Neighbour.

»
7 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Where is your implementation for link cut?

»
7 лет назад, # |
  Проголосовать: нравится +26 Проголосовать: не нравится

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;

»
7 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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)
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -10 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            7 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.