Competitive Programming – An Introduction
@sid12.dubeySiddhant Dubey Hello I’m Siddhant Dubey, a high schooler who loves programming, reading, and tech in general! I wri Competitive Programming is an art form. It is creative problem solving at its finest, a combination of hard analytical thinking and creativity. Competitive programmers use their knowledge of algorithms and data structures and logical reasoning skills to solve challenging algorithmic problems in a limited time frame. Java and C are extremely popular due to their relative run-time efficiency compared to a language like Python. C is my preferred competitive programming language as I love its Standard Template Library (STL) which allows for quick write ups of solutions. Without further ado, lets get right into it. How to Get Started Learn C I know most people might not want to hear this, but as I mentioned already, Python will be hard to succeed with in competitions. C as a language for Competitive Programming is fairly easy to pick up, but like any languages understanding the nuances takes a little bit more time. Here are a couple of resources I found helpful: Learn Algorithm Analysis Algorithm Analysis a llows you to look at the solution you came up with and see whether or not it will run in time for a contest or if it will exceed the time limit imposed by the online judge. Time Complexity analysis as the name suggests, quantifies the amount of time that an algorithm takes to run, it is where the famous O(n) notation comes from. This is called big O notation and yields the worst-case scenario run-time, that is the longest it would take for the algorithm to run. O(n) then means that if there are n elements to perform an operation on, the algorithm would run in time proportional to the n elements. Similarly O(n^2) is proportional to n^2 and O(log n) is proportional to log(n). There are other types of Time Complexity Analysis that are also handy. Here’s a resource to read up on Algorithm Analysis: Learn how to Brute Force Problems At the start of one’s competitive programming journey you more often than not encounter problems that can be brute forced with simple algorithms and do not require optimization to solve. In this case, you can usually just code out the solution step by step rather than applying specific algorithms. To get good at brute forcing problems, all you really have to do is practice. I would advise practicing rating 1000 problems on codeforces.com. Codeforces is a wonderful site to practice your competitive programming skills on. Learn Greedy Algorithms Greedy algorithms make the locally optimal choice at each stage of the algorithm in the hope of finding the global optimum. These are usually more efficient than Brute Force solutions as long as you can come up with a greedy solution. They are not suited to every type of problem and may end up being inefficient if you apply them in places they shouldn’t be used. Here is some great information on Greedy Algorithms: Learn Dynamic Programming Dynamic Programming is an optimization on normal recursion. Essentially it involves solving subproblems, saving those solutions, so that you don’t have to resolve them later on as you would with normal recursion. This greatly reduces time complexity and is helpful on recursive type problems. » Read More
Like to keep reading?
This article first appeared on hackernoon.com. If you'd like to keep reading, follow the white rabbit.