A dive into Competitive Programming

  “In order to understand recursion, you must first understand recursion.”

  Competitive programming is a mind sport which involves solving algorithmic problems related to computer science, math, or logic within some limits or under certain constraints. There are several websites which hold online programming contests and also provide a vast archive of problems to solve in the spare time.

  Below are some of the most popular ones:

1. TopCoder – it’s considered one of the best coding challenge websites and it is also one of the original platforms for competitive programming online. It has a vast collection of algorithmic challenges from past contests that you can solve on your own using their code editor. Also, a few times per month there are held Single Round Matches where you can compete against others in solving challenges.
2. HackerRank – it focuses on computer science topics, so it provides challenges for several domains such as Algorithms, Mathematics, SQL, Functional Programming, AI, and more. It also has a discussion and leaderboard for every challenge, and most challenges come with an editorial that explains it and shows an approach of finding the solution.
3. Codeforces – it is a Russian-based competitive programming website that regularly hosts competitions. The contests are more difficult and their challenges usually require advanced math and knowledge of algorithms.

How to start with competitive programming

  First of all, you need to have a bit of experience in some programming language. The most popular is C++, because of its STL (Standard Template Library) and it is faster compared to other languages. But there are also other languages available like Java, Python, so you can choose the one you are most comfortable with.

  This is basically enough for starters. You can now get on a coding website and start practicing some problems. Sounds easy, right?

  Once you’ve mastered the basics, you can start learning data structures and algorithms to improve your skills. For the beginning, you should understand the following topics: Sorting and searching algorithms, Array, Linked List, Stack, Queue, Binary Tree, Dynamic Programming and Graph Theory.

  Also, you should learn about Big O notation, which is used to classify algorithms according to how their running time or space requirements grow as the input size grows.

  Because problems always have some time and memory constraints, it would be good for you to understand how different algorithms behave and come up with a solution that will pass the tests for the given constraints.

What should you expect from a challenge

  Every challenge consists of the problem statement, input and output, constraints, examples and sometimes additional notes.

  The problems always have a background story behind the relevant data. This is to make them more interesting and to help you improve your analytical skills during the problem-solving process.

  The input and output can vary from contest to contest. It can be, for example, standard input/output, files or a method definition, explicitly stating what parameters it expects and what it should return.

  The constraints consist of time, memory and data limits, for example, “N will be between 1 and 200,000, inclusive.”

  The examples and notes are self-explanatory, they provide some test cases for the input and output. You can use them to test your implementation and also to better understand the problem statement.

  Once you have a solution that works, you can submit your code to the online judge for evaluation. It will test your solution on other test cases and if all the tests pass, then you receive a score. A thing worth mentioning is that very often, corner cases are checked as well, so you should consider implementing a solution that covers them too and not only test the best-case scenario.

Let’s take a look at a coding challenge

  Here’s a problem from HackerRank, called “Save the Queen!”

  The kingdom of Zokoria is under attack! The invaders wish to capture the Queen and conquer Zokoria. Aware of the danger, Heldorf , the captain of the Zokorian army must devise an exit strategy for the Queen.

  In order to do so, the invaders must be kept at bay for a period of time. There are n invaders who must be engaged in fight for as long as possible. The army has k soldiers, with each having the capability to fight for a total of ai seconds. The soldiers can fight against any invader at any time i.e. they can move to fight with another invader by dropping the current fight.

  Heldorf wants you to find out how long does he have to help the Queen escape. You have to find the maximum possible time for which all the n invaders can be kept busy.

Constraints

• 1 ≤ n ≤ k ≤ 10⁴;
• The time for which each soldier can fight a, lies between 1 and 10⁶.

Input Format

  The first line of input contains two numbers n and k – the number of invaders and the number of soldiers respectively. The next line contains k numbers, each integer representing the time for which the respective soldier can engage in a fight.

Output Format

  Print the maximum possible time for which the n invaders can be engaged in a fight. The number should be accurate up to 10^-4 absolute precision.

Sample Input

  3 4
  1000 100 100 100

Sample Output

  150.000000000

Explanation

  Soldier 1 can fight invader 1 from time 0 to time 1000.
  Soldier 2 can fight invader 2 from time 0 to time 50.0.
  Soldier 3 can fight invader 2 from time 50.0 to time 150.0.
  Soldier 4 can fight invader 3 from time 0.0 to time 100.0.
  Soldier 2 can fight invader 3 from time 100.0 to time 150.0.

  This problem is of medium difficulty. One way to solve it is by using Binary Search. We can define a function check(t) which tells if it is possible to keep the invaders engaged for time t. Since this function is monotonically increasing in nature, we can apply Binary Search here.

  For checking, we can assign a soldier to an invader if t ≤ a_i else we can compute the total time we can allot to each invader. Now, since the time can be a real number, we have to be careful about the precision while implementing Binary Search. One way we can get the correct answer is to iterate the Binary Search a fixed number of times so that all bits in the answer have been found and there is no epsilon error.

  The time complexity for the algorithm would be O(k*iterations).

What can you get from competitive programming

  As you can see, competitive programming is quite different from real-life development, you won’t create any product or use any software principles. But it certainly has a value in improving your skills and a lot of positive aspects too:

• It develops many skills. You become better at problem-solving, debugging, testing, and enhance your ability to deliver results under pressure.
• It prepares you well for technical interviews. Apart from side projects and relevant experience, knowledge of data structures and algorithms will help you to ace interviews.
• It teaches you how to work in a team. Many contests involve team participation. So you start to learn how to approach a situation in a group and divide the work in a team.
• You learn to deal with failures. While solving questions in competitive programming, in the beginning, you’ll mostly get only wrong answers. Competitive programmers develop the attitude not to give up, they stick to a problem until they finally achieve results.
• It’s fun! I would say that this is a really important factor. When you enjoy what you are doing, then the other things will come naturally.