YouKn0wWho's blog

A List of Useful Equations in Competitive Programming
By YouKn0wWho, 3 years ago, In English

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

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

Comments Comments (54)
| Write comment?
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

195 cool equations that makes life easier. How many of them is LGM tier though?

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

Petetion to open up a brand new publication named 'Jalalkoli'.

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

too little

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

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.

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

    Really thanks for finding those inconsistencies, I will fix them ASAP.

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

    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 don't think the equations are that bad that you have made it sound like in your comment. But it's true that I have made some mistakes. There are 3-4 equations that were stated multiple times (of course I didn't notice that) and the rest of the points were about having similar (but not exact) equations. Like "(23) is a weird special case of (15)", so I have stated both cases in different lines and I don't see why it is a problem. Maybe it would have been better to write them in one item but that doesn't make the whole post bad. All the equations are not super helpful, and that's pretty normal.
    • "(70) copied from somewhere without even fixing LaTeX?", so is it bad to have a mistype in a 500 line markdown file? I don't get it. It is not like that I have copied the Latex, everything has been converted to Latex from a doc file by some people.

    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.

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

      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.

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

        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.

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

    Hey Ashneer, I dare you to comment with your real I'd.

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

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 .

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

    You should not be using that list as a roadmap, it's just there for referencing. Use a book or problemset like CSES instead.

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

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.

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

    You counted 2028289129 equations ? xD

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

    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.

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

      So.. does it mean you've actually used all of these formulas on a problem before?

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

        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.

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

          If you haven't use some of the formulas, then why would you think they're "important" for CP and deserve to be listed?

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

      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.

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

        Thanks for your feedback. Now I know the problem. I have changed it to "collection of some useful equations in Competitive Programming".

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

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 .

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

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

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

A mere publicity stunt.

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

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.

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

You forgot this one

$$$\displaystyle \sum_{i = 0}^{32} 210000 \cdot \frac{50}{2^i}$$$
→ Reply
»
3 years ago, # |
  Vote: I like it +95 Vote: I do not like it

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.

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

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!

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

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

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

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.

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

    That hurts

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

    I unterstood the humour!

    But for info: Something like is mentioned. Check 71.

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

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?

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

    Funny that you mentioned that one equation, because just recently i came across Problem B2 which uses that identity

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

    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.

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

    I am quite sure I used this exact identity more than once in my life

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

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!

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

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.

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

    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

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

      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?

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

The most Usefull looking USELESS Blog everr...

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

at least monogon sir accepts that he wants contrib

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

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?

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

Next up: Ultimate list of numbers 1-1000 used in competitive programming

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

    In random order and with repetitions I assume.

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

      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$$$

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

        420 and 69 (They are used a lot in sample test cases and important for beginners to understand the underlying principles behind it. )

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

happy new year !!!

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

Here is one more: 22*8 + 2*28 + 2+2-8 = 228

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

One more useful equation : (6*9)+6+9=69

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

Kummer's Theorem is my favorite.

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

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.

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

Thanks for these equations.

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

very much helpful,thanks

→ Reply