Templates (for CP)

  1. Next smaller element in left and right side of any element - Link    (Can easily modify)
    • Next greater element for both sides in one pass - Link

  2. String Hashing - Link
    • MUST call precalc() inside function

  3. Count inversions in any random array (GENERAL) - Link
    • Count inversions in binary string - Link

  4. Sum of XOR of all subarrays - Link ——₪—— Original question link
  5. Sum of XOR of all subsequence - Link ——₪—— Original question link
  6. Prefix sum of 2-D array - Link

  7. Number of subarrays with sum = k → Link
  8. Number of subarrays with sum divisible by k → Link
  9. Segment Trees → Link
  10. djikstera algorithm - Link
  11. Prime Factorization of given number n → Link
    • Count no. of divisors in O(N⅓) → Link

Comments

Post a Comment

Popular posts from this blog

DSA Trees + Heap

Image
Trees are special form of graph If n nodes => n-1 edges (means 2 points have only 1 line joining them) They are acyclic => means from node A to node B there is only 1 way to reach Whenever see  stuffs like  connected ,  unique path  -> tree Types of traversal in trees inorder traversion - left -> root -> right preorder traversion - root -> left  -> right postorder traversion - left  -> right -> root If first time visited -> must be root (bcz parent hai)  => PRE-ORDER If second time visited -> left subtree fully analyzed bcz we are moving in anti-clockwise direction => toh left check krke hi aayenge  => IN-ORDER If third time visited -> left and right subtree fully analyzed => POST-ORDER Post-order is reverse of Pre-order from clockwise Binary search tree (BST) = Binary tree + Search property each subtree follows -- left subtree < root value < right subtree Inorder traversal in BST is...
Read more

Modular Basics + Number Theory + Permutations

Image
Binary Exponentiation - to find   a b  →  converted b into binary  Benefit - instead of multiplying b times => multiply   lo g 2 ( b ) times If a is large  →  take  (a % M) If M is itself very large (like 1e18) =>  instead of a*a  →  DO a+a+a....(a times) even if a*a = 1e18  →  will not get reduced log²(n) bcz log(n) for binary_Multiply & log(n) f or expo Same code as expo => Only change * to + everywhere If b is large in a b  →  a b c  ≠  a ( b c  %  M )  ( mod M )  →   cannot take mod in power Use Euler Theorem  →  a b c ≡ a ( b c  % ɸ(m) )  (mod M )  → ɸ is euler totient function For safety, add extra ɸ in power bcz above fails if gcd(a, m) ≠  1 a b c ≡ a (ɸ(m) + ( b c  % ɸ(m) )) ( mod M )   →  updated GCD + prime  properties a divides b + b divides a ---> a =  ±  b gcd is alwa...
Read more