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).
About the List
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.
The Equation List
Link: blog.shahjalalshohag.com/equation-list/
Outro
A good life is just a series of good days. So make sure to have a good day, friend 
.
195 cool equations that makes life easier. How many of them is LGM tier though?
Petetion to open up a brand new publication named 'Jalalkoli'.
too little
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.
Really thanks for finding those inconsistencies, I will fix them ASAP.
Okay, I just took a look at the things that you have mentioned and in general went through all the comments that people made and I can see that people also made a similar post to troll this post.
I have fixed the issues that I found reasonable and tbh I liked your comment as at least you pointed out some mistakes and I am also a human who can make mistakes.
And in general, here is the process that I had to put behind this post: I used to learn lots of new things, I just loved learning new stuff. It's true that I am not that good at problem-solving but I love to learn. So when I learned new stuff, I used to collect the things that I thought is important in one place. So after 4 years, I posted the ultimate topic list blog and I wasn't able to post the equation list before that I have collected throughout my journey because all the equations were just screenshots or written in a doc file. So last month I thought of posting the equation list but the problem is converting all these equations to Latex. So what I did was: I have removed all the unnecessary stuff (like another 100 equations) and collected the useful equations (in my opinion) in one place and tried to categorize everything like Combi, NT, etc. Then found 7 people who agreed to convert the equations to Latex as it would help the community. Everything took some days. Then I found out that to support the Latex equations in markdown I have to manually fix some errors, or use smth called Pandoc which is not 100% accurate so I didn't use it. I also tried to contact adamant and -is-this-fft- on converting Latex files to Markdowns, but they also suggested fixing the errors manually (while using raw Latex (containing packages) in Markdown). I did that, took me a day because the file is 500 lines long. Then I posted it to my personal blog and pasted it here in this Codeforces blog.
So if I did all this just for contribution, then I think I must be the most foolish person ever. It made me sad tbh. Contribution is just a byproduct.
Also, this is a 'collection' not a 'tutorial', and albeit not for beginners which also I have mentioned in the post.
I did some mistakes like writing "all equations" instead of "some equations", had a few bugs in some lines of the 500 line Markdown file, had unnoticed 3-4 repeated equations among almost 200 equations. But that doesn't mean that this post is a failure or 'really bad'.
I will be more than happy if some random guy finds this helpful and I am pretty sure that someone will.
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.
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.
Hey Ashneer, I dare you to comment with your real I'd.
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 .
You should not be using that list as a roadmap, it's just there for referencing. Use a book or problemset like CSES instead.
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.
You counted 2028289129 equations ? xD
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.
So.. does it mean you've actually used all of these formulas on a problem before?
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.
If you haven't use some of the formulas, then why would you think they're "important" for CP and deserve to be listed?
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.
Thanks for your feedback. Now I know the problem. I have changed it to "collection of some useful equations in Competitive Programming".
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 .
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 applications
Try to put an explanation under every equation and link to some problems where they are applied
A mere publicity stunt.
The only three sums you need in low div2:
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.
You forgot this one
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.
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!
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 :/
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.
That hurts
I unterstood the humour!
But for info: Something like is mentioned. Check 71.
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?
Funny that you mentioned that one equation, because just recently i came across Problem B2 which uses that identity
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.
I am quite sure I used this exact identity more than once in my life
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!
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.
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
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?
The most Usefull looking USELESS Blog everr...
at least monogon sir accepts that he wants contrib
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?
Go to his website : https://shahjalalshohag.com/ then scroll down and then you will see your answer in his Achievements :D
Next up: Ultimate list of numbers 1-1000 used in competitive programming
In random order and with repetitions I assume.
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$$$
420 and 69 (They are used a lot in sample test cases and important for beginners to understand the underlying principles behind it. )
happy new year !!!
Here is one more: 22*8 + 2*28 + 2+2-8 = 228
One more useful equation : (6*9)+6+9=69
(5*9)+5+9=59
Kummer's Theorem is my favorite.
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.
Thanks for these equations.
very much helpful,thanks