This document is to guide those people who want to get started or have just started with competitive programming.
Originally, this document was prepared during the summers of 2014 to help the freshers of Indian Institute of Technology, Kanpur. So, we thought it might be useful to others as well.
Prerequisite : Basics of any programming language. We will follow C/C++.
Note : Please note that this blog is not meant to explain concepts in details. The Aim of this blog is to guide you about which topics you should read and practice in a systematic way. However, in many places short explanations have been included for their relevance. Relevant problems are given after each topic. Proper sources are given from where these concepts can be studied. Where sources are not mentioned, that means these are very very popular and you can get to know about them just by a single google search. Move forward and enjoy it !
All the following things are from our experience and not something written on stone.
PARTICIPATE PARTICIPATE PARTICIPATE (the only mantra)
SPOJ: Its a problem Archive (recommended for all beginners)
CODECHEF: Do all the three contests every month. Do participate in CodeChef LunchTime for sure.
Codeforces: 4 to 5 short contests of 2 hour in a month (Do them once you develop some confidence).
Online Programming Contests
You write codes and submit them online . The judge runs your code and checks the output of your program for several inputs and gives the result based on your program’s outputs.You must follow exact I/O formats. For example, do not print statements like : “please enter a number”, etc :P
Each problem has constraints :
Properly analyse the constraints before you start coding.
Types of errors you may encounter apart from wrong answer :
Run Time Error (Most Encountered)
Segmentation fault ( accessing an illegal memory address)
Declaration of an array of HUGE HUGE(more than 10^8 ints) size -_- .
Compilation error
Time Limit Exceeded
Wrong Answer [most encountered]
Wrong answer means that the output given by your program did not match the correct output for that input (or did not fulfill the conditions in case multiple solutions were possible). This is the most frequently occurring bug that you will face and getting rid of it can be a pain.
Now its time for some serious debugging.Modulate your code, that means if I have to first generate a graph and then apply shortest path on it, I check first if the graph has been generated correctly. Some speed can be traded for accuracy, with practice you will learn to write accurate programs faster.
If you have already proven your algorithm then try to generate some test cases and check it against you program.
Case 1: Your program fails for you own inputs but you don’t understand how.
Case 2: You program passes for you hand made test case but still gives WA on judge.
Other Points:
Sometimes when you are stuck . Check the running time of other accepted codes to take an insight like what Order of solution other people are writing / what amount of memory they are using.
4 MB ~ array of size 10^6 . Or 2-d array of size 10^3*10^3
Standard Memory limits are of Order of 256MB. You cannot allocate more than 4 MB space inside a function (it gives segmentation fault). Thus if you have to make an array of size >= 10^6 , make it global or use dynamic memory allocation.
Order analysis :
Order of a program is a function dependent on the algorithm you code. We wont go in theoretical details just think Order of program as the total number of steps that program will take to generate output generally a function based on input like O(n^2), O(n) or O(log n) .
Suppose you write a program to add N numbers .See the following code.
int curr,sum=0;
for(int i=0;i<n;i++)
{
scanf(“%d”,&curr);
sum = sum+curr;
}
Total number of computations = n*(1+1+1+1)
n times checking i<n. n times i++ n times scanf n times + operating
So total of 4*N. We remove the constant and call it O(N) This is the simplest I can explain.You will get further understanding with practice and learning.
You must know running time of these algorithms (MUST)
Binary Search -> ? Merge / Quick sort -> ? Searching an element in sorted/unsorted array -> ?
HCF / LCM / Factorization / Prime CHeck ?
We all know the computation power of a processor is also limited. Assume 1 sec ~ 10^8 operations per second . (for spoj old server it is 4*10^6). Keep this in mind while solving any problem.
If your program takes O(n^2) steps and problems has T test cases . Then total order is T*N^2.
For T < 100 and N < 1000 . It will pass . But for T < 1000 and N < 1000 it wont . Neither for T < 10 and N < 10000 .
INT OVERFLOW :
Sum three numbers. Constraints : 0 < a,b,c < 10^9
int main()
{
int a , b,c;
scanf(“%d %d %d”,&a,&b,&c);
int ans = a + b + c;
printf(“%d”,ans);
return 0;
}
This program won't give correct output for all cases as 310^9 cannot be stored in INTS you need long long int or unsigned int (410^9).
what if 0<a,b,c < 10^1000 ?
Comparing Doubles :
int main()
{
float a ;
scanf(“%f”,&a);
if(a == 10 ) printf(“YES”);
return 0;
}
float / double don’t have infinite precision . BEWARE ( 6/15 digit precision for them respectively). Use a margin of EPS ( ~ 0.0000001 ) in comparing. Ex - if ( abs( a - 10 ) < EPS ) printf(“YES\n”);
Lets do the following problem.
http://www.spoj.com/problems/GAMES/ (discussed)
Standard Template Library (STL):
In your code sometimes you need some data structures and some functions which are used quite frequently. They already have lots of standard functions and data structures implemented within itself which we can use directly.
Data Structures ( To be discussed in later lectures )
Functions
Now imagine writing codes using these inbuilt functions and data structures . It would be much more simpler now.
What headers/libraries should you include ?
Basically the above functions / DS are in different libraries So in some cases you may need to include many headers . But you can include everything using just one header.Ignore headers and #define’s in other coders codes for now.
#include <bits/stdc++.h>
Try the following problem :
www.codechef.com/problems/ANUUND
Which of the above inbuilt function did you use ?
What if we have to sort an Array of structure ?
You can either make a struct and write compare function for it.(Read more at cplusplus.com)
Or you can use an vector of pair
Read This:
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=sorting
Now you are ready to start competitive programming .
You can continue reading this doc or get started on your own . Good luck :)
First, you must learn the basic and well known algorithms . Not only algorithm but you must also understand why that works , proof , code it and analyze it . To know what basic algorithms you must know you can read here(Advice make a quora account if don’t have one).
Also read these answers on how to start competitive programming and get good at it.
http://www.quora.com/ACM-ICPC-1/For-an-ACM-beginner-how-should-I-start
http://www.quora.com/Can-I-crack-the-ACM-ICPC-in-1-5-years-if-I-have-to-start-from-scratch
Topcoder has very nice tutorials on some topics here http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=alg_index.
You must also read this book topic wise to understand an algorithm in more broader way http://ldc.usb.ve/~xiomara/ci2525/ALG_3rd.pdf. [Introduction to Algorithms By Cormen]
To get good at writing fast codes and improving your implementation follow this:
My personal advice is to start practicing on topcoder . Start with Div2 250 master it then start with Div2 500 master it then move to Div1 250 .Also read the editorials of problem you solve and the codes of fastest submissions to learn how to implement codes in simple and elegant way.Meanwhile keep learning algorithms and keep practicing them on SPOJ or Codechef or Codeforces . And do read the tutorials, after a time you will realize that the tricks and methods to solve are repeating themselves . We learn from practice only.In the beginning you will feel that every problem uses a different algorithm,How can anyone learn so much but I assure you after a time the logics/algorithms will start to repeat and after some time you will be able to solve problems using those algorithms in actual contests.
Below are few topics to start with and problems related to those topic.
They are very basic stuffs and you can learn all you need to know by just googling.
“When i will get some time I will try to update and give more details about the topics a newbie should cover.”
Try to do all the problems stated below if you are a beginner.
PRIMES
Practice Problems :
Try as many as you can.
Go through these tutorials (The listed problems might be tough but do read the tutorial)
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=combinatorics
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=math_for_topcoders
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primeNumbers
Basic Number Theory
solving linear recurrence using matrix exponentiation(like fibonacci)
Practice problems:
Power of BITS
Some cool Tricks
Problem : You are given N numbers and a numbers S. Check if there exist some subset of the given numbers which sums equal to S .What if you are asked to compute the number of such subsets ?
Read this for further knowledge
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=bitManipulation
Binary Search :
sample implementation :
int l = 0, r = 10000, key_val = SOME_VALUE, m;
while (r - l > 1)
{
m = (l+r) >> 1;
int val = some_non_decreasing_function(m);
if(val < key_val) l = m;
else r = m;
}
if (some_non_decreasing_function(l) == key_val ) return l;
else return r;
// this can be modified in a variety of ways, as required in the problem
Practice Problems:
The Beauty of Standard Template Library of C++
Vectors in one dimension and two dimension
Now use stacks to taste its beauty and solve the following problem too.
Queue
Priority Queue
SomePractice Problems Before you proceed further
GRAPHS
Any Ideas ?
Def : Think graphs as a relation between node , related nodes are connected via edge.
How to store a graph ? ( space complexity )
You must know the following terminologies regarding Graphs :
Tree [[ connected graph with N nodes and N-1 edges]]
Cycle in graph
Directed Acyclic Graph [[ DAG ]]
Bipartite Graph ( Tree is an example of Bipartite Graph . Interesting Isn’t it.)
Breadth First Search/Traversal (BFS) [[ very important, master it as soon as possible]]
Depth First Search/Traversal (DFS) [[very very important, master it as soon as possible]]
Now try the problems given at the beginning !
Problem : You are given a Graph. Find the number of connected components in the Graph.
Hint : DFS or BFS.
Problem : You are given a grid with few cells blocked and others open. You are given a cell , call is source, and another cell , call it dest. You can move from some cell u to some another cell v if cell v is open and it is adjacent to cell u. You have to find the shortest path from source to dest.
Hint : Try to think the grid as a Graph and apply some shortest path algorithm. Which one ? You think !
Problem : You are given a Tree. You need to find two vertices u and v such that distance between them maximum. [[http://www.spoj.com/problems/PT07Z/]]
Hint : Try to do it in O(1) number of DFS or BFS !
GREEDY ALGORITHMS
Greedy Algorithms are one of the most intuitive algorithms. Whenever we see a problem we first try to apply some greedy strategy to get the answer(we humans are greedy, aren’t we :P ? ).
Read this tutorial for further insight or you can directly attempt the problems most of the greedy approaches are quite simple and easy to understand/formulate.But many times the proving part might be difficult. But you should always try to prove your greedy approach because most the times it happens that you later realise that you solution does not give the optimal answer.
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=greedyAlg
They are generally used in optimization problems and there exists an optimal substructure to the problem and solutions are generally O(n log n) (sorting) or O(n) (single pass).
Problems List:
Q)A thief breaks into a shop and finds there are N items weight of ith item is Wi and cost of ith item is Ci and thief has a bag of which can carry at most W units of weight. Obviously thief wants to have maximum profit . What strategy he should choose if :
Case 1: If he is allowed to take fractional part of items (like assume item to be a bag of rice and you can take whatever fraction of rice you want). [Hint :: greedy])
Case 2:If he cannot break the items in fractional parts. Will now greedy work ? Try to make some test cases for which greedy will fail.
Most of time when greedy fails its the problem can be solved by Dynamic Programming(DP).
DYNAMIC PROGRAMMING [[ DP ]]
In my view this is one the most important topic in competitive programming. The problems are simple and easy to code but hard to master. Practice as many DP problems as much possible.
You must go through this topcoder tutorial and you must try to solve all the problems listed below in this doc.
( These are basic problems and some with few variations that we feel one should know. You must practice other DP problems too)
Problems list:
For further advanced topics you can follow topcoder tutorials.
This also might be helpful introduction to competitive programming - Stanford.