### YouKn0wWho's blog

By YouKn0wWho, 8 months ago,

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 .

• +1334

 » 8 months ago, # |   +41 To be honest, I always skip these blogs. But I couldn't do it without upvoting this time..
•  » » 8 months ago, # ^ |   -64 That's the reason why you're pupil.
•  » » » 8 months ago, # ^ |   +8 That's the reason why you're blue.
•  » » » » 8 months ago, # ^ |   -38 Sure, non red.
•  » » » » 7 months ago, # ^ |   +2 That's the reason why you're yellow.
•  » » » » » 7 months ago, # ^ |   0 That's the reason why you're yellow.
•  » » » » » » 7 months ago, # ^ |   +13
•  » » » 7 months ago, # ^ |   0 That's the reason you are studying in a lawda-lassan college
 » 8 months ago, # |   +222 almost all the important templates that you will need in CP (saying almost just for courtesy). 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!
 » 8 months ago, # | ← Rev. 2 →   +9 This is beautiful. Thank you!Are you missing a dynamic 1D segment tree?
•  » » 8 months ago, # ^ |   +39 Dynamic 2D segtree contains dynamic 1D segtree.
 » 8 months ago, # | ← Rev. 2 →   0 very helpful for me,thank you
 » 8 months ago, # |   0 Thank you for sharing with us
 » 8 months ago, # |   0 Thanks a lot, brother. This repo means a lot to me :)
 » 8 months ago, # | ← Rev. 2 →   +64 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).
•  » » 8 months ago, # ^ | ← Rev. 3 →   +33 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.
•  » » 8 months ago, # ^ |   +203 (triggered) Spoiler
•  » » » 8 months ago, # ^ |   0 koosaga ORZZZZZZZZZZZ
•  » » » 8 months ago, # ^ |   0 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.
•  » » » » 8 months ago, # ^ |   +16 Maybe also some fast general matchings. But I was satisfied because MCMF was polynomial.
•  » » » » » 8 months ago, # ^ |   +11 Except it is not polynomial: https://ideone.com/8juY9Y And it doesn't even support negative cycles...
•  » » » » » » 8 months ago, # ^ |   0 :facepalm:
•  » » » 8 months ago, # ^ |   +84 That's what I hate love to see from ko_osaga!
•  » » » » 8 months ago, # ^ |   +62 See ya on GP soon
•  » » » » » 8 months ago, # ^ |   +11 fckwell 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.
•  » » » 8 months ago, # ^ |   +78 Actually, I added the 'almost' part just because I am not ko_osaga XD.
•  » » » 8 months ago, # ^ |   +29 Even we ourselves don't have 4-edge connectivity in our library :D
 » 8 months ago, # |   +11 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!
•  » » 8 months ago, # ^ |   +18 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.
 » 8 months ago, # |   0 Thanks a lot YouKn0wWho bhai! That's amazing ❤️
 » 8 months ago, # |   +15 I don't want to be a dick while writing this but, why have spaces between file names?
 » 8 months ago, # |   +1 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.
 » 8 months ago, # |   +79 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.cpp you assume max of two ints. If I want to use Link Cut Tree.cpp to find the maximum weight edge on some path, I need to read 200 lines of code and find all places where I need to put max instead 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.
 » 8 months ago, # |   +35 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!
•  » » 8 months ago, # ^ |   0 ❤️ Hii!
•  » » » 8 months ago, # ^ |   +2 Ok, why did I always assume that it's impossible to use emoji? :) We should use them more often!
•  » » » » 8 months ago, # ^ |   +9 We should use them more often!I hope no newbie reads this.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +5 Embed
 » 8 months ago, # |   0 It should be added to the codeforces navbar. I just said it.
 » 8 months ago, # |   0 After all it's in C++.
 » 8 months ago, # |   0 What is the directory for "Slope trick" though? or, is it named differently?
 » 8 months ago, # |   0 Thanks for sharing, YouKn0wWho. There are so many things in there that I always thought were impossible to do!
 » 8 months ago, # |   0 Thanks for sharing.
 » 8 months ago, # |   0 where is rerooting?
•  » » 8 months ago, # ^ |   +11 I normally don't need a template for rerooting.
•  » » 8 months ago, # ^ |   +11 Can you please briefly explain what you mean by rerooting?
•  » » » 8 months ago, # ^ |   +16 its about dp on treessuppose we want to calculate dp for each vertex of tree if it this vertex is root of whole treeif 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)$
•  » » » » 8 months ago, # ^ |   0 It can be solved in O(n) and I have a template for this:https://codeforces.com/contest/1498/submission/126109184
•  » » » » » 8 months ago, # ^ |   0 sure, but O(n) requires description of f (in your template), O(nlogn) don't.
•  » » » » » » 8 months ago, # ^ |   0 I don't get your point, of course it requires a description of f, it's a template.
•  » » » » » » » 8 months ago, # ^ |   0 There is no merge function in nlogn method
•  » » » » » » » » 8 months ago, # ^ |   0 Your loss, if you designed it around three operations (edge extend, merge, vertex extend) you'd get O(n)
•  » » » » » » » » » 8 months ago, # ^ |   +13 By "sure" I meant "i know it" :)
•  » » » » » » » » » 8 months ago, # ^ |   +11 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.
•  » » » » 8 months ago, # ^ |   +11 That is not the full potential of rerooting. The reroot implementation I usually use calculates two things: rootDP and edgeDP. rootDP[node]= DP[node] assuming node is the root edgeDP[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 edgeDP is the thing that is really useful. A great example is problem C in facebook hackercup round 1. That problem is almost trivial using edgeDP. You can download my Python solution here.
 » 8 months ago, # |   +18 I feel very weak after reading some of the codes.
 » 8 months ago, # |   0 Amazing! Can't imagine the effort put into this...
 » 8 months ago, # |   0 Whoa, this is awesome.
 » 8 months ago, # |   0 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).
 » 7 months ago, # |   +150 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.
 » 7 months ago, # |   0 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?
 » 5 weeks ago, # |   0 Nice, thanks!Do you have any repos for design patterns (eg — momento, proxy, observer)?