Mathematics for Competitive Programming

As said by Carl Friedrich Gauss that,

"Mathematics is the Queen of Sciences,
and Arithmetic is the Queen of Mathematics"

it is there. In every concept or in understanding nature Mathematics is there. Every problem can be modeled mathematically.

In this article series, we will focus on the Mathematical Concept which is Necessary or we can say Must for any Competitive Programmer.

Mathematics is one of the most important subjects to study for Competitive Programmer along with Data Structure and Algorithm. It helps in modeling the given problem efficiently, optimizing the algorithm so that it can run within Time Limit.

Below we will be going through one example to look at the importance of mathematics in Problem Solving.

Example: Count Number of Shortest Path to reach from corner A to B in the grid of N x M.

To go to B we need to travel all grids RIGHT of A, and then travel all grids UP to reach B.
This will be the shortest path as we are not repeating any path,
Now let us formulate it,
  • Let us represent the RIGHT Direction by 1 and UP by 0
  • One possible way would be,
    • "1111000" ( i.e, first from A come to C and then from C to B. )
    • Now the number of ways to arrange this string made by 1 and 0 would be the number of the shortest paths to reach from A to B.

=   7! / (3! x 4!)
=   7 choose 3 =  7 choose 4

For N x M grid, it will be  (n+m)! / (n! x m! )
I.e, The number of ways to place N zeros in ( N+M ) spaces.

More Uses:
  • Used in Handling Large integers by Using Modulo Operation.
  • And many different problems which we will be discussing as we start, etc.
What are the things we will be discussing here?
  • Number Theory
  • Combinatorics
  • Computational Geometry
  • Miscellaneous
  • And any of your doubts.

Our goal

  • To be better at Problem Solving.

How we will achieve this?

  • First, study and understand the Concept.
  • Then go through the solved problem. ( Most of these problems will be from Codeforces and CodeChef )
  • And then Practice, Practice and Practice.

Prerequisite
  • Programming Experience in any Language, preferably C/C++.
  • Mathematical Background
  • Basic of Data Structure and Algorithm will be better.

We will be starting with Number Theory from the next article.

Thank You,
Bye and take care,
Enjoy!

Comments