Math 101 for Competitive Programming
Many of us are trying to do something productive in this Quarantine. This Article is one of them which is gonna help you out of “Fear of Starting Competitive Programming”.
In this Article we will discuss the essential needs of Math Knowledge for Starting Competitive Programming.
Table of Content:
- Birthday Paradox Problem
- Modular Arithmetic Properties
- Inclusion Exclusion principle and programming applications
Birthday Paradox:
Birthday Paradox actually states. How many people must be there in a room to make the probability p% that at-least two people in the room have same birthday?. Naive solution is the by finding p(different) and subtracting from 1 equaling it to p(same). After solving you will get the N. Instead of that you can simply use the formula which is actually derived from the above equation is
sqrt(2*365*log(1/(1-p)))
For more information you can visit reference
Modular Arithmetic Properties:
In competitive programming, Modular Arithmetic Properties are essential tools in solving big number problems. In the Problem statement when they ask to print solution in mod(107+9). It not as sample as it seems. You might get large number before applying mod to it. To simplify, You need have idea on Modular Arithmetic Properties
- ( a + b ) mod p
When they ask to add sum of two large numbers which get overflow after adding.
Use this Formula
(a+b) mod p = ((a mod p) + (b mod p))mod p
2. ( a*b) mod p
Same case here but when they said to multiply and which result might end up overflow. Use this Formula
(a*b) mod p = ((a mod p)*(b mod p))mod p
For more Information you can visit. Modular properties reference.
Inclusion Exclusion principle and programming applications:
The principle of inclusion-exclusion says that in order to count only unique ways of doing a task, we must add the number of ways to do it in one way and the number of ways to do it in another and then subtract the number of ways to do the task that are common to both sets of ways.
For more information you can visit reference
And Also Worth Mentioning
L.C.M and G.C.D code
You can see all the code here in my Github Repo
