Complete Reference to Competitive Programming

The Complete Reference to

Competitive Programming

by
Ravi Ojha
Software Developer, @HackerEarth

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?

Levels of our Journey

A walk in the Park

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.

Welcome to the Jungle

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

You need to know:

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.

Take the Fast Track

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.

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.

Load up the Weapons

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.

Heavy Artillery

You’ve already become a pro at this game. If you fail in one, go back and analyze where you went wrong. Read the editorials after the contest. Many programmers underestimate the value of post contest analysis, because you had already figured the whole solution but missed just a single case. So the urge of knowing what you missed is irresistible and you’ll never forget what you learnt in the analysis.

Usually there are not many deep algorithm intensive questions in short contests, however longer version such as monthly clash challenges on HackerEarth may have applications of one of these.

Heavy Light Decomposition
Graph Coloring, Network Flow
Sqrt Decomposition.

2 Cents

Many programmers argue that the problems in competitive programming do not relate to the real life programming work. For the most part, it is true. Then why do we do it? Because it makes you a better programmer. How?

Time limit always makes you write time efficient solutions.
Critical test data helps you write correct solutions, in one go!
Further it makes you great at debugging code.
Hard problems makes you break down the problem into chunks, solve them individually and bring it all together to solve the main problem.

Yes, competitive programming is not the only way to master these qualities but it is one of the best ways to do so. Give it a shot, if you enjoy it, it’s worth it. You will be rewarded with objective benefits. If you don’t, even after repeated trials, give yourself a break.

Learn from tutorials and solve problems in our new practice section

Practice