YouKn0wWho's blog

(The Ultimate) Code Library
By YouKn0wWho, 3 years 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 (52)
| Write comment?
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
  • »
    »
    3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years 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
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where is rerooting?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I normally don't need a template for rerooting.

    → Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Can you please briefly explain what you mean by rerooting?

    → Reply
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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.net/contest/1498/submission/126109184

        → Reply
        • »
          »
          »
          »
          »
          3 years 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
          • »
            »
            »
            »
            »
            »
            3 years 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
            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              There is no merge function in nlogn method

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                3 years 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
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

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

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 years 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
      • »
        »
        »
        »
        3 years 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
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

I feel very weak after reading some of the codes.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Whoa, this is awesome.

→ Reply
»
3 years 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
»
3 years 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
»
3 years 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