A Better Way To Approach Competitive Programming

This article helps to all those who want to begin with Competitive Programming. The only prerequisite one need is the knowledge of a programming language.

Now, Let us find a better approach to Competitive Programming. Please note:

1. One should read the proper Input and Output format because most of the beginners make mistakes of having extra print statements in the output. So please be careful about the output format. Example – “Please Enter Next Number :” and “Output is : .
2. Analyze the problem constraints before writing code because most of the time you have written the code that is brute force and will not run in the given time limit constraint.

Following are some of the issues that you might face if you are a beginner.:

1. Time Limit : It is given in seconds. It gives you insight into the order of the correct solution. Consider the following situation.Time Limit = 1 Sec
   Let us Assume 1 sec approximately can perform 10^8 operations.
   If you write a program that is of order O(N^2) and the problem has T test cases. Then the total order of your program becomes O(T*N^2).
   If T <= 1000 and N <= 1000, then (ignoring hidden constants in asymptotic notations) your code may not be accepted in the worst case as 1000*1000*1000 is 10^9 operations which mean 10 seconds.
   To avoid TLE, always think of the worst test cases that are possible for the problem and analyze your code in that situation.
2. Run Time Error : It is the one of the most encountered problem by the beginners. The main reason could be :
   1. Segmentation Fault : It is the illegal accessing of memory address.
      e.g int[] array = new int[100]; System.out.println(array[101]);
   2. Declaration of an array of more than 10^8.
   3. Divide & Taking Modulus with 0 .
   4. You should know how to use GDB that will help you to correct your run time error.
3. Compilation Error : It is one of the errors that is frequently faced when programming in C/C++.

4. Wrong Answer : Whenever you encounter WA, write a brute force code & make sure that it is perfect. Now generate test cases using random function in C++. Run your code on these test cases and match the output. Now think of the corner cases that will help you to find the problem in your algorithm.
5. IntOverflow : Many times unknowingly you will exceed the maximum value that can be stored in primitive type int. e.g. Constraints : 0 < num1,num2 <= 10^9

   
   

   
   
   

   #include<iostream.h> int main() {     int num1, num2;     cin >> num1 >> num2;     int answer = num1 + num2;        // error if num1 and num2 are large     // numbers     cout<< answer;         return 0; }

   The above program won’t run correctly always because (2*10^9) it may exceed the maximum value that can be stored in INTS. i.e 10^9. So you will have to use long long int or unsigned int primitive data type for the answer in such a case.

6. Comparing Doubles :

   
   

   
   
   

   int main() {     float a ;     cin >> a;     if (a == 10)       cout << “YES”; }

   float and double data types don’t have infinite precision . Beware (6/15 digit precision for them respectively). So always use a margin of (~0.0000001) in comparing. Example –

   if (abs(a -10) < (0.0000001))
   {
       cout << “YES”;
   }
   

Other Useful Points :
Sometimes when you are stuck. Check running time of other accepted code and analyze about the order of solution is required and the amount of memory that is allowed.

1. 4 MB ~ integer array of size 10^6 (assuming int takes 4 bytes) or 2-d array of size 10^3*10^3

Standard Memory limits in most of the problem are of the order of 256MB.

If you have to allocate a large array, then it is NOT a good idea to do allocation inside a function as memory is allocated and released for every test case, and memory is allocated on the function call stack (stack size is limited at many places). Thus if you have to make an array of large size, make it global.

I hope this article was of help to you and hope that you will now be able to attempt questions being better prepared and thereby perform better, quicker. 🙂