Competitive Programming

From Metakgp Wiki
Jump to navigation Jump to search

This article has been originally written during the winter of 2019-2020. While there are many articles and resources on the internet on "How to start with competitive programming", this has been written keeping in mind some of the dynamics of IIT Kharagpur, and to save students from Paradox of Choice.

Why Competitive Programming?

Did you like solving hard math problems, or olympiad problems in your high school? If that's so then chances are that you will like Competitive Programming too. While there are a few benefits from competitive programming, like getting noticed by recruiters and enhancing your problem solving skills, for many it is a hobby to many who like to feel the spirit of a problem solving competitions and the adrenaline rush that comes with it.

Instead of writing the whole article from scratch, I will just attach the necessary, and sufficient resources needed.

Resources in KGP

I'm amazed at the number of anynomous queries, on fundae page, saying that KGP lacks resources for Competitive Programming. I guess, for some reason the resource are not well known. So let's list all of them, once and for all.

Basic Information

Problem Solving

  • There are lot of programming websites where you can practice competitive programming. Almost all of them follow the same format, where you are given a problem, and you have to write and submit code that will solve the problem. Your solution will be checked on some test cases and you'll be given a verdict depending on, if your program outputs to all the test cases correctly, or not, or if it ends up having a segmentation fault.

Programming Websites

  • Spoj : Spoj is a problem archive. It has many easy problems to help you, if you are just starting with competitive programming. You can sort the problems by number of submissions, and solve first few (say 25 or 30 or 50) problems. The problem with Spoj is that, after sometime you will find it boring because problems here are repititive, and finding good problems is difficult here. This is the website where you can find the classical problem (problem that asks you to directly implement a standard algorithm or trick) for any algorithm.
  • Codechef : If you're just begining with competitive programming, you can right away start with Codechef's. It holds atleast three contests a month. The best thing about codechef is its Long challenges, which are aimed for beginners. Each long challenge starts on first friday of every month and lasts for 10 days, and therefore you get enough time to think about problems, debug the codes, and search the internet to learn related things. It also hosts two short contests, Codechef Cook off, and Codechef Lunchtime. Lunchtime consists of more mathematical and ad-hoc problems.
  • Codeforces : This is the most used competitive programming website. It has a lot of features, including problem ratings, virtual contests, gym, mashups, and better problems. It hosts 5-6 short contests every month. Once you are familiar with problem solving on codechef, start solving problems on codeforces too. Start participating in contests here, once you gain some confidence. Comparing to interview problems, almost no interview problem is harder than Codeforces Div2D.
  • Atcoder : It holds contests quite irregualry, but the quality of problems is far better than any of the other programming platform. Start solving problems here, once you are comfortable with codeforces problems, and wants to improve your problem solving skills.
  • Interviewbit : This website contains minimal problems to get you acquainted through Competitive Programming needed to crack interviews, if you are short on time. Once you are familiar with basics needed for Competitive Programming, and want to prepare for interviews, this is the place you should head to. Even if you are already too good at Competitive Programming, I would suggest you to solve interviewbit to get a taste of problems that are asked in interview.
  • LeetCode : If you want to solve more interview-related problems on some specific topics other than the ones on interviewbit, then LeetCode covers that for you. It contains a lot of problems that were asked in previous interviews of companies.

RoadMap

Learn Basic syntax

  • Learn the basic syntax of any programming language until loops, functions, recursion, struct. You can choose any programming language to begin with, java, python, C, C++. This article will mainly focus on C++, as it is used by most competitive programmers.
  • C++ is superset of C. If you haven't learnt C yet, then you can directly start with C++.
  • C Video Playlist Hindi , C Video Playlist English, C slides
  • You do not need to learn classes and their properties in C++ for competitive programming. The part of C++ that makes it far more usable than C in CP is the vast variety of contains and algorithms in Standard Template Library. But before moving to that, just learn input output syntax in C++, and most of the rest is almost same as C

What now?

  • The first thing you should do before you start solving problems is to learn about Time and Space Complexity. It's always a good idea to calculate the time complexity of your algorithms before you start implementing it. A rule of thumb is that 10^7 operations can pass in 1 second on any programming judge, but if you're not using any of the costly operations like modulo, and overhead of your program is less, then 10^8 operations may pass too.
  • Now you're all set to solve problems. Go through this well-written article by Triveni Mahata, and try to solve almost all problems from it.
  • If you want to learn some algorithm or some topic, you can find a list of tutorials here CodeMonk Hackerearth

Interview Preparation

  • If you've solved most of the problems in the above article, then you already have had a taste of competitive programming problems, and know about basic uses of STL.
  • If you want to prepare for Interviews, this should be enough to get you going through most of the problems on interviewbit. Directly start solving problems from interviewbit, but make sure to finish almost all problems in the above article before that. Once you're done with interviewbit, you can move on to LeetCode for further practice, and I'm pretty sure, that it is enough for cracking almost all interviews.
  • The article further focuses on, how to improve further in Competitive Programming. If your sole aim is to prepare for interview, you can still practice more problems on codeforces but that is not necessary at all.
  • Please make sure you check out the Interview Blogs Archive by CodeClub, IITKGP

Improving beyond basics

So now, you've already solved enough problems from the blog, and you really liked solving problems. But the problem is that you still get stuck at solving even easy problems.

  • Learn more algorithms and techniques from Prepare Codechef's Advanced section. Do not stop participating in long challenges and other codechef contests just because you are learning new topics. This ideology, almost never ends well.
  • You can find tutorials to almost all algorithms and data structures at CP-agorithms.
  • Start participating in codeforces contests too.
  • If even after solving so many problems, you still can't get Div2C AC during contest time. Do not worry, we all have been there.
  • Start solving problems from Div2 C Ladder.
  • Once you are comfortable with problems from Div2C Ladder and you're able to solve most of them without much effort. Start solving Div2D ladder.
  • If you've solved most (around 50) problems of Div2D Ladder, and you're still not improving, then do not worry. Let me assure you that you're too close to rating 1800-1900. It is just a matter of time. Keep solving.

Beyond 1800

A lot of people in KGP are stuck at around 1800 rating on codeforces. Once you reach the 1800 bar, you know almost all there is to know to reach 2100. The only thing that you need to train now is your problem solving skills. While the gap in rating is just 300 points, it is certainly more hard than getting to 1800 from 1500.

And as I have experienced over time, only people who have been doing competititve programming regularly, and participating in atleast every other contest, have been able to reach 1900 and manage it for a couple of contests.

What problems to solve?

Just solving contest problems regularly will keep you busy. If you still get time, then there are a whole lot of problems on Codeforces, just filter them by your current rating + 100, and keep solving. Here are some other resource to solve problems.

More Resources

  • CP Resources : Contains resources for some advanced algorithms and data structures.
  • CP FuckUps : Contains non-trivial behaviour, or errors. If you too find some non-trivial error while solving problem, send a pull request.
  • Algorithms Resources: Contains some materials for purists to go through. Old classics still seem pertinent in most cases.

Piece of Advice

  • Checking for correctness of your algorithm is not necessary, but is highly recommended. It not only helps you in figuring out the corner cases, but also in getting more insight into the problem. And, I'm pretty sure if people knew that this ability grows so quickly over time, more people would be doing it.
  • Dunning-Kruger Effect, and the fact that it applies to Competitive Programming so well, is my favourite thing to talk about.
    Graph explaining Dunning-Krugger effect
    Dunning-Kruger effect

    • The origin is the point, when you start Competitive Programming, and find it so hard, that you may take hours, and sometimes days to debug your code. Everything seems so new, every problems seems to use a different algorithm, and you feel like you do not have talent needed to excel in CP. But as soon as you solve enough problems, you start observing the patterns, and you realise that most problems are just ad-hocs, using some trivial data-structures.
    • The peak point is when you are rated 1700-1800 on codeforces. You think that you know all there is to know, and that you rating doesn't represent your true level. Your rating is low just because you miss some problems in contests during the last minute, or you couldn't debug it before the contest ended. No Karen, your rating represents your true level, if you think that it doesn't then increase your rating. Numbers don't lie.
    • The minima comes when you're just on the boundary of purple and blue. You are afraid to give any contest because that might decrease your rating. So you avoid participating, because you think that you do not deserve to be purple, it is just purely by chance. Participate in contests. Even if you lose rating in a few contests, you will gain it back. You deserved it :)
    • Don't fall prey for Dunning-Kruger Effect :)
    • Improve your implementation skills.Be time efficient in short contests,have clear thought process.upsolving is most important.make sure u have breadth knowledge of theory.DONOT focus more on rating(be patient:)).Learn several DS,ALGO to take a deep dive into CP.

FAQs

  • I am not able to improve even after solving a lot of problems. What should I do now?
    • Chances are that you are solving only easier problems, until you start solving problems that are outside your comfort zone chances are high that you will not improve. Or, it might be the case that you're only under the impression that you're solving problems, while most of the time you're just scrolling through codeforces blogs, and choosing a problem. In that case, see the number, for they never lie :) . How many problems did you solve in the last month? 20 is not a good answer, if you're saying that you're practicing regularly. But I must mention that even if you're solving a lot of problems, and that too outside your comfort zone, you may not see any improvement. In that case keep patience.
      Black.n.White's cf rating graph
      my cf-rating graph

      Eventhough I was practicing a lot during my third semester, I was stuck in between cyan and blue (mostly on the cyan side :( ), but soon after I had a steep curve, which I did not expect at all. These times come with lots of demotivation and self-disappointment but that's how it works, you cannot improve in a day. You have to give it time.


  • How much time should I spend on a problem?
    • My advice is to spend time on a problem as long as you find it interesting. It's only when you start finding it boring, go for the editorial.

We want to build this FAQs section. So, if you have any other questions that you want me to answer, then feel free to ping me on facebook.