What is the best strategy to improve my skills in competitive programming in 2-3 months?

Answer by Sachin Gupta:

This post has been taken from the blog post  Learn to Code by Competitive Programming written by MV Kaushik when he was interning at HackerEarth

Here are some steps to get started and be good at it.

    • Get comfortable writing code in either of one of these languages C, C++ or Java. Why only C, C++ or Java? Because these are the standard languages allowed in any programming competition.
    • If you are already good at C, it is suggested to learn C++. It is the most popular language among competitive programmers because of its speed and an excellent library in the form of STL (Standard Template Library).
    • Pick an online judge. Recommended ones are Topcoder and Codeforces. These sites have high quality of problems and also allow you to see other’s code post contest completion. These also categorize problems based on the topic. Some other popular judges include SPOJ, CodeChef (powered by SPOJ) andHackerEarth.
    • To begin with, start with simple problems that typically require transformingEnglish to code and does not require any knowledge on algorithms. Solving Div 2 250 (Division 2, 250 points) in Topcoder or Div 2 Problem A in Codeforces is a good start.
    • At the early stages of programming one tends to write long pieces of code, which is actually not required. Try to keep codes short and simple.
    • Practice these problems until you become comfortable that you can submit it for 240 odd points on any day.
    • Start implementing basic(or standard) algorithms. It is suggested to read them from Topcoder tutorials or Introduction to algorithms.

      1) Graph algorithms: Breadth first search(BFS), Depth first search(DFS), Strongly connected components(SCC), Dijkstra, Floyd-Warshall, Minimum spanning tree(MST), Topological sort.

      2) Dynamic programming: Standard dynamic programming problems such as Rod Cutting, Knapsack, Matrix chain multiplication etc.

      3) Number theory: Modular arithmetic, Fermat’s theorem, Chinese remainder theorem(CRT), Euclidian method for GCD, Logarithmic
      Exponentiation, Sieve of Eratosthenes, Euler’s totient function.

      3) Greedy:  Standard problems such as Activity selection.

      4) Search techniques: Binary search, Ternary search and Meet in the middle.

      5) Data structures (Basic): Stacks, Queues, Trees and Heaps.

      6) Data structures (Advanced): Trie, Segment trees, Fenwick tree or Binary indexed tree(BIT), Disjoint data structures.

      7) Strings: Knuth Morris Pratt(KMP), Z algorithm, Suffix arrays/Suffix trees. These are bit advanced algorithms.

      8) Computational geometry: Graham-Scan for convex hull, Line sweep.

      9) Game theory: Basic principles of Nim game, Grundy numbers, Sprague-Grundy theorem.

      The list is not complete but these are the ones that you encounter very frequently in the contests. There are other algorithms but are required very rarely in the contests.

    • You can find description and implementation of standard algorithms here
    • Once you have sufficient knowledge of popular algorithms, you can start solving the medium level problems. That is Div 2 all problems in Topcoder and Codeforces. It is advisable not to go for Div 1 500 at this point.
    • Learning to code is all about practicing. Participate regularly in the programming contests. Solve the ones that you cannot solve in the contest, after the contest. Apart from Topcoder and Codeforces you can also look at HackerEarth Challengesor Codechef contests.
    • Read the codes of high rated programmers. Compare your solution with them. You can observe that it is simple and shorter than your solution. Analyse how they have approached and improve your implementation skills.
    • Read the editorials after the contest. You can learn how to solve the problems that you were not able to solve in the contest and learn alternative ways to solve the problems which you could solve.
    • Always practice the problems that you could solve in the contest. Suppose if you are able to solve Div 2 250 and 500 in the contest but not Div 2 1000 then practice as many Div 2 1000 problems as as you can.
    • Do not spend too much time if you are not getting the solution or are stuck somewhere.
    • After you feel that you have spent enough time, look at the editorials. Understand the algorithm and code it. Do not look at the actual solution before you have attempted to write the code on your own.
    • Programming is a very practical and hands on skill. You have to continuously do it to be good at it. It’s not enough to solve the problem theoretically, you have to code it and get the solution accepted. Knowing which algorithm/logic to use and implementing it are two different things. It takes both to be good at programming.
    • Programming learning phase is going to take a lot of time and the key is practicing regularly. It takes some time before you can attempt Div 1 500 and other tough problems. Do not give up on reading the editorials and implementing them, even if it takes many hours/days. Remember everything requires practice to master it.

It takes considerable amount of time before you get good at it. You have to keep yourself motivated throughout. Forming a team and practicing is a good choice. Not giving up is the key here.

What is the best strategy to improve my skills in competitive programming in 2-3 months?

What was Anudeep Nekkanti’s Competitive Programming strategy to become 35th in Global ranking, in just 6-7 months?

Answer by Anudeep Nekkanti:

What I did ?

Result ?

  • Became very good with C++ and STL
  • Got introduced to most Competitive programming KEYWORDS (like DP, maxflow, sets, hashing, etc)
  • Learned Standard Problems and Algorithms
  • Indenting code
  • Fast typing 😛

How ?
Before starting programming, I searched about how and where to start, many said “Learn an Algorithm, implement it, solve  problems related to it”. I did not do it that way, If you know what algorithm to use you generally think in that direction and leave about correctness.  I did them problem by problem, easy to hard, I spent 1 – 4 hours on a problem.
I get the idea, I code it, Get it Accepted. (I used to test a lot, I always wanted to get AC on first go)

I do not get the idea, I save that problem and try it after a month again. If I still do not get them, then search for hints. If it clearly needed some algorithm which I never used then I first smile (? I could not only because I did not knew the algorithm 😛 ) and then start reading about that algorithm. TopCoder had tutorials of almost all common algorithms. This is where I did a BIG MISTAKE. I never cared about correctness or run-time analysis proof, I always learned how to solve the problem using that algorithm, I hardly learned about how the algorithm works. I feel bad about it now, but that is how I solved those problems then. I solved max-flow, convex hull, etc., problems using described algorithms but I did not UNDERSTAND those algorithms then.

Mistake: Once I started taking part in contests, I completely stopped practice.

35th in Global Ranking

  • CodeChef long contests are comparatively easy ( Which is good, You can learn a lot), you get a lot of time to think about a problem, search for resources. You only need KEYWORDS to search for similar problems.
  • I gave a lot of time for each contest. I used to solve 4 easy problems in 2-3 days, then take 5-6 days for other 3 problems.
  • CodeChef rating system is not good. It is highly Volatile.

If I am to start programming now, I would do it this way

  1. Solve 200 most solved problems on SPOJ, Problem by problem. In 2 months.
    (This will teach all standard problems, algorithms and implementation skills)
  2. Solve problems from CodeChef and CodeForces for 2 months.
    (This will teach variations, we can read others solutions and learn better ways. Skip easy problems)
  3. Solve problems from TopCoder for 2 months.
    (This will teach  Dynamic Programming. Div 1 500p)
  4. Check past ACM ICPC Regional’s Problems
    (Great quality problems)

If I am to learn a new Algorithm now, I would do it this way

  1. Read it from at least 3-4 different sources.
  2. Understand correctness proof and run-time analysis.
    (This is very very important, you will know it only when you  deal with non standard  and hard problems)
  3. Question yourself on every step for correctness. Try to tweak the implementation.
  4. Check other implementations.

Final Note
Thought I became good in solving problems and had good rank. I later(Feb 13) realized that I learned it the wrong way. I then started learning again. I learned all the algorithms again this time gave importance to the algorithm itself, correctness proof and mathematical analysis. It is worth the time.

Lucy and the Flowers – Problem from December long contest, Try to solve it with suffix arrays. You can only if you understand suffix arrays and LCP completely.

I was able to solve a not-so-obvious medium level Max-Flow problem at ACM KGP Onsite only because I completely understood how the algorithm works. It was at 4 hour 25 minutes I got 5th problem accepted, then I read this problem and got it accepted 4 minutes before end. Learning the algorithm helped. Dot.

What was Anudeep Nekkanti’s Competitive Programming strategy to become 35th in Global ranking, in just 6-7 months?