Data-Structure-and-Algorithms

Data Structures and Algorithms Implementation with C++

Notes

• STDIO
  • cout << fixed << setprecision(10)
• Language
  • int capacity: -2 * 10^9 to 2 * 10^9
  • long long int capacity: -9 * 10^18 to 9 * 10^18
  • Global Array Size: 10^7
  • Local Array Size: 10^5
  • typeid operator in c++
• OJ Time Limits
  • Number of iterations in 1 second is : 10^7 to 10^8
  • 10^8 operation -> 1second
  • 10^9 -> 10 seconds
  • 10^10 operation -> 10^10/10^8 or 100seconds
  • 10^11 -> 1000 seconds
• Primes and Divisors
  • log(a^b) = b log(a)
  • n << k -> n * 2^k
  • n >> k -> n / 2^k
  • 2'complement of ~N = -((~(~N))+1) = -(N+1)
  • positive integers: >= 1 and non-negative integers: >=0
  • log6(x) = log_e(x) / log_e(6)
  • builtin functions
    • __builtin_popcount(x)
    • __builtin_clz(x)
    • __builtin_ctz(x)
  • xor Trick
    • n ^ (n + 1) == 1 // if n is even
    • x ^ 0 == x
    • x ^ y == 0 // x == y
    • x ^ x ^ x = x // len even
    • x ^ x ^ x ^ x = 0 // len odd
  • BIT LOW: Think about each bit separately. That's it. It will make your life real comfy.
  • The complexity of bitwise operations in bitset of size is O(size/32) or O(size/64)
• Modular Arithmetic
  • Notation:
    • expr1 ≡ expr2(mod m). This is read as "expr1 is congruent to expr2 modulo m", and is shorthand for expr1 mod m=expr2 mod m.
  • Basic arithmetics:
    • -b % m = (m - b) % m
      • -4 % 6 = (6 - 4) % 6
      • -49 % 6 = ((-47 % 6) + 6) % 6
      • finally -b % m = ((-b % m) + m) % m
    • a % b = a - (floor(a/b) * b)
    • (a + b) % m = (a % m + b % m) % m
    • (a - b) % m = (a % m - b % m) % m
    • (a * b) % m = (a % m * b % m) % m
    • 25 ^ 4 % 10 = (25 % 10 * 25 % 10 * 25 % 10 * 25 % 10) % 10 = (5 * 5 * 5 * 5) % 10 = (5 % 10 * 5 % 10 * 5 % 10 * 5 % 10) % 10
  • modulo 2^32 and 2^64
    • x % 10^k got last k digit
    • x % 2^k got last k bit
    • x % 2^k = x & (2^k - 1)
    • Note that x % 2^k = x & (2^k - 1). So unsigned int x, y, z; z = x * y is the same as z = 1LL * x * y % 2^32. Similarly unsigned long long will automatically take modulo by 2^64.
  • modular multiplicative inverse
    • mmi defined when a and m is coprime
    • if gcd(a, m) == 1 then a and m is coprime
    • (a / b) % m => (a * b^-1) % m => (a % m) * (b^-1 % m) % m
    • b^-1 % m - modular multiplicative inverse of b
    • (a * b) % m = 1 - b is mmi of a => ((a % m) * (b % m)) % m = 1
  • fermat's little theorem
    • a ^ m-1 = 1 % m -> fermat's little theorem, here m is prime and a is not multiple of m
    • a^-1 % m = a^m-2 => a^-1 = a^m-2 % m
    • a / b % m = a * b^m-2 % m if m is prime
  • intuitive mod
    • x mod m < m / 2 when x >= m.

STL Components list

• Functions
  • Min/Max: min(), max(), min_element(), max_element()
  • Binary Search: binary_search(), upper_bound(), lower_bound()
  • Modifying: reverse(), swap(), unique()
  • Non-modifying: count()
  • Sorting: sort()

Path

complexity

• time complexity
• space complexity
• constant O(1)
• logarithmic O(log n)
• linear O(n)
• quadratic O(n^2)
• cubic O(n^3)
• linearithmic O(n log n)
• exponential O(2^n)
• factorial O(n!)
• O(sqrt(n))

recursion

• print 1 to n
• print n to 1
• sum of array
• sum of n number
• digit sum
• fibonacci
• gcd with recursion
• calculate x of the power y
• reverse string

stl

• pair
• vector
• iterator
• string, stringstream
• map, unordered_map
• set, unordered_set, multiset
• bitset
• math.h
• algorithms
• stack
• queue, deque, priority_queue

sort

• selection sort
• bubble sort
• insertion sort
• counting sort
• merge sort
• lexicographical sorting
• std::sort()
• comparator function
• quick sort

search

• linear search
• binary search
• lower bound
• upper bound
• peak element
• first last occurrence
• rotated array
• max in a hill
• square root

prime

• divisors
• gcd lcm
• primality test
• prime factors
• sieve of eratosthenes
• string multiplication

bits

• base conversion
• bitwise operators
• k-th bit on/off and set/unset
• bit masking
• builtin functions
• xor trick
• bitset
• contribution technique

mods

• basic arithmetics
• overflow
• bigmod (binary exponentiation)
• modular inverse (modular multiplicative inverse)
• mulmod
• factorial with mod

data structure

• stack
• queue
• circular queue
• deque
• singly linked list
• priority queue

graph

• adjacency matrix
• adjacency list
• adjacency matrix with edge weight
• adjacency list with edge weight
• dfs (depth first search)