Hey everyone, I am sharing my personal code library where I compiled almost all the important templates that you will need in CP (saying almost just for courtesy). Most of the codes are originally written by me and some of them are collected from others but modified in a cleaner way. Link: https://github.com/ShahjalalShohag/code-library
It took me around 4 years to complete the list. Maybe each line is just a line to you but to me it tells a story of the excitements I had while learning those stuffs, the sleepless but fun nights I had to seek knowledge.
Why am I sharing this library?
- Just so that your learning path becomes a bit smoother.
- Knowledge hidden inside my head or codes in a private code-library will be useless when I am dead, so it's better to share those among people before I die.
Also, you can make me happy(as in to pay me) just by upvoting this blog and giving a star to the repository.
I believe that my coding style is pretty clean and readable, and furthermore, a few problem links are attached to most of the codes so that you can practice those problems. Best wishes, my friend 
.
To be honest, I always skip these blogs. But I couldn't do it without upvoting this time..
That's the reason why you're pupil.
That's the reason why you're blue.
Sure, non red.
That's the reason why you're yellow.
That's the reason why you're yellow.
Of course, I immediately disliked this sentence, thought about a bunch of obscure algorithms nobody cares. But I opened your repo and was pleasantly surprised. Good work!
This is beautiful. Thank you!
Are you missing a dynamic 1D segment tree?
Dynamic 2D segtree contains dynamic 1D segtree.
Incredible library. After a quick scan I still can't find anything I know that could be added. What I think you can add is whether a data structure / algorithm assumes 0-indexing or 1-indexing, or if you work with ranges then do you represent them with right end inclusive or exclusive (for example, segment tree) — to generalize, either above a struct or above a function, I think it would be nice if you can detail how it takes input and provides output in a short comment.
And just to make sure — do you permit other people to use your library? with credit of course.
EDIT: I can't seem to find Alien's trick. Also I found even my little contribution to the library (queue undo trick), so I feel very honored, however it does require a small fix; In my blogpost I explain that we must maintain the bottom pointer of the stack so that we never pass it — so at the current state of the code, it may run in $$$O(n \sqrt n)$$$ operations. Just a few lines of code to add (whenever you feel like it).
I almost always use 1-indexing and inclusive ranges unless mentioned otherwise. That means wherever I have used 0-indexing or exclusive ranges I have commented out explicitly.
And, of course, people can use my library(that's why this post exists). I have added the MIT license to clear out the confusion.
Replying to your EDIT section: Aliens trick is just binary search, that's why I normally don't need an explicit template for it. It is included in my topic list(ft tutorial links) which will get published soon. And sorry for not adding the required lines in the "queue undo trick" code. Will be updated soon.
(triggered)
koosaga ORZZZZZZZZZZZ
I only know persistent BST from that list, but I guess you're right — there is something I know that's not in the library.
I guess we can add on that some faster maxflow algorithms since the fastest there is $$$O(EV^2)$$$ dinic.
Maybe also some fast general matchings. But I was satisfied because MCMF was polynomial.
Except it is not polynomial: https://ideone.com/8juY9Y And it doesn't even support negative cycles...
:facepalm:
That's what I
hatelove to see from ko_osaga!See ya on GP soon
fck
well actually two Korean GP from last season (if I'm not mistaken you were involved in both) 1 2 In the second one we participated during ptz camp so no copypasting, and we knew where to copy-paste L from, we just didn't know how to implement it ourselves. So in OpenCup rules we would won by a problem from USA1 in ICPC-eligible line-up, which seems insane.
Actually, I added the 'almost' part just because I am not ko_osaga XD.
Even we ourselves don't have 4-edge connectivity in our library :D
Thanks a lot for the great library, I really liked it since it's one of the most comprehensive ones I've seen so far (with some documentation to make them usable as well).
Some minor feedback: if you feel like it, you could add some links/brief description to some of the more obscure techniques that are included in the repo (for instance, the Venice technique), however, I do understand that getting it to the current stage must have been a pretty huge task already. Nevertheless, since most stuff is searchable, it's not as necessary, and still a great resource!
Good news, I have been collecting the topic names, tutorial links, problems links etc for more than a few months now. So you can expect the list to be completed soon, hopefully within this week or sooner.
I don't want to be a dick while writing this but, why have spaces between file names?
This library is amazing! It would be nice to create something like this for documentation and easily finding templates. It would probably be a lot of work though.
As a library creator myself I'm deeply impressed by the number of items.
One thing that is lacking is templates on every algorithm/data structure that can be generalized, and for many algorithms/DSs presented, you are assuming what they will be used for. For example, in
Segment Tree.cppyou assume max of two ints. If I want to useLink Cut Tree.cppto find the maximum weight edge on some path, I need to read 200 lines of code and find all places where I need to putmaxinstead of something else, and I'll probably make a mistake anyway.In conclusion this is great educational material, but in some places it's hard to use the codes as snippets the way they are now.
Honestly, the most amazing thing about your blog post for me is that you included an emoji into a codeforces blog post. How did you do that?? I need a tutorial!
❤️ Hii!
Ok, why did I always assume that it's impossible to use emoji? :) We should use them more often!
We should use them more often!
I hope no newbie reads this.
Embed
What is the directory for "Slope trick" though? or, is it named differently?
where is rerooting?
I normally don't need a template for rerooting.
Can you please briefly explain what you mean by rerooting?
its about dp on trees
suppose we want to calculate dp for each vertex of tree if it this vertex is root of whole tree
if we have dp of two subtrees and we can describe function of
link one subtree to other(as child), than we can solve problem in $$$O(nlogn)$$$It can be solved in O(n) and I have a template for this:
https://mirror.codeforces.com/contest/1498/submission/126109184
sure, but O(n) requires description of
f(in your template), O(nlogn) don't.I don't get your point, of course it requires a description of
f, it's a template.There is no
mergefunction in nlogn methodYour loss, if you designed it around three operations (edge extend, merge, vertex extend) you'd get O(n)
By "sure" I meant "i know it" :)
I think you are missing the point. It is a trade off between time it takes to implement the solution vs the running time.
The merge function will often times be quite tedious and complex to implement. So paying an extra log factor of runtime to skip having to implement it can absolutely be worth it.
The way I've coded my reroot template, I can freely switch between using a merge function (with runtime O(n)) or not using a merge function (with runtime O(n log n)). Most of the time I just stick to slower running (but far easier to use) O(n log n) version.
That is not the full potential of rerooting. The reroot implementation I usually use calculates two things:
rootDPandedgeDP.rootDP[node]= DP[node] assuming node is the rootedgeDP[node][i]= DP[node] assuming node's neighbour graph[node][i] is the root.When I've been using my reroot code in practice, I've found that
edgeDPis the thing that is really useful. A great example is problem C in facebook hackercup round 1. That problem is almost trivial usingedgeDP. You can download my Python solution here.I feel very weak after reading some of the codes.
Amazing! Can't imagine the effort put into this...
Whoa, this is awesome.
This is amazing! To make this more useful, you should include an example submission for each file (preferably on classical problems) so people can have some confidence that the code is correct and fast. It would be an easy way to point people to problems which hopefully will have a discussion thread on the technique. This can also make it much easier to accept contributions from others if they can immediately show that a change still ACs and results in a faster submission time.
In general it would be nice if you can adopt a consistent documentation format (up to you but I would include: author, license, brief description/complexity, source problems/submissions/editorials/articles). In particular, missing author/license details means you're probably not complying with the license of where you copied the code from (even if no one in the CP world cares about enforcing them, it is still nice to give credit where it's due).
Btw we didnt get icpc medal cause I added this half-plane intersection in our TRD. Current version works fine, but the one from 25 august or smth was incorrect in some cases. Though it passed 2018 icpc wf problem G. I understand that I am stupid myself, need to test code properly.
Hi, i couldn't find Cycle Enumeration in your library, I say this because I was solving a question involving it while visiting your post, is it not present in the library?