YouKn0wWho's blog

(The Ultimate) Code Library
By YouKn0wWho, 21 month(s) ago, In English

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 blobheart.

  • Vote: I like it
  • +1334
  • Vote: I do not like it

Comments Comments (54)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +41 Vote: I do not like it

To be honest, I always skip these blogs. But I couldn't do it without upvoting this time..

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +222 Vote: I do not like it

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!

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

This is beautiful. Thank you!

Are you missing a dynamic 1D segment tree?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +39 Vote: I do not like it

    Dynamic 2D segtree contains dynamic 1D segtree.

    → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +64 Vote: I do not like it

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).

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +11 Vote: I do not like it

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!

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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.

    → Reply
»
21 month(s) ago, # |
  Vote: I like it +15 Vote: I do not like it

I don't want to be a dick while writing this but, why have spaces between file names?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +79 Vote: I do not like it

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.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +35 Vote: I do not like it

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!

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the directory for "Slope trick" though? or, is it named differently?

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

where is rerooting?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I normally don't need a template for rerooting.

    → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Can you please briefly explain what you mean by rerooting?

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      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)$$$

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It can be solved in O(n) and I have a template for this:

        https://codeforces.com/contest/1498/submission/126109184

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sure, but O(n) requires description of f (in your template), O(nlogn) don't.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't get your point, of course it requires a description of f, it's a template.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              21 month(s) ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There is no merge function in nlogn method

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                21 month(s) ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Your loss, if you designed it around three operations (edge extend, merge, vertex extend) you'd get O(n)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

                  By "sure" I meant "i know it" :)

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  21 month(s) ago, # ^ |
                    Vote: I like it +11 Vote: I do not like 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.

                  → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        That is not the full potential of rerooting. The reroot implementation I usually use calculates two things: rootDP and edgeDP.

        1. rootDP[node]= DP[node] assuming node is the root
        2. 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.

        → Reply
»
21 month(s) ago, # |
  Vote: I like it +18 Vote: I do not like it

I feel very weak after reading some of the codes.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing! Can't imagine the effort put into this...

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Whoa, this is awesome.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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).

→ Reply
»
20 months ago, # |
  Vote: I like it +150 Vote: I do not like it

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.

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
9 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Awesome Bro

→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whoever's reading this, i pray that whatever you're going through gets better and whatever you're struggling with or worrying about is going to be fine and that everyone has a fantastic day! Amen

→ Reply