By radoslav11, history, 4 years ago,

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

 » 4 years ago, # |   +8 For LiChao_parabolic.cpp, can two parabolas have more than one intersection?
•  » » 4 years ago, # ^ |   +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.
 » 4 years ago, # |   +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
•  » » 4 years ago, # ^ |   0 Link.
•  » » » 4 years ago, # ^ |   +9 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).
 » 4 years ago, # |   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.
•  » » 4 years ago, # ^ |   0 It's for adding an arithmetic progression to a subarray update and sum of subarray query. By adding arithmetic progression update I mean adding A to the first element of the subarray A + B to the second, A + 2 * B to the third and so on.
•  » » » 4 years ago, # ^ |   0 Here is practice problem (problem from IZHO 2013): https://www.e-olymp.com/en/problems/7482
•  » » » 4 years ago, # ^ |   +8 Another practice problem: Euclid from RMI 2015
•  » » » » 4 years ago, # ^ |   +8 Hi, sorry for necroposting, does RMI have some online judge where I can submit this problem?
•  » » » » » 4 years ago, # ^ |   +3 Yes and no. There is no RMI OJ but all the problems from RMI can be found on infoarena.ro.Here is the link for Euclid: euclid.
 » 4 years ago, # |   +8 Not as cool as the blog about Nearest Neighbour.
 » 4 years ago, # |   +8 Where is your implementation for link cut?
 » 4 years ago, # |   +26 Here is a bug: In file: LinkIn 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;
•  » » 4 years ago, # ^ |   0 thanks
 » 4 years ago, # |   +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)
•  » » 4 years ago, # ^ |   -10 Can you elaborate what you mean by Tree Decomposition? Centroid decomposition of tree?
•  » » » 4 years ago, # ^ |   0 No. This is.
•  » » » » 4 years ago, # ^ | ← 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.
•  » » » » » 4 years ago, # ^ |   0 How about 668F? (VK Cup 2016 Round 2)
•  » » » » » » 4 years ago, # ^ |   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.