### YouKn0wWho's blog

By YouKn0wWho, 2 years ago,

Hi, I am super excited to be back with another list. This time it is a collection of some useful equations in Competitive Programming.

### Motivation

Do you find it bad if you couldn’t solve a problem just because you didn’t know about a certain equation?

Do you find it difficult to take a quick look at an equation that you know exists but forgot about it while solving a problem?

Do you think that all the equations that are important in CP are just cluttered and you are too lazy to collect them in one place?

Well, then you are in the right place! I am here to solve all of the aforementioned problems. I believe you should not waste your precious time searching the internet for important equations. You should solve more problems. I am here to undertake the nasty task of collecting things.

### Payment

Everything comes with a cost. You need to do something for me. That is you need to upvote this blog. Pretty easy!

### Acknowledgement

Thanks to the following guys as they converted all the equations to Latex: Mahbubul Alam Sabuj(newb_ie), Irfan Ullah Munna (Shanto65), S.M.A Nahian (Nahian9696), Ashiqur Rahman Naeem (nayeem2021), Md. Imran Hossain(peripatetic), Jamilur Rahman(jamil314) and Mahmood (mah_mood).

I didn't add any explanations for any of the equations because it's not feasible to explain too many equations. So make sure to understand them by yourself or use google or just comment under this blog. The community will help.

The list also contains some small tricks as a bonus. As the list is long, it must have some errors. Feel free to point those out. Also, comment the missing equations that you think should be added to the list.

Enjoy!

### Audience

This list is NOT for beginners. This is for people who already came across lots of stuff in Combinatorics, Number Theory, and Math but found it hard to keep track of the equations that you already know of. This list can be used as a reference. If you are a beginner or someone who is not experienced in Combi, NT, or Math, then stay away from this.

### Outro

A good life is just a series of good days. So make sure to have a good day, friend .

• +327

| Write comment?
 » 2 years ago, # |   +6 195 cool equations that makes life easier. How many of them is LGM tier though?
 » 2 years ago, # |   +28 Petetion to open up a brand new publication named 'Jalalkoli'.
 » 2 years ago, # |   +20 too little
 » 2 years ago, # |   +457 This is a really bad post and it proves that you do this only for contribution. You didn't even try to make this systematic, you just took all the formulas you could find and that's it, the ultimate list.I haven't read all of this, so just some random things I have noticed: The first section in combinatorics is called "General", but it is mostly about binomial coefficients. Nothing wrong with that, of course, but why (29) is somewhere in between facts about binomial coefficients? The answer is because it is equivalent to (1) if you think about it. So, they should have been in the same item, and that item certainly shouldn't be the first, that's insane. (10), (12) and (16) are literally the same thing, with (11) not very far off. (17) and (18) are more or less the same, but for some reason, they use different notations (k instead of n) which make them look very different. (20) is very random. Why 3? There is no binomial theorem on the list as far as I can see, but for some reason, there is a special case with $x=3, y=1$. Then (21) gives half of the binomial theorem which, again, is weird. (23) is a weird special case of (15), I can't imagine why it deserves its own item. (26) is just some random consequences from (28) or (39). (28) actually refers to (39) by name, why (28) is before (39) and so far from it then? (30) and (32) are the same thing, and the thing between them is completely different. somewhere around here I stopped caring (70) copied from somewhere without even fixing LaTeX? Oh wow, (88) is again (1)! (140) is just wrong. $\frac{n}{\phi(n)}$ is not bounded from above. Let's say $n=\prod_{i=1}^{k} p_{i}$, then $\frac{n}{\phi(n)} = \prod_{i=1}^{k} \frac{p_i}{p_i - 1} \ge \prod_{i=1}^{k} (1 + \frac{1}{p_i}) \ge 1 + \sum_{i=1}^{k} \frac{1}{p_i}$ which is unbounded. Unbounded sequence cannot be periodic.
•  » » 2 years ago, # ^ |   +35 Really thanks for finding those inconsistencies, I will fix them ASAP.
•  » » » 2 years ago, # ^ |   +32 Maybe the problem is in the word "Ultimate". This is a list of formulas alright. But I don't think that you have made any serious work on it, like choosing more useful formulas or deciding the order. I cannot justify the presentation you gave. Retyping 200 formulas is not so hard that you would need some people to help.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +9 Agreed on the word selection part. I will be more careful in choosing the right word next time.Changed to "A List of Useful Equations in Competitive Programming". Thanks.
•  » » 2 years ago, # ^ |   +25 Hey Ashneer, I dare you to comment with your real I'd.
 » 2 years ago, # |   -8 this is request for you the ultimate topic list blog , can you please order the topics in each section in order in which a beginner should learn in that list .
•  » » 2 years ago, # ^ |   +39 You should not be using that list as a roadmap, it's just there for referencing. Use a book or problemset like CSES instead.
 » 2 years ago, # |   +217 This post is honestly pretty detrimental to anyone who is starting out on CP.Literally no one memorizes this many formulas. Instead what most people do is understand intuitively what the formulas are saying. By making a blog like this where you just present random formulas without any context, you are giving people the wrong impression that CP is about memorizing 2028289129 equations and algorithms. This kind of shit is exactly the thing that gives people a sour taste in their mouth when they think about high school math.
•  » » 2 years ago, # ^ |   -33 You counted 2028289129 equations ? xD
•  » » 2 years ago, # ^ |   +10 Hi, this post is NOT for someone who is starting out CP. This list is just a collection to take reference from just like people should NOT start from my ultimate topic list, that one is also for taking reference.And, of course, no one should memorize formulas, that's why the need for a collection list arises in the first place. I have just shared a list that I used to take references from.
•  » » » 2 years ago, # ^ |   0 So.. does it mean you've actually used all of these formulas on a problem before?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +34 Not all formulas, but yes I have used some of the equations from this list to solve actual problems.But note that, the equations were not the main part for solving those problems, but they are a little part.
•  » » » » » 2 years ago, # ^ |   -10 If you haven't use some of the formulas, then why would you think they're "important" for CP and deserve to be listed?
•  » » » 2 years ago, # ^ |   +20 Ok, I guess now it is better that you updated to blog to say that this isn't meant for beginners.Sharing your collection to let people see is totally fine and all but how do you think people will interpret " collection of all important equations in Competitive Programming "? I really cannot think of a why someone would unironically describe his collection of equations as collection of all important equations in Competitive Programming and another ultimate list. To me, it just seems like you are appealing to the users who want comprehensive lists (guess who these people are).The content is fine I guess, but the way you advertise it on this blog should be more honest or else it will give people wrong impressions.
•  » » » » 2 years ago, # ^ |   +5 Thanks for your feedback. Now I know the problem. I have changed it to "collection of some useful equations in Competitive Programming".
 » 2 years ago, # | ← Rev. 2 →   +34 I am really interested to know who this list gonna help to. Masters ? Grandmasters ? As an expert I just got demotivated seeing it in the form its presented and feel most of the things are not relevant for majority of people. And moreover masters / grandmasters wo'nt need this .
 » 2 years ago, # | ← Rev. 9 →   +38 Dude I can't even read these. I don't think it's gonna help anyone if you just randomly put different equations one after another without any explanation and their applicationsTry to put an explanation under every equation and link to some problems where they are applied
 » 2 years ago, # |   +39 A mere publicity stunt.
 » 2 years ago, # |   +231 The only three sums you need in low div2: $1 + 2 + \ldots + n = n \cdot (n + 1) / 2$ $1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \ldots + \frac{1}{n} \approx \log(n)$ $1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \frac{1}{16} + \ldots = 2$The first sum is useful for problems about counting. The other two sums are often used to estimate the time complexity of an algorithm (example: prime sieve). Note that the last sum is an infite series.
 » 2 years ago, # |   +68 You forgot this one $\displaystyle \sum_{i = 0}^{32} 210000 \cdot \frac{50}{2^i}$
 » 2 years ago, # |   +95 Is this list useful for learning mathematics or anything in general? No. Is it useful for looking up something you reduce a problem to, though? Also no.Good luck scrolling these 100-something items seeking something specific and seeing the same other things with changed variables instead.
 » 2 years ago, # |   -6 It is an excellent and resourceful blog coming from the author of the “Ultimate Topic List”!No, this blog doesn’t serve the purpose to educate any beginner level contestant or to explain the mathematical background behind each of these equations and the author stated it pretty clearly.And c’mon! It might’ve happened to all of us when we know solving a math/number theory problem is just one equation away and we’ve seen this equation somewhere but just can’t remember where! At that intense moment, groping in Google with random search words might be a very bad idea and then we badly feel the need of a “safe search space” or an “archive” where we can look that up. And the author just gifted us one of those. I know I’m not a very knowledgeable person in this matter and there may be a bunch of structural improvements the blog needs. But as an initiative, this was a very thoughtful and a much needed one and I appreciate the author for that. Keep up the good work, man!
 » 2 years ago, # |   +12 Come on, let competitive programming remain programming please. It has almost become just another math olympiad already. No way, I am going to learn these many formulas :/
 » 2 years ago, # |   +182 Good list but it doesn't contain $(a + b)(a^2 + b^2) = \frac{a^4 - b^4}{a - b}$ which is the most useful formula in all of CP so it's a terrible list and I hate it L + downvoted + ratio + you fell off.
•  » » 2 years ago, # ^ |   +11 That hurts
•  » » 2 years ago, # ^ |   0 I unterstood the humour!But for info: Something like is mentioned. Check 71.
 » 2 years ago, # |   +19 I feel like the list lacks motivation to an extent. Some of these I've used, but $k {n \choose k} = n {{n - 1} \choose {k - 1}}$ just for example, like sure, that's neat I guess, but why would I care? :P I think it might be helpful to have a problem link for these. I'm sure that would be 100x more work though, but if you can't find a problem that uses it, is it worth learning?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -18 Funny that you mentioned that one equation, because just recently i came across Problem B2 which uses that identity
•  » » 2 years ago, # ^ |   +84 IMO it's one of many formulas that you should be able to derive easily. No need to remember it.What's more fun is proving such formulas without algebra. ${n \choose k} \cdot k$ chooses $k$ out of $n$ objects, and then chooses one of $k$ as a boss. $n \cdot {n-1 \choose k-1}$ chooses one boss out of $n$ objects and then chooses the remaining $k-1$ objects.
•  » » 2 years ago, # ^ |   +8 I am quite sure I used this exact identity more than once in my life
 » 2 years ago, # |   -11 If anyone of you who scrolled to this extent and think that you will be tourist once you remember these formulas then! Oh Come on Man Math comes from inside no need to remember or google search. if you do google search for math problems then you are no more a good loyal CPer!
 » 2 years ago, # |   -33 Take a look over all the equations. Bookmark the blog. Come here again if you ever think you need to look at the article again.Please, don't try to see everything from your LGM/IGM/GM eyes. More than 99% are not RED here. Some people will be happy more than you if they ever can be an Expert or CM or maybe Master. So leave some space also for them.
•  » » 2 years ago, # ^ |   +10 Dude really ?? - No one is gonna memorize all those formulas - This blog creates a wrong impression on a lot of beginners - Even if someone had to look up for a formula , I don't think so anyone would go through all that trouble just to find a formula in this list with so many formulas . They will just google it and find the answer in seconds. - Its not just LGM/IGM/GM , i don't think it is useful for us <= Masters as well. I mean half of the formulas don't even make sense to me lol
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -17 At first, no one told you to memorize these formulas.Then, I can ensure you, for some of the formulas you need more time to write down at the search box than look up this blog. (At least for many of us)Finally, I believe maybe sometimes this blog could be partially useful for some person.If you aren't able to connect with yourself with this blog, then why aren't you skipping it? Does his top rank bother you from any side?
 » 2 years ago, # |   +12 The most Usefull looking USELESS Blog everr...
 » 2 years ago, # |   -11 at least monogon sir accepts that he wants contrib
 » 2 years ago, # |   +43 I guess this post is useful for many people, including me. But I just find it a bit weird how you ask people to "pay you by upvoting." I mean Codeforces is a community for people to share their knowledge and grow, I am sure you already got "paid" by reading other educational blogs like this here, so what's with this indecency?
•  » » 2 years ago, # ^ |   +42 Go to his website : https://shahjalalshohag.com/ then scroll down and then you will see your answer in his Achievements :D
 » 2 years ago, # |   +140 Next up: Ultimate list of numbers 1-1000 used in competitive programming
•  » » 2 years ago, # ^ |   +100 In random order and with repetitions I assume.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +62 No, This is not enough! Staying in the realm of traditional whole numbers is a waste of brain. You need to make it REALLY Ultimate!Sample part of the list: $439$ Three $2\frac{1}{2}$ четырнадцать $\bigotimes\bigotimes\bigotimes\bigotimes\bigotimes$
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +6 420 and 69 (They are used a lot in sample test cases and important for beginners to understand the underlying principles behind it. )
 » 2 years ago, # |   +8 happy new year !!!
 » 2 years ago, # |   +45 Here is one more: 22*8 + 2*28 + 2+2-8 = 228
 » 2 years ago, # |   +48 One more useful equation : (6*9)+6+9=69
•  » » 2 years ago, # ^ |   0 (5*9)+5+9=59
 » 2 years ago, # |   0 Kummer's Theorem is my favorite.
 » 2 years ago, # |   0 Thanks for creating this list. For someone without a mathematics background, I will not be able to figure out most of these under competition conditions. But when you put a list like that, it helps people like me to know roughly what people with math background need to know, and then I know what kind of thought processes I should develop to be on-par with other competitive programmers.
 » 2 years ago, # |   0 Thanks for these equations.
 » 2 years ago, # |   0 very much helpful,thanks
 » 12 months ago, # |   0 great