(This guide is meant for beginners. If you have solved 100+ problems and are looking for guidance on how to solve problems involving algorithms and data structures, this document is not for you.)
Competitive Programming is an interesting activity which mixes problem solving with programming. It is not only enjoyable but also very demanded in placements. Competitive programming will make you very good at writing efficient programs quickly. If you get really serious with competitive programming, it will make you an expert in data structures and algorithms.
I recommend all Computer Science students to at least try it out.
So how to get started?
Any programming language will do. But most problems are set with C/C++ and Java programmers in mind, so knowing any one of them will be really helpful.
You don't need to know really advanced concepts, like classes or generics/templates.
You should just know if/else, loops, arrays, functions and have some familiarity with the standard library, like math functions, string/array operations and input/output.
For C, <string.h>, <stdio.h>, <math.h>, <stdlib.h> will generally be sufficient to start.
If you know only C, you can easily start. But at some point of time (especially when you reach advanced stages), you'll need features which most languages have but C does not. Learning C++ is very easy if you know C. I'll suggest that you start out with C and learn C++ in parallel with competitive programming.
Even if you are not confident of your skills in a programming language, you can (and should) still start. Competitive programming is also a good way to practice a new language you have learned.
You'll find problems on many websites.
Most websites will give you a specification and ask you to write a program implementing that. You will then have to submit your code. Your program will be automatically compiled and run and you'll be told whether it ran correctly or not. Such websites are known as online judges.
You will find many online judges on the internet. Here is a small list of the most popular ones:
Apart from that, there is also a website called Project Euler. Project Euler does not ask you to submit code. It has direct problems. For example, their problems 7 asks you to find the 10001th prime and submit the answer. You'll need to write code to find this out (since you can't solve this by hand). But once you have written the code, you just need to run it, find out the answer, and submit the answer (not the code).
Sometimes it takes time to get used to online judges and Project Euler can help you easily start. But I recommend that if you choose to solve problems on Project Euler, do it only when starting out. It has advanced problems as well, but I think solving problems on online judges will help you learn faster and is a better use of your time.
You should stick to just one (or maybe two) online judges when you start.
Most online judges have problems categorized by difficulty levels. For each difficulty level, easier problems generally have more submissions. So you can sort problems based on number of submissions to find the easiest ones.
For beginners, I recommend Codechef. If you have never before solved a problems on an online judge, you can begin by solving the easiest problem on Codechef - Life, the Universe, and Everything. You will have to read the Input/Output tutorial to solve the problem. If you face problems, you can refer to my solutions. I have submitted code in many languages, so you'll most likely find a solution in the language of your choice.
SPOJ is also a good place to start. There are problems there even for people who are new to programming.
Remember that it is very important to practice. Try to solve at least one or two questions everyday.
It is helpful if you stay in touch with people who do competitive programming regularly. This will keep you motivated.
Often while practicing, you will not be able to solve some problems. Do not give up easily! Keep trying! But sometimes even after trying for hours, we are not able to solve it. In those cases, it is advisable to look at the editorials. Editorials are step-by-step explanations on how to solve a problem. Often you'll find new innovative ways of solving problems on reading them. So sometimes you should read editorials even if you have been able to solve a problem.
Sometimes reading editorials is not enough to understand how to solve a problem. This is usually the case when you know how to solve it but you are not able to express your ideas as code easily. When that happens, you should try looking at others' code. Some online judges make other people's code public (like Codechef) while some don't (like SPOJ).
Once you solve 15 to 20 problems, you should occasionally take part in programming contests. Many websites host contests regularly.
Codechef has 3 monthly contests - Long challenge, Cookoff and LunchTime. Long Challenge has 10 questions to be solved in 10 days. You should try to solve as many questions as you can (without taking hints from others). Cookoff has 5 questions to be solved in 2.5 hours. Regularly taking part in Cookoff and trying to perform better in it will increase your speed. I have never taken part in lunch time so I don't know much about it but it is probably similar to Cookoff.
You should not be disheartened if you are able to solve only one or two questions. This is natural when starting out. As you get better, you'll be able to solve more and more. If you are not able to solve any question, you should contact a senior and he/she will help you.
When you have solved more than 50 to 75 problems, you should also start solving problems on Codeforces and taking part in Codeforces' contests. This is one of the sites where the most serious programmers of the world can be found.
With regular practice, you should become pretty good. One of my friends solved average 4 questions per day for a year and he recently got AIR 7 in a Codechef Long challenge!
One question I get asked sometimes is what compiler or IDE to use.
If you have Linux or Mac, I would advise you to use:
- gcc for C
- g++ for C++
- javac for Java (both oracle and openjdk are good)
If you are on windows, you might want to use an IDE. Code::Blocks is good for C and C++. I haven't used IDEs for other languages so I can't help you there.
Some online compilers are also available. The most well known is ideone. Codechef has an online compiler called code-compile-run.
In some longer problems, you may want to make your own functions which make code more readable (hence easy to debug). In c/c++ it is pretty easy to do this. Just write
() { //code here. return //this means the function throws out some value. if you dont want this, declare void functions. }
Calling functions is super easy. Just do : (;
If the function is returning something, just catch that in a variable. Eg, int x = sqrt(a);
Each function has its own (seperate) block of memory. Hence, if you declare some variables or arrays in a function, then you can not use them outside the function. This goes for loops (no pun intended!), if statements.
When functions get some variable as from another function, what actually happens is that the second function makes a copy of the data in the variable that it got. (Because, as I said above, all functions have their own memory spaces(stacks)). So, if you update the value of the input inside the function but do not return it, the value of the input in the calling function will not change.
Eg: int foo(int b){ b++; a++; return b;}
main(){ int a = 5; int x = foo(a); printf("%d\n", x); printf("%d\n", a); }
This will give an error during compilation since a is not declared inside the function foo(). Moreover, if you comment out a++; the output will be: 6 5
This was passing by value-since we gave the function foo() the value of the input arguments.
However, if we want to send arrays or pointers as arguments, they are passed by reference (pointers themselves are passed by value, but their content(the addresses) are obviously passed as references, so it appears as if the pointers are passed by reference). This means that the function that receives these arrays actually gets access to the memory in which the array is present. They directly modify that memory. Hence, they dont need to return the arrays after completion.
You can declare some global resources for use by all functions, loops etc. Just write the declaration outside all functions but before/above the functions that might want to use it.
These global variables reside in something thats called the static memory. This is retained throughout the execution of the program. Moreover, if you want to store something in this memory, but give it local scope, then just append the keyword static in the start of the declaration. Eg http://ideone.com/c3lBIH
Note: above code uses recursion, this means that a function calls itself again and again till it reaches what is called the base case after which control returns to the previous call, then the one before it, and so on. Its somewhat like diving in a pool. You go deep inside and then come back to the surface, similarly the calls go to deeper levels and then back to where the first one. Base case is like the floor of the pool, without which you might go too deep.
Tip: any globally declared array/variable will be initialized to zero.
https://www.youtube.com/watch?v=iOq5kSKqeR4 This is a very useful concept that actually becomes a jargon once you start to think about different approaches to a problem and try to compare them. Also, keep in mind that 1 second of processor time usually means that there will be 10^6 instructions (iterations) executed. This will help you get an estimate of whether your code will pass the time limit or not.
You can often benefit a lot from the rich standard libraries offered by most programming languages. After gaining sufficient experience with a programming language, it is advisable to sift through its software libraries to see what all does it offer.
For C/C++, these are good reference sites:
cppreference has the advantage of having an offline version. However, cplusplus.com's reference is better when you are unfamiliar with the things you are reading about (which will generally happen with relatively advanced concepts like iterators and STL containers). cplusplus.com has better explanations for these topics.
Some people realize very late that C++ offers a sort function. This is one of the most used functions in competitive programming.