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.
For LiChao_parabolic.cpp, can two parabolas have more than one intersection?
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.
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
Link.
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).
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.
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.
Here is practice problem (problem from IZHO 2013): https://www.e-olymp.com/en/problems/7482
Another practice problem: Euclid from RMI 2015
Link: http://rmi.lbi.ro/rmi_2015/_dwl/euclid.pdf
Hi, sorry for necroposting, does RMI have some online judge where I can submit this problem?
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.
Not as cool as the blog about Nearest Neighbour.
Where is your implementation for link cut?
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;
thanks
It looks really helpful to thousands of coders.
New Algorithm Suggestion:
Can you elaborate what you mean by
Tree Decomposition? Centroid decomposition of tree?No. This is.
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.
How about 668F? (VK Cup 2016 Round 2)
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.