Competitive Programming Guide

CP Handbook is the one place for all competitive programming lovers as it contains all the algorithms and data structures. Also every topic contains examples and unsolved problems for practice.

Competitive Programming is a sport, I mean literally. Take any sport, let’s consider cricket for that matter, you walk in to bat for the first time. Swing and a miss, do it couple of times and you’ll eventually hit one over the ropes. Now, consider a programming contest as a game of cricket, metaphorically. Compile a code and submit, you may get a WA (Wrong Answer).

Make changes to code and eventually you will get your first AC (Accepted/Correct Answer). Let me give you a sneak peek, about 20% of questions in a programming contest are simple conversion of plain english to a code of your favourite programming language.

Walk right into it, you will learn the unwritten rules of the game as you play harder and get better.

And believe me, you don’t need to know any “fancy name” algorithm or data-structure to get started. Ever heard of “Waft shot”, yet you’re the best batsman in your street, right?

Alright, let’s conquer the first 20% of programming problems out there.

You need to know:

Intermediate hold on any one programming language

English! Convert english to code!

Let’s take an example problem of this level: Terrible Chandu

All you have to do is, read input line from STDIN and print reverse of that line to STDOUT. Go ahead, make a submission. Seek your first AC. Want more? We’ve got loads in our practice section. Look for the ones with thousands of correct submissions.

Okay, now you’re ready to take on some real challenge. Hold tight, we are diving deeper.

You need to know:

1. Sort and Search algorithms

2. Hashing

3. Number Theory

4. Greedy Technique

More importantly, you have to figure out what, when and where to apply them. It gets really tricky and hence to help beginners gain a feeling of confidence we run a series of contests as Code Monk. Before each contest, we release a tutorial on certain topic and later in the contest the problems are aimed only on that particular topic. I’d recommend you to go through the tutorials and solve a question or two on each topic.

By now you’ve realised that the questions are framed to deceive the way we think. Sometimes, If you convert plain english to code, you’d end up with TLE (Time Limit Exceeded) verdict. You need to learn a set of new techniques and algorithms to cope up with the time limits. In certain cases, Dynamic Programming (DP) comes to the rescue. Infact, you might have already intuitively used this technique. There’s always at least one question in any contest that can be solved by DP.

Also, you’d have noticed that there are questions that just can’t solved by linear array data-structures.

1. Graph Theory

2. Disjoint Set Union (Union-find)

3. Minimum Spanning Tree

These set of data structures will get you quite far enough. Moreover, you’d have figured that the real art is to modify the techniques you know in order to solve a question. All Easy-Medium and Medium level questions can be tackled in this fashion.

You are all set to top the leaderboards of Short Programming Challenges, just keep steady persistence. As I’ve already mentioned, it’s a sport, you won’t master it until you actually do it. Go ahead, participate in a short contest, know your strengths, weaknesses and see how you handle the adrenaline mode when the clock is ticking.

Stick to your own logic as long as possible, you’ll eventually come up with something similar to the algorithm required to solve the question. You just need to brush it up. Several of these techniques will help you solve some of the toughest of the problems around.

1. Segment Tree

2. String Algorithms

3. Tries, Suffix Tree, Suffix Array.

4. Heavy Light Decomposition

5. Graph Coloring, Network Flow

6. Sqrt Decomposition.

So Download this CP Handbook and enjoy learning new things also don't forget to CODE them with less Time Complexity.