A List of Useful Equations in Competitive Programming
source link: http://codeforces.com/blog/entry/101232
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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 .
11 hours ago, # |
195 cool equations that makes life easier. How many of them is LGM tier though?
11 hours ago, # |
Petetion to open up a brand new publication named 'Jalalkoli'.
10 hours ago, # |
too little
10 hours ago, # |
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 . 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. is not bounded from above. Let's say , then which is unbounded. Unbounded sequence cannot be periodic.
-
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.
-
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.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK