Tips For Data Structures

Tips on STL

Tip 1: In competitive programming always declare the array globally when you need to have a function along with the main function, globally declared arrays can have a size of 10^7 as they are stored in Data Segments.

Tip 2: Whenever you declare a function where you need to return multiple items, or even in general where your goal is to return an array after some modifications, always go for Pass By Reference (eg void swap(int &a, int &b)), it helps you in two ways one, by reducing the time in making a copy of the data and then processing on it and second, as you’re directly working on the main data you can modify as many values as you wish without having to worry about returning the values and dealing with them.

The limit of the size of an array declared inside the main method is 10^5, coz it’s stored in Stack Memory with a memory limit of around 8MB, if the size is more than this then it results in Stack Overflow.
A very peculiar error occurs sometimes when you’re taking multiple strings as input after a cin input. instead of taking required inputs, it automatically takes space as input then takes the remaining two strings, to resolve this use cin.ignore() before using the getline() to take the string as input.
while forming a new string from another string, instead of using syntax like str = str + str2[I], ie adding character to get a string, this method’s time complexity is O(size(string)), Hence listed of adding characters to a string we use push_back(character) whose time complexity is O(n).

Most Critical Mistakes & Tips in Competitive Programming

The moment a beginner hears this word, an image pops up in one’s mind where students are sitting in a room full of Computers and coding some out of the world stuff, We’ll to be honest it’s nothing too hard to grasp so we will be proposing tips that help a programmer to level up faster. So let’s begin with the most underrated points on each topic where even the advanced competitive programmers slip.

So the concept of overflow can be seen in competitive coding a lot, the worst problem of not understanding it is, writing a completely perfect code but Still getting the wrong answer, this is because, at higher input ranges, the compiler strips down the result as per the data size hence it’s important to remember the basic ranges of data types.

Int => [-10⁹To 10⁹]
Long Int / long => [-1012,1012]
Long Long Int / long long => [-1018,10^18]

Example:

C++

// C++ Program, to Illustrate General Tips In Competitive
// Programming
 
// Importing all C++ libraries
#include <bits/stdc++.h>
 
using namespace std;
 
// Main method
int main()
{
 
    // Case: Stack Overflow
    int a = 100000, b = 100000;
    // Expected answer ? 10^10 but
    // no the answer you get is 1410065408, error in
    // precision.
    int c = a * b;
    long long int d = a * b;
 
    // Note: Still error will be generated because
    // calculation was done on two ints which were later
    // converted into long long ie they already
    // lost their data before converting
 
    // Print and display on console
    cout << c << " " << d << endl;
 
    // Now if we store a value more than its capacity then
    // what happens is the number line of range of value
    // becomes a number
    // Example: Circle, If min val is 1 and max is 9, so if
    // we add 1 to 9 it will result in 1, it looped back to
    // starting, this is overflow
 
    int p = INT_MAX;
 
    // An example of overflow
    cout << "An example of overflow " << p + 1 << endl;
 
    // Long long is way better than double,
    // double although can store more than long long but
    // in exchange it will cost you your precision.
    // We can simply use the below command as follows:
    // cout<<fixed(no scientific
    // notation)<<setprecision(0){removes decimal}<<variable
    // to give value same form as long long
 
    // Question where the answer came wrong coz of
    // overflow!!
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
 
        // Here, before i used int and got wrong answer,
        // then made it long long
        long long pdt = 1, temp;
 
        for (int i = 0; i < n; i++) {
            cin >> temp;
            pdt *= temp;
        }
 
        if (pdt % 10 == 2 || pdt % 10 == 3 || pdt % 10 == 5)
            cout << "YES" << endl;
 
        else
            cout << "NO" << endl;
    }
}

Java

// Java Program, to Illustrate General Tips In Competitive
// Programming
 
// Importing required Java libraries
import java.util.*;
 
public class Main {
 
  // Main method
  public static void main(String[] args)
  {
 
    // Case: Stack Overflow
    int a = 100000, b = 100000;
    // Expected answer ? 10^10 but
    // no the answer you get is 1410065408, error in
    // precision.
    int c = a * b;
    long d = (long)a * b;
 
    // Note: Still error will be generated because
    // calculation was done on two ints which were later
    // converted into long long ie they already
    // lost their data before converting
 
    // Print and display on console
    System.out.println(c + " " + d);
 
    // Now if we store a value more than its capacity
    // then what happens is the number line of range of
    // value becomes a number Example: Circle, If min
    // val is 1 and max is 9, so if we add 1 to 9 it
    // will result in 1, it looped back to starting,
    // this is overflow
 
    int p = Integer.MAX_VALUE;
 
    // An example of overflow
    System.out.println("An example of overflow "
                       + (p + 1));
 
    // Long is way better than double,
    // double although can store more than long but
    // in exchange it will cost you your precision.
    // We can simply use the below command as follows:
    // System.out.printf("%.0f", variable)
    // to give value same form as long
 
    // Scanner to read input
    Scanner sc = new Scanner(System.in);
 
    // Question where the answer came wrong coz of
    // overflow!!
    int t = sc.nextInt();
    while (t-- > 0) {
      int n = sc.nextInt();
 
      // Here, before i used int and got wrong answer,
      // then made it long
      long pdt = 1, temp;
 
      for (int i = 0; i < n; i++) {
        temp = sc.nextLong();
        pdt *= temp;
      }
 
      if (pdt % 10 == 2 || pdt % 10 == 3
          || pdt % 10 == 5)
        System.out.println("YES");
 
      else
        System.out.println("NO");
    }
  }
}

C#

// C# Program, to Illustrate General Tips In Competitive
// Programming
 
// Importing required C# libraries
using System;
 
public class MainClass {
 
    // Main method
    public static void Main(string[] args)
    {
        // Case: Stack Overflow
        int a = 100000, b = 100000;
        // Expected answer ? 10^10 but
        // no the answer you get is 1410065408, error in
        // precision.
        int c = a * b;
        long d = (long)a * b;
        // Note: Still error will be generated because
        // calculation was done on two ints which were later
        // converted into long long ie they already
        // lost their data before converting
 
        // Print and display on console
        Console.WriteLine(c + " " + d);
 
        // Now if we store a value more than its capacity
        // then what happens is the number line of range of
        // value becomes a number Example: Circle, If min
        // val is 1 and max is 9, so if we add 1 to 9 it
        // will result in 1, it looped back to starting,
        // this is overflow
 
        int p = int.MaxValue;
 
        // An example of overflow
        Console.WriteLine("An example of overflow "
                          + (p + 1));
 
        // Long is way better than double,
        // double although can store more than long but
        // in exchange it will cost you your precision.
        // We can simply use the below command as follows:
        // Console.WriteLine("{0:0}", variable)
        // to give value same form as long
 
        // Reading input
        int t = int.Parse(Console.ReadLine());
        while (t-- > 0) {
            int n = int.Parse(Console.ReadLine());
 
            // Here, before i used int and got wrong answer,
            // then made it long
            long pdt = 1, temp;
 
            for (int i = 0; i < n; i++) {
                temp = long.Parse(Console.ReadLine());
                pdt *= temp;
            }
 
            if (pdt % 10 == 2 || pdt % 10 == 3
                || pdt % 10 == 5)
                Console.WriteLine("YES");
 
            else
                Console.WriteLine("NO");
        }
    }
}

Python3

# Case: Stack Overflow
a = 100000
b = 100000
# Expected answer ? 10^10 but
# no the answer you get is 1410065408, error in
# precision.
c = a * b
d = a * b
# Note: Still error will be generated because
# calculation was done on two ints which were later
# converted into long long ie they already
# lost their data before converting
 
# Print and display on console
print(c, d)
 
# Now if we store a value more than its capacity then
# what happens is the number line of range of value
# becomes a number
# Example: Circle, If min val is 1 and max is 9, so if
# we add 1 to 9 it will result in 1, it looped back to
# starting, this is overflow
 
p = float("inf")
 
# An example of overflow
print("An example of overflow ", p + 1)
 
# Long long is way better than double,
# double although can store more than long long but
# in exchange it will cost you your precision.
# We can simply use the below command as follows:
# print(fixed(no scientific notation) setprecision(0){removes decimal} variable)
# to give value same form as long long
 
# Question where the answer came wrong coz of overflow!!
t = int(input())
while t > 0:
    n = int(input())
 
    # Here, before i used int and got wrong answer,
    # then made it long long
    pdt = 1
    for i in range(n):
        temp = int(input())
        pdt *= temp
 
    if pdt % 10 == 2 or pdt % 10 == 3 or pdt % 10 == 5:
        print("YES")
    else:
        print("NO")
     
    t -= 1
    

Output

1410065408 1410065408
An example of overflow -2147483648

Tags:

#STL #C++ #Competitive Programming #DSA #GBlog #CPP #STL

Tips on STL

Tips For Data Structures

Most Critical Mistakes & Tips in Competitive Programming

C++

Java

C#

Python3

Similar Reads