Learn Competitive Programming

tutorial
, ,
1

How do I Learn to Code? This is probably the most nagging question at the back of your mind, once you have decided that you want to learn programming. Like learning anything else, there is no standard process for learning to code. Of course there are guidelines, there are courses, there are ideologies and there are set traditions, but there is no one single correct way.

One school of thought which is very popular and fairly simple to begin with is Competitive Programming. Getting started with it is quite easy and if one devotes sufficient amount of time and effort, you can develop a very strong grasp of programming logic in relatively short amount of time.

Here are some steps to get started and be good at it-

Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.

If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).

Pick an online judge. Recommended ones are Topcoder and Codeforces or Codechef. These sites have high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ) and HackerEarth.

To begin with, start with simple problems that typically require transforming English to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.

At the early stages of programming one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.

Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.

Keep Calm & Learn To CODE

![alt text][1]

Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials or Introduction to algorithms.

  1. Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.

  2. Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.

  3. Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic Exponentiation, Sieve of Eratosthenes, Euler’s totient function.

  4. Greedy: Standard problems such as Activity selection.

  5. Search techniques: Binary search, Ternary search and Meet in the middle.

  6. Data structures (Basic): Stacks, Queues, Trees and Heaps.

  7. Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.

  8. Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.

  9. Computational geometry: Graham-Scan for convex hull, Line sweep.

  10. Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.
    The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.

Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.

Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challenges or Codechef contests.

Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.

Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.

Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.
.
Do not spend too much time if you are not getting the solution or are stuck somewhere.
After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.

Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.

Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.
It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here.

By the way Best of Luck for your programming career .You might beat ACRush :stuck_out_tongue:

87 Likes
2

Additionally, I recommend that you read Competitive Programming by Steven and Felix Halim.

https://sites.google.com/site/stevenhalim/

9 Likes
3

My addition to the post:

A large number of people are in the phase that they are able to do adhoc problems (where you just need to read a problem, and then write the code; no knowledge of any algorithm is required) and they can’t go beyond that OR they find it very hard as to what path to follow to attempt the harder problems at ease.

So, this will help those people:

In the 20 days period of the month when there is no Long Challenge at Codechef, solve the problems at SPOJ according to most users solved. (2-3 hours per day). Few days before the Cook-off attempt any running contest(s) at Codeforces, or previous un-attempted contests just like you would when the contest were live.

In the Long Challenge at Codechef, you’ll be able to solve 2 problems at ease. Then think and keep attempting the next problems. There might be cases when you get TLE, in those cases try to analyze your algorithm and think how can you further improve on that. If you’re fed up, move on to next problem (next most solved problem) and attempt it as well. The idea is to give breaks to your mind, thinking strategy and solve more problems to open it up.

Within 2 months you’ll find tremendous improvement and you’ll be able to solve ~4-5 problems in the Long Challenge at Codechef.

Few tips though:

  1. Don’t think “let’s first study all the algorithms, then I will attempt the problems.”
  2. Don’t think “let’s study this algorithm and do few problems related to it.”

NO!! This is not going to improve your problem solving skill. In the first case, just because you are all the time into theory, you didn’t practice code and you kept studying. In the second case, you already know what algorithm to apply for the problems, so you didn’t trigger that part of mind which thinks How to approach this problem!

Solution: Study problems wise and write code!

That’s why I suggested to do the SPOJ classical problems in the free time of every month, according to most users solved. Almost everyone in this phase might have gone through a basic instinct of the algorithms, so to exploit it to the fullest…just attempt problems, later when you study the algorithm again because you needed it to solve the problem then you will automatically be learning more and there will be an increase in “let’s implement it my way” motive. I would suggest Stanford video lectures, for they provide a good basic idea about algorithms and running time analysis and also about the applications. The explanation is clear and even people with average math skills can understand the proofs and all. Otherwise there are many other sources as well.

Conclusion: Practice! Attempt a problem, study things(algorithms) that are required for that. Move on!
Don’t aim to be a top ranker in few days. Focus on learning things, and be patient and carry on hard work!

Disclaimer: This shouldn’t be taken as a generalized fact. But I have experienced and observed that problem wise strategy does work indeed! So, you’re free to accept/deny this strategy. For each his own, after all. But I will be glad if this write-up could help few people improve their skills.

51 Likes
4

Now u have to say… "You might beat Tourist :P"

2 Likes
5

@bugkiller: please provide link to stanford video lecture for algorithms…:slight_smile:

and definitely within a year or two,… I might beat tourist…:wink:

1 Like
6

Thank you so much for this nice post.

7

Really Good Post …Thanks

8

Thank you got motivated and very much appreciated for your time to make this post.

9

Thank you so much !!! I completely agreed with what you said specially the below two points:

Don’t think “let’s first study all the algorithms, then I will attempt the problems.”
Don’t think “let’s study this algorithm and do few problems related to it.”

I will always remember these tips…:slight_smile:

10

@ppz02 Don’t learn algorithms to beat someone :stuck_out_tongue:

11

Nice, it got me motivated :stuck_out_tongue: :slight_smile:

12

Really good post

13

Agreed reading and on occasion re-reading Competitive Programming by Steven and Felix Halim and The Algorithm Design Manual by Steven Skiena helped me tremendously.

1 Like
14

do anyone have soft copy of this book?

1 Like
15

thnku…:slight_smile:

16

There is an ongoing course on coursera offered by STANFORD on Design and Analysis, Just Enroll and grab all the video…

17

I need tips on how to solve problems on SPOJ… Like i am on 4-5th problem that PRIME number one where segmented sieve is used and i am unable to solve it…

In these situations what should i do? Should i read the algo and try to implement or should i try to figure how can i solve without searching it over internet or should i directly read the implementation and understand whats goin on… ?

Please Help!!

18

@rishabhprsd7 >> Yes, avoid taking a direct look on the implementation or code submitted by others. You can take google’s help though. Spend hours and days till you get it right, and then move on to next problem. It will only come with time, and that time will teach you a lot!

4 Likes
19

Thanks @bugkiller …
:slight_smile:

20

thanku…:slight_smile: