Approach towards Competitive Programming

Competitive Programming nowadays is becoming a very popular mind sport and if you are an engineering student and want to work with any popular IT company, the first round before the interview that you’ll come across is the Coding Round. In the coding round, we have a set of programming problems related to real-world. We are supposed to solve them out by using suitable algorithms and once we get a successful submission, we shall qualify for the next round.

To find the best solution, we need to focus on different aspects of solving any problem like the time complexity of the solution and space complexity of the solution. The time complexity of the solution is defined as how much time your solution will take to solve the problem. It depends on the number of loops you used to solve the problem, input provided to test the problem, etc. The space complexity of a solution can be affected by the Data structure you are going to use. The most affecting factor to decide your solution is good or not is your logic you applied to solve.

Let’s discuss it with an example.

To find a number(n) is prime or not we have many approaches like if we run the loop from 2 to n-1 and check with every number that the number is divisible or not. This is the naïve approach that most of us will follow in usual. But the time it takes is O(n). Another approach is that if we only check the number from 2 to n/2. It will also give us the right result but in less time. Because we all know if a number is not divided by 2 then no other number after n/2 will be the option for us. But if we think about this problem more and more then we’ll find that the best naïve approach is to check the number between 2 to ✓n (square root of n) then this approach will give you the best result in terms of time complexity.

This is a very basic example of a logic building. Moving further we’ll discuss some tips on how to improve logic.

1. Whenever you are solving any problem, keep pen and paper with you always. It’ll help you a lot.
2. Whenever you are reading any problem, note down the understanding from the problem. Always remember, in Competitive programming, we have to give a generic solution.
3. After reading the problem, try to find what concepts of programming the problem wants like whether it’s a problem based on sorting or string manipulation, etc.
4. After figuring out what the problem is all about, try to think about different approaches to solve it like whether if I solve this problem with stack then what sort of operations I have to apply or if I solve this problem with the tree then what sort of options I have.
5. After figuring out the solution, try to make a rough algorithm in your notebook, this will give you a idea about all loops you are going to use and different factors to achieve the best output. Now, start coding the problem.
6. After completion of the code, try to dry run the code in a notebook with different types of input that come to your mind. And after checking and refactoring the code on different test cases, submit the code.
7. Pair programming is also a best practice to follow while doing C.P., because before going to solve any problem, discussing it will give you different ideas towards a solution.

These are certain steps that help you to solve different C.P. problems. Sometimes we are stuck on a certain solution and trying to solve the problem with some refactoring in the code. In such cases sometimes we have to take a 5-minute rest and then try to write the whole code again. This will help you out for thinking in different directions.

As a beginner in C.P., the approach that one should follow is to try to learn a topic first and the application of that particular topic. After learning, try to implement your knowledge on different online platforms like Hackerrank, GeeksforGeeks, Codechef, etc. On these platforms, you’ll find a lot of problems on each topic. Try to solve 5 easy, 3 medium, and 2 hard level problems. This approach will give you an idea about all the types of problems.

In conclusion, I can say that practice is the best strategy to follow for improving your competitive programming.