Intro to Competitive Programming
Many of you might have heard about the term Competitive Programming and would have wondered what it actually means. I am writing this blog to provide a brief intro to it as well as tell you about the requirements to start pursuing it. Even if you are not a computer science student, I would suggest you explore competitive programming. The reason being it helps you develop logical aptitude and breaking down complex problems into simpler sub-problems. It does not involve learning the concepts of an operating system or database management, but it teaches you how to deal with a problem under some constraints and still come up with the most optimal solution. Let’s dive into the world of competitive programming. I promise you won’t be disappointed! ;)
What is competitive programming
Wikipedia defines competitive programming as a mind SPORT usually held over the Internet or local network. Participants have to program the solution to a given problem according to the specified constraints. For example, suppose you are asked to solve the problem of finding the maximum of n given numbers. Your task would be to code its solution in the language of your choice which can find the answer for any given input.
Now, what makes it different from other sports? Hmm…many of you might play football. Some of you might be really good at it. But what are the chances of you ever getting the opportunity to share the field with the likes of Ronaldo or Messi? Next to impossible right. What competitive programming offers you is the chance to compete with the best! You would be participating in contests where the best programmers of the world would be your competitors. The opportunity to compare one’s performance with the likes of Vaibhav Gosain, Rajat De, Petr, etc. excites a beginner and motivates him/her to improve his game. Don’t know these names? Well, it won’t be wrong to call them the best coders out there. And trust me, once you start with cp they will be the guys you would look up to.
Why should I try it
Want to land a job at Google? Want to crack interviews for a software company? Start programming cause competitive programming contests are often used as preliminary round during the selection process of many software and IT sector companies. Tech giants such as Google and Facebook organize their own contests for hiring purposes. The International Olympiad in Informatics (IOI) is an annual competitive programming competition for secondary school students. It serves as a highway to the world’s topmost universities like MIT and Stanford. Being an Indian student, you might not get a seat at IITs but who cares when you have an even better option.
You learn a programming language, its intricacies and get familiar with writing code on a regular basis. Almost any real-world job requires the ability to visualize a problem and come up with a fast and efficient way of solving it. Wait, isn’t this what you learned through cp? :)
Which language should I use
Most of the programmers prefer C++ due to its simplicity and a very powerful standard template library. As such, there is no problem with Java and python too. Still, I would suggest you learn C++ because:
a) I haven’t seen an online contest yet which does not allow C++.
b) its STL is very powerful and you get to implement data structures such as queue, stack, lists, etc with a single line of code.
c) most of the blogs and tutorials would use C++ and its knowledge will enable you to understand them quickly
You can learn C++ from here.
How to start
There is only one way to start competitive programming: open any online judge and start participating. Start with the easy problems gradually climbing up the ladder. Basic understanding of arrays, strings, functions, and loops will get you through the initial problems. It will take time to learn and apply advanced algorithms and data structures. Maybe you won’t be able to come up with the solution instantly. Keep thinking about it. Try harder. Still, if you are not getting it, try to google the solution. Learn how to read other programmer's code. It will teach you about the tricks and shorthands you can use to save time in an ongoing contest. Various platforms to practice competitive programming are:
Codeforces: It hosts 5–6 short contests of duration 2 or 2.5 hours each month. The problem-set is quite interesting and the contests see participation from all around the globe. The rating system keeps you on your toes and motivates you to improve. There are two divisions — 1 and 2. You start with a rating of 1500. The contestants with a rating >=1900 are in the DIv-1 category.
Codechef: There are 3 monthly contests. Cook-off and Lunchtime are the short contests of 3-hour duration. Codechef Long Challenge is a 10-day contest. One can learn a lot of new stuff while solving problems of the long challenge as there is no time constraint. Visit here and you will find problems sorted according to their difficulty level.
Atcoder : This is also a great platform that is gaining popularity today. A nice set of problems with regular contests will help you a lot.
Hackerrank: Here you will find problems sorted according to the data structure being used or the algorithm to be implemented. Week of code is a great challenge and do participate in it.
Hackerearth: Another great platform. Have comment sections with each problem to discuss it. There are many tutorials and blogs available on hacker earth to learn from. You will find a great tutorial on the standard template library here.
There are many other sites like spoj, topcoder, a2oj etc. You can explore them and choose the one which suits you best.
Apart from these monthly contests, there are annual contests. Thousands participate in them as they are more prestigious and have value.
ACM-ICPC: International Collegiate Programming Competition is called the Olympics of Competitive Programming. It’s a team competition with each team having three members. There are three rounds — Online Round, Onsite and World Finals. Only college students can participate in it. This year, the team Triangulation from IIT Roorkee was able to reach World Finals!
Google Code Jam: Google Code Jam is an international programming competition hosted and administered by Google. The competition began in 2003 as a means to identify top engineering talent for potential employment at Google. A way to get the opportunity to interview with google!
Hacker Cup: Facebook Hacker Cup is an international programming competition hosted and administered by Facebook. The competition began in 2011 as a means to identify top engineering talent for potential employment at Facebook. The competition consists of a set of algorithmic problems that must be solved in a fixed amount of time. Competitors may use any programming language and development environment to write their solutions.
From where can I learn
I would suggest learning through participating. Stuck on a problem, search the algorithm mentioned in its tag and read about its working and implementation. Geeksforgeeks will be your best friend. If you want to learn in a more disciplined way, Introduction to algorithms course by MIT OpenCourseWare is a good option. If you prefer books rather than lecture videos, Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (popularly known as CLRS) is a great book but with a lot of mathematics involved to analyze the algorithm and its complexity. If you have the patience and time, go for it. Otherwise, The Algorithm Design Manual by Skiena will come in handy.
Remember that the most important thing is you should have fun while solving problems cause one can’t continue something for long if we are not enjoying it. If you are feeling tired, take a break. Return after a while with fresh vigor and energy. The biggest room in the world is room for improvement. Keep practicing, keep participating and the pursuit of perfection will lead you on to the path of success!
Still, have some unanswered queries? leave them in the comments section and I will try my best to help you out.
Written by Vinay Aggarwal.