Introduction to competitive programming and different “platforms”.

➼ What is Competitive programming?

It is a mindsport in which you will be given a problem and you have to solve it using writing code.Problem will be mathematical and Algorithmic.You can code in any programming language permitted by that contest.Most famous and preferable programming languages are C,C++ and Java.Every contest and online judge permit this languages.

➼ Which language is best suitable for competitive programming?

Java being a compiled language is fast but sometime it do not satisfy all the corner cases therefore your solution will not get AC(accepted).C is the fastest language amongst the permitted languages but it do not support generic programming.Also it do not have a standard template library.Therefore C++ is the most preferable language above all.But it doesn’t matters which language you choose.

➼ Some famous and prestigious competitive programming contests:

These are some of the most famous and prestigious programming contest in the world.

1. ACM-ICPC : This is the most prestigious and biggest contest in the world.A team of three can take part in this contest.This is a multi-tiered programming language.It is backed by IBM(International Business Machine and ACM(Association For Computing Machinery).ACM-ICPC is the olympic for programmers.Read this to know more about ACM-ICPC ACM_ICPC in brief.
2. Google Code-jam : Code-jam is google’s annual programming contest.It takes places worldwide.University student and professionals from all over the world take part in this contest.Google Code Jam in brief.
3. Google Kickstart : Formally known as google APAC .Kickstart is for hiring university students from Asia Pacific university.It is conducted annually.
4. Facebook Hacker-Cup : This is Facebook’s annual programming contest.Takes place every year.They use this to felicitate the best brains in the world.Facebook Hacker Cup in brief.
5. Topcoder Open:This is topcoders annual competitive programming contest that take place worldwide.Topcoder open in details.
6. Codechef Snackdown: Codechef snackdown is the most famous competitive programming contest in India.Codechef organizes it annually to encourage programmers in India.This contest also takes place globally.All the legendary Grandmasters and international Grandmaster attend this event.Codechef Snackdown in details.

➼ Some Online judges or platforms where you can practise CP:

1. Codeforces:This is one of the most famous online judge for competitive programming.This site conducts monthly contest and rate you on basis of your performance.
2. Codechef:This is another online judge where monthly contests are organize.codechef organizes long challenge in which you will be given 7–8 problems and you have to solve them in 10 days.codechef also has Single Round Matches it will consist of 5 problems that needs to be solve in 2:30 hrs.
3. Spoj:spoj is another online judge where you can participate and show you talent.

➼ How to analyze a problem?

Following is the template for every problem in cp.This are the fields that must be given in your question.

1. Paragraph.
2. Input Constraint.
3. Output format.
4. Sample Input.
5. Sample Output.
6. Explanation of sample Input.

1) Paragraph:It is nothing but the description or statement of your problem don’t panic if problem statement is too big.Break that statement into parts.Don’t start writing code just after reading paragraph.

2) Input Constraint:This are the most important attributes in the description of problem.It will help you to analyze the problem.

A standard processor can perform(1–2)*10⁸ operations in one seconds.Let us suppose N is your input now your input constraint lies between 1≤N≤10⁴ and given time limit is 1 second.At this time you can come up with an algorithm which is O(N²) times fast.if input constraint varies from 1 to 10⁸ then you have to come with an algorithm which is as fast as O(N).Else if your Constraint lies between 1 to 10¹⁶ then you have to implement an algorithm which is O(NlogN) or O(logN) times fast.

3) Sample Inputs and Sample Outputs:This are the sample inputs you should get desire output on this.Perform Stress testing as well.

4) Output Format:You need to follow exact output format otherwise you will get a Presentation Error.

This is how you can Analyze a problem.

➼ How Online Judge works?

You will be given a problem and you will write a code.Output file for your code will be generated for your submitted code.Then Online judge tally your answer and time constraint with their system output file.No human will ever check your code on this online judges.Your code will be evaluated by system.

➼ Terminologies and Errors on Online Judges:

1. TLE: TLE stands for Time Limit Exceeded error.This means your code takes more time than expected to execute therefore it can’t be accepted.
2. AC : AC stands for accepted.This tells us that your code passes all the test cases and your solution is accepted by online judge.
3. WA : WA stands for Wrong Answer.It indicates that your code is giving wrong output on some test cases therefore your solution cannot be accepted.
4. MLE:MLE i.e. Memory limit exceeded is a very rare error you will get in CP if your code is taking more space than given constraints.
5. PE : PE stands for Presentation Error you will get PE if you don’t follow the exact output format.

➼ Different problem solving paradigms :

1. Dynamic programming:this is problem solving paradigm in which you store result for some value using Memoization or Tabulation then you recall that values again and again.Many problems in CP are based on this paradigm.
2. Recursion:This is another popular problem solving paradigm.While working with recursion you need to be very familiar with recursive equations and Base cases.
3. Euler’s totient:This is not a paradigm but a theorem which can help in solving many CP questions.

There are many other problem solving paradigms that I am going to discuss in next Blog with details.

➼ Legends of the Competitive Programming:

1. Gennady korotkevich : He is a russian sport programmer fellow of St.Petersburg ITMO university.He is the highest rated sport programer in the history.He has win every single major competition since age of 11.He is the highest rated programmer on codeforces,codechef,hackerrank and Atcoder.

Gennady Korotkevich(THE GOAT)

2. Petr Mitrichev:We are living in the era of gennady and petr.They both are dominating this sport of programming.Petr has also won many prestigious contest till now.Till today he is unbeatable at Topcoder SRM(Single Round Matches).He works at google on their search engine team.

Petr mitrichev

list of some top competitive programmers in the world.

➼ What will you get after doing competitive programming :

If you do competitive programming for 6 to 8 months with proper dedication then you will become very good in writing bugless code.You will become very familiar with all the corner cases.First round of most of the product based companies is based on problem solving i.e competitive programming.You will have a great command over all the data structures and algorithms.Competitive Programming is like going to gym.One is to sharpen your mind and other is to sharpen your body.You will rock in Technical interviews of companies as you will be aware of all the Data structure,algorithms ,mathematics and oops concepts.

In the next upcoming blog I am going to explain various problem solving paradigm and mathematics in competitive programming.

One site i would like to mention to learn Competitive programming theory from scratch is academia.edu.

Thank You for reading!!!