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

Автор fractal, история, 2 года назад, По-английски

Can someone make tutorial on Morbius inversion?

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

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

Its morbin time

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

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

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

    Stop learning useless algorithms, go and get some bitches.

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

      Stop writing useless comments, literal bitchless behaviour

      • »
        »
        »
        »
        2 года назад, # ^ |
        Rev. 2   Проголосовать: нравится -105 Проголосовать: не нравится

        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?

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

          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.

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

            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?

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

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

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

              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.

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

          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.

          • »
            »
            »
            »
            »
            »
            2 года назад, # ^ |
            Rev. 2   Проголосовать: нравится -42 Проголосовать: не нравится

            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.

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

              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.

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

                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.

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

                  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?

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

                  emmm, better than you is ok.

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

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

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

                  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.

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

                  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.

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

                  just shut up man

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

                  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.

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

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

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

                  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.

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

                  can yall just shut the fuck up

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

                  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?

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

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

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

          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.

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

            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.

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

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

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

          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.

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

            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.

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

              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.

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

    speedrunning negative contribution

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

Morbius inversion is undoubtedly one of the algorithms of all time

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

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

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

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

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

I would also appreciate some info on morbius sweep line algorithm

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

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

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

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

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

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

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

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)