Points to focus on while doing Competitive Programming

Competitive Programming is vital for one’s development in the coding field. This article is going to discuss some basics points one should keep in mind while competing.

• Make a list of functions to perform tasks that are encountered frequently in questions and add them to your code in the form of a template. This saves time during contests and helps in quick submission of solutions. Some valuable functions required to be added in the template are as follows:
  • Power Function (a^N%M, where a, b, N are integers and M is Prime Number)
  • Printing Prime Factors
  • Printing Prime Numbers
  • Function to find nCr using mod
  • Function to calculate GCD.
• Focus on constraints while thinking of an approach to solve the problem. Based on the constraints, check if the devised solution can pass through all the test cases by calculating time complexity of your approach.
• Think of bitmask or brute force only if constraints are small enough (say 2^N) which will not exceed the time limit. Thus, the approach should involve checking all possible combination of outcomes.
• If there is a question involving sorted data in the form of input then think of an approach using Binary Search.
• If there is a question related to Trees, Graphs(cycle-detection and others), develop a mindset to think of an approach revolving around Depth First Search or Breadth-First Search, which is the basic requirement to solve those type of problems. 
• Number Theory:
  • Addition of two or more odd prime numbers will always be an even number (Eg. 13 + 3 = 16, 19 + 5 = 24).
  • Goldbach’s Conjecture is one of the well-known unsolved problems in mathematics(Number theory to be more precise). Note: It is not proved for larger numbers.
  • There are several other concepts in number theory that are required to be grasped in order to do well in CP.
• If a state is dependent on the future state, then solving the problem with a greedy solution is not possible. Moreover, the naive approach can’t be resorted to as it will exceed time limit. Hence, for all such problems, always try to approach with a Dynamic Programming solution. 
  It is very simple if one can write a simple recursive solution that works in an exponential complexity. Store every path visited in memory which could be used later to go in the direction of solution this is called memoization. Once the memoization method learnt gradually learn the tabulation method.
• If there is a question related to Bitwise Operators like XOR, OR, and AND it can changes the array by those operations then, sometimes naive approach will work as there will be at most 64 numbers with different MSBs (2⁶⁴ ). But in this approach, the main task is to identify the base case.
  Let’s take an example where a sorted array in increasing order is given and the task is to make it non-increasing by replacing two adjacent elements with their Bitwise XOR of the two minimum number of times.
  

  Input: arr[] = {2, 5, 6, 8}
  Output: 1
  Explanation:
  Operation 1: Choose elements 2 and 5, and replace 2 them with 2⊕5 = 7.
  Now, the array will be {7, 6, 8} which is non-increasing.
  Hence, the count of operation is 1.

  Approach: This can be solved in naive way also i.e., find a subarray whose XOR is less than element before starting point of subarray or is less than element after the ending point of subarray.

  But, before that handle a base case that is if there exists 3 continuous elements were MSB is same (For Eg. MSB of arr[i – 1] = arr[i] = arr[i + 1]) then the result is obtained by replacing it by arr[i] ⊕ arr[i + 1]. 

  So, for naive approach in array only when N > 60 because 2*(⌊log₂10⁹⌋ + 1) = 60. (Let, a[i] <= 10⁹). Multiply 2 because that is the only last case possible. If it is multiplied by 3 then there will surely be 3 continuous elements with same MSB(Most Significant Bit).

• The GCD of the array elements can also be expressed as:
  

  gcd(a₁, a₂, ⋯, a_{n − 2}, a_{n − 1}, a_n) = gcd(a₁, a₂ – a₁, ⋯, a_{n – 1} – a_{n − 2}, a_n − a_{n − 1})

  Proof:

  gcd(a, b) = gcd(a, b  – a)
  gcd(a, b, c) = gcd(a, gcd(b, c)) = gcd(gcd(a, b), c)
  Then, it can be generalized as: 
  gcd(a₁, a₂, ⋯, a_n−1, a_n)   = gcd(a₁, a₂, ⋯, a_n−2, gcd(a_n−1, a_n))
                                                       = gcd(a₁, a₂, ⋯, a_n−2, gcd(a_n−1, a_n−a_n−1))
                                                       = gcd(a₁, a₂, ⋯, a_n−2, a_n−1, a_n−a_n−1)
                                                       = gcd(a₁, a₂, ⋯, gcd(a_n−2, a_n−1), a_n−a_n−1)
                                                       = gcd(a₁, a₂, ⋯, gcd(a_n−2, a_n−1−a_n−2), a_n−a_n−1) 
                                                           …
                                                       = gcd(a₁, a₂, ⋯, a_n−2, a_n−1−a_n−2, a_n−a_n−1)

• Some of the most used Bitwise Operator properties can be:
  • a ⊕ b = a | b − a & b
  • a + b = a ⊕ b + 2*(a & b)
  • a + b = a | b + a & b

  Here ‘a’ and ‘b’ are integers, ⊕ means XOR, & means AND and | means OR.