Блог пользователя YouKn0wWho

Автор YouKn0wWho, 3 года назад, По-английски

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.

  • Проголосовать: нравится
  • +1334
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +41 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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!

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

This is beautiful. Thank you!

Are you missing a dynamic 1D segment tree?

»
3 года назад, # |
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).

»
3 года назад, # |
  Проголосовать: нравится +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!

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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!

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

where is rerooting?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    I normally don't need a template for rerooting.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Can you please briefly explain what you mean by rerooting?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              There is no merge function in nlogn method

              • »
                »
                »
                »
                »
                »
                »
                »
                3 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +13 Проголосовать: не нравится

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  3 года назад, # ^ |
                    Проголосовать: нравится +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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

        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.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

I feel very weak after reading some of the codes.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Whoa, this is awesome.

»
3 года назад, # |
  Проголосовать: нравится 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).

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится 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?