fractal's blog

What is the Morbius inversion?
By fractal, history, 2 years ago, In English

Can someone make tutorial on Morbius inversion?

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

Comments Comments (57)
| Write comment?
»
2 years ago, # |
  Vote: I like it +158 Vote: I do not like it

Its morbin time

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +67 Vote: I do not like it

Morbin

Article #1

Article #2

→ Reply
»
2 years ago, # |
  Vote: I like it -64 Vote: I do not like it

Stop learning useless algorithms, go and solve some problems, learn how to use binary search.

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

    Stop learning useless algorithms, go and get some bitches.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -17 Vote: I do not like it

      Stop writing useless comments, literal bitchless behaviour

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
        ← Rev. 2   Vote: I like it -105 Vote: I do not like it

        When Um_nik says the sentence, nobody gives downvote to him. But now when I says the same sentence, nobody gives upvote to me. That all because I have a low rating. People send message all base on rating, but where is our own mind?

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it +38 Vote: I do not like it

          The difference is in the context. Um_nik gave the advice for someone who wants to improve rating. Author of the blog on the other hand didn't mention the purpose of his genuine interest in the topic. Moreover, Um_nik's advice was about complex algorithms and aimed the low rated audience, surely not high CM or low Masters.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
              Vote: I like it -35 Vote: I do not like it

            Um_nik gave the advice, why can't I do that? Learning useless algorithm have not use in contests, so I just give the suggestion to remind him. As we know, we should learn for those useful suggestions, why so cares about the rating of the audience?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              ← Rev. 2   Vote: I like it +5 Vote: I do not like it

              Yeah let's take the advice for the newbie who says "omg sir i learnt FFT and LiChao Tree, why am i still newbie???" and apply this advice to a CM who wrote a troll post. You are either an incredible r/wooosh moment, or a troll (likely a troll).

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

              You can give advice. What you shouldn't do, however, is tell someone who is just curious about learning something to "Stop" which is a command more than an advice. You could have worded your comment to indicate that it is an advice if the blog author is focusing on improving rating. Also, how likely is it that a Candidate Master with +1000 solved problems does not know about binary search, and does not know how complex the things one needs to learn to improve rating? This is why you got downvoted. Not because you are not Um_nik.

              → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 3   Vote: I like it -10 Vote: I do not like it

          Why should copying what other people say get you upvotes? Perhaps the supposed ratism is because higher rated users can make original comments.

          Also, I don't like Um_nik's take in general, many would rather know cool algorithms than only being very good at stupid binary search puzzles.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 2   Vote: I like it -42 Vote: I do not like it

            When we find out something good, we should learn form it. So why can't I use Um_nik's sentence? Giving the suggestions are just because the kindness to remind a stranger, why must for upvotes?

            Also, I agree with Um_nik's mind. Use some cool algorithms will just make you seem a smart man. However, it has not any use in our contests and learning.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it -21 Vote: I do not like it

              If somebody has a higher rank than you then you are in no positon to teach that person how to learn because this person probably knows more about learning. I agree in fact that thinking is more important than knowledge but you must also notice that higher ranks need some more advanced knowledge than binary search.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 years ago, # ^ |
                ← Rev. 3   Vote: I like it -29 Vote: I do not like it

                How can you know that somebody have a higher rating than me? You should notice that I just take part in one contest, maybe I have the ability to reach Master?

                And all the people has its own ability good at. Maybe I am good at some way that he isn't good. So I don't agree that I have no position to teach him.

                And I also agree we need a higher knowledge that binary search, but it just a analogy right? I can't list all the algorithm we need so I can just write one of them.

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

                  How can you know that somebody have a higher rating than me? You should notice that I just take part in one contest, maybe I have the ability to reach Master?

                  um... because you only solved problem A in Div.4 with 1 wa and 1h 25m?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -24 Vote: I do not like it

                  emmm, better than you is ok.

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

                  I agree that I'm not a good coder but still...

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -10 Vote: I do not like it

                  Wow, solve four problems in div4 in almost an hour! WHAT a strong man you are!

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

                  I said I'm not a good coder. Also, I just did that to prove you're no better than me. Anyway, you're just a troll so I'm not talking about this anymore.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  WOW, find out that you are not better than me so that I am just a troll? What a good logic you have. I think that I probably know that why you are so weak.

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

                  just shut up man

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -13 Vote: I do not like it

                  Did I do anything wrong so that you want me to shut up? I have not do any things wrong. Instead, You ask me to shut up means that you feel ashamed of yourself because of my right behaviour, So that you can only say shut up to cover up your anger.

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

                  I think you should cover up your identity because for sure no one would like to be amidst someone as obnoxious as you are

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                  ← Rev. 3   Vote: I like it -21 Vote: I do not like it

                  Hey guy, why so angry? I think you should knows that your anger has no use at all. Whatever you slander，abuse，defame insult，humiliate me, the truth will not change. Admit your mistakes is not as difficult as you think. We should learn from those who have good virtue. In my home town, Even a three-year-old baby can correct his error, why can't you? So, stop envy other who have noble character, change yourself right now. And I believe that you can understand my meaning one day.

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

                  can yall just shut the fuck up

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 years ago, # ^ |
                    Vote: I like it -17 Vote: I do not like it

                  What does it have to do with you, the man full of dirty words? Or you are just another account of the man in front?

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

                  nah, im Morbius. And once again... shut the fuck up.

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

          nobody gave you an upvote, because your comment is off-topic and rude. Morbius inversion is not a thing, and author of blog was just memeing about film "Morbius". You, without even looking up the stuff, decided to post an unfunny comment that has no meaning in the context of a blog, and then whined about getting (rightfully) downvoted.

          → Reply
          • »
            »
            »
            »
            »
            »
            2 years ago, # ^ |
            ← Rev. 3   Vote: I like it -26 Vote: I do not like it

            It takes about 0.1 calorie when an adult male sending a message in codeforces. There are about 100,000 users in codeforces. If everyone in codeforces sends one less message per day, we can save 3,650,000 calorie energy per year. And one person needs about 2,000 calorie per day. So if everyone in codeforces sends one less message per day, we can save 1,000 people who are in hungry per year. Do you care about this? No, you don't care. You just care youself.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
                Vote: I like it -18 Vote: I do not like it

              yeah, while i sent 3 comments in last month, you sent 26, who cares about hungry people less, idiot?

              → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          It is true that learning many useless (for CF) algorithms is not very helpful for rating, but learning these algorithms is no problem at all. You got downvotes just for comments, not your rating.

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

            But I just give an advice to remind him do not indulge in learning useless algorithm. I don't know what is the reason I get so much downvotes except I my rating.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 years ago, # ^ |
              ← Rev. 3   Vote: I like it 0 Vote: I do not like it

              The author of this blog just wanted to know about this algorithm, not for his rating. That's why he wrote this blog in Codeforces. You cannot force him to learn binary search instead of Möbius inversion. Even if you were a red coder, you'd get downvotes because of your comment.

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

    speedrunning negative contribution

    → Reply
»
2 years ago, # |
  Vote: I like it +149 Vote: I do not like it

Morbius inversion is undoubtedly one of the algorithms of all time

→ Reply
»
2 years ago, # |
  Vote: I like it +82 Vote: I do not like it

You simply morb by yelling "ambatumorb", no need for a tutorial

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

I can give a small glimpse of what's the usage/overview:

A lot moebius inversion relies on the equality $$$\sum_{d\mid n} \mu(d) = [n = 1] = \begin{cases} 1 &\text{if}\ n = 1 \\ 0 &\text{otherwise} \end{cases}$$$, where $$$\mu(d)$$$ is the moebius function, which can be precomputed for $$$d \in [1, n]$$$ in $$$O(n)$$$ time using linear sieve. Often using this identity, you can expand a boolean expression/counting problem into expressions involving divisors, and exchanging summation signs will reduce time complexity. For example (classical example), let's count the number of coprime pairs $$$|{(a, b) \in [1, n]^2 : \gcd(a, b) = 1}|$$$:

$$$\begin{align*} \sum_{i=1}^n \sum_{j=1}^n [\gcd(i, j) = 1] &= \sum_{i=1}^n \sum_{j=1}^n \sum_{d\mid\gcd(i, j)} \mu(d) \\ &= \sum_{i=1}^n \sum_{j=1}^n \sum_{d\mid i, d\mid j} \mu(d) \\ &= \sum_{d=1}^n \mu(d) \sum_{i=1,d\mid i}^n \sum_{j=1,d\mid j}^n 1 \\ &= \sum_{d=1}^n \mu(d) \lfloor\frac{n}{d}\rfloor^2 \end{align*}$$$

Hope that each line makes sense and follow, or ask me if you don't :)

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

    Such kind of problems can be solved with the concept of Euler totient function, hence I find very less people using or even knowing mobius inversion.

    → Reply
»
2 years ago, # |
  Vote: I like it +71 Vote: I do not like it

I would also appreciate some info on morbius sweep line algorithm

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

    True, it would be also cool if it contains analysis of it's morbing time complexity.

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

    Anton we love you!!!!

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

I can reccomend this instructional tutorial video essay documentary: https://www.imdb.com/title/tt5108870/

→ Reply
»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

You can't. Morbius is a godly invention that can't be replicated by us mortals.

→ Reply
»
2 years ago, # |
  Vote: I like it -13 Vote: I do not like it

It's a useless Algo, Go Learn DFS or Binary Search

→ Reply
»
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

There are some online tutorials about mobius inversion technique, and you can find many of them using your favorite search engine. But I would suggest going one step further, and reading some other text in number theory or combinatorics as well, because mobius is just a clean way of applying inclusion/exclusion principle.

To do this, I really recommend the book "Introduction to the Theory of Numbers" by "Harold N. Shapiro"

It's a good book overall, and the exercises can surely help you improve your skills, but to really get the intuition behind this trick, I suggest you also read the amazing "GeneratingFunctionology" by "Herbert S. Wilf", especially the second chapter and its exercises. I should also mention that to get the most of this book, you should know a bit a calculus (at least taking derivatives)

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

    Read the title again :p

    Spoiler
    → Reply