Prepare for Competitive Programming

I started learning C++ from scratch during my first year of College. I knew nothing about programming, algorithms or data structures.Now i am more comfortable with data structure and algorithms.

What language should you choose?

1. C++ — Highly recommended! It’s very fast. Implementing different algorithms takes little time because of STL. C++ is accepted in all competitions. I’ve been using it since my first line of code.
2. C — Go and learn C++ because of STL. If you have knowledge of C, you are ready to code in C++ as well.
3. JAVA — It’s slow. But it has Big Integer class, even if there are very few problems that require using it. If the time limit is tight, you will get Time limit exceeded. Java is not accepted in all competitions.

Where can you practice?

I recommend Sphere Online Judge (SPOJ). It’s effective in terms of quality and quantity. Editorials and solutions are available online if you get stuck while solving problems. Supporting websites SPOJ Toolkit and Problem classifier for SPOJ.pl.

Firstly, you have to master the basics.

After you get used to the language’s syntax it’s time to solve some problems. Start with simple ones that require implementation skills. In this stage, your goal is to define your coding style. Maybe you like to write with lots of spaces, maybe not. Maybe you put the braces on the same line with the ‘if’ statement, maybe not.

And keep in mind these two principles while developing your coding style.

• Easy to implement. You should feel comfortable implementing the solution you came up with. Why? Because during the competition, the last thing you want to happen is to get lost in your code. It’s always better to think 5 more minutes about implementation rather than spending 10 more minutes doing it.
• Easy to read. This means ‘Easy to debug’. Let’s face it, we both know that bugs appear all the time. Do you know that feeling when you have 10 minutes left and you don’t find that fucking bug? Yes, you do. To solve that you have to write legible code. So when you start debugging, the code would feel natural and simple to follow.

How to boost your implementation skills?

Practice, practice and more practice. I recommend you to work the first 250 most solved problem on SPOJ. Solve them in that exact order. And think of the solution for at least one hour.

Take a piece of paper and a pencil and try to think. In this way, you will probably find the solution, but for sure you will develop algorithmic thinking. If you don’t find the solution in one hour, then you can take a look on the forum or editorials to see the solution.

The results of this approach? Fast implementation. And learning classic problems & algorithms.

Secondly, you have to master Algorithms and Data structures.

Follow a hierarchical approach. Did you start running without knowing how to walk? No. Can you build a skyscraper without a strong foundation? Again, no.

Start with fundamental Algorithms and Data structures.

It’s hard to start. Probably because you don’t know what to learn first. That’s why I’ve created an Algorithms and Data structures video course. I’ve made this course in the way I wish I had been taught. The response was incredible, 3000+ students from 100+ countries had joined during the first month.

The most effective way to find what you don’t know is to actually encounter it. It’s what happened to me. I’ve learned many new techniques, that I had never heard of before, by choosing a hard problem.

From every 3 problems you solve, one should teach you something new. If not, choose them more carefully. Choose harder problems!

After you finish those 250 problems from SPOJ, you will have an overview of the main topics of competitive programming. By deeply understanding the logic behind basic algorithms, high-level algorithms will seem easy to understand. So you can rapidly leverage your knowledge.

Now dig deeper into every major topic.

Here is an tremendous resource with Top 10 Algorithms and Data structures in every topic. After those 250 problems from SPOJ, you will know many from that list. But there are still many that you have never heard about. So start learning them in ascending order.

I recommend that after you learn a new algorithm to practice 2–3 problems using it. Search the tag of the algorithm on SPOJ and you’ll find problems that require it. Work them before anything else.

From my experience, in every contest is at least one Dynamic programming problem. Many people get a headache when they hear DP because they don’t understand it.

And it’s a good thing. Because if you truly understand DP, you will win.

I like DP, it’s my favourite topic. And here is DP’s secret: think globally optimal, not just locally. You have to break the problem into simpler subproblems, solving each of them just once, and building the solution combining these solved subproblems. The opposite of DP is a greedy algorithm because the latter picks the locally optimal choice at each step. And locally optimal choices may result in a bad global solution.

When learning new concepts, check TopCoder tutorials. They are very detailed and easy-to-follow. I’ve truly understood Binary Indexed Trees from there.

Well! I hope this added some value to you! Feel free to let me know your comments. :)

For more of my work, follow me on:

LinkedIn: https://linkedin.com/in/shubhaiswal/

GitHub:  https://github.com/Shubham1007 

Cheers!