Can someone make tutorial on Morbius inversion?
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
5 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 10 | nor | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 25.11.2024 14:50:44 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
Its morbin time
man im morbin all over myself over here
Morbin
Article #1
Article #2
Amazing tutorial!!
Stop learning useless algorithms, go and solve some problems, learn how to use binary search.
Stop learning useless algorithms, go and get some bitches.
Stop writing useless comments, literal bitchless behaviour
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?
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.
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?
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).
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.
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.
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.
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.
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.
um... because you only solved problem A in Div.4 with 1 wa and 1h 25m?
emmm, better than you is ok.
I agree that I'm not a good coder but still...
Wow, solve four problems in div4 in almost an hour! WHAT a strong man you are!
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.
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.
just shut up man
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.
I think you should cover up your identity because for sure no one would like to be amidst someone as obnoxious as you are
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.
can yall just shut the fuck up
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?
nah, im Morbius. And once again... shut the fuck up.
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.
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.
yeah, while i sent 3 comments in last month, you sent 26, who cares about hungry people less, idiot?
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.
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.
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.
no its morbius inversion
I don't know what do you mean.
Look up Morbius
speedrunning negative contribution
Making jokes about others is so fun?
yes
Morbius inversion is undoubtedly one of the algorithms of all time
You simply morb by yelling "ambatumorb", no need for a tutorial
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}|$$$:
Hope that each line makes sense and follow, or ask me if you don't :)
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.
You should read https://codeforces.me/blog/entry/97623. I explain why totient function and the identity function are related in the same way as the unit function and the mobius function.
Yeah now I understood. Nice blog, thnx!!
A lot of times it cannot, that's the point.
I would also appreciate some info on morbius sweep line algorithm
True, it would be also cool if it contains analysis of it's morbing time complexity.
Anton we love you!!!!
I can reccomend this instructional tutorial video essay documentary: https://www.imdb.com/title/tt5108870/
You can't. Morbius is a godly invention that can't be replicated by us mortals.
It's a useless Algo, Go Learn DFS or Binary Search
It's a useless comment, Go get some bitches
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)
Read the title again :p
Morbius