Skip to content

Latest commit

 

History

History
92 lines (90 loc) · 4.82 KB

Subjects.md

File metadata and controls

92 lines (90 loc) · 4.82 KB
Raw

In the name of God

This book is a good reference: Competitive Programmer's Handbook (github)

  • Simple problems
    • A + B
    • Print 1 to N
    • Is even?
    • Count of divisors
    • Sum of divisors
    • 1 to N that sum of divisors (except itself) equals itself
  • Vector
  • Array
    • Reverse a list
  • Set
  • Map
  • Primitive algorithms etc.
    • Area of a triangle by the points
    • Is prime $O(\sqrt{n})$
    • Prime factorization
    • Digits count
      • Reverse number
    • Prime sieve
      • Divisors count
        1. No check for prime (bad)
        2. Factorize, $(a + 1) * (b + 1) ...$
      • Sum of divisors (no check for prime)
      • ...
    • GCD
    • Base change
    • Power
    • with logarithmic order
      1. $a^{10110} = a^{16} * a^4 * a^2$
      2. $a^b = (a^{b/2})^2 [*a]?$
    • Binary search
    • Big integer
  • Other algorithms
    • Bubble sort
    • Insertion sort
    • Shell sort
    • Merge
    • Merge sort
    • Quick sort
  • String
    • Get a string and n characters, index of/occurences count
    • Get a string and n strings, index of/occurences count
    • 746B Remove middle character of a string repeatedly, put them in a line (zopda -> podza)
    • Reverse the previous action
    • Base change, base > 10
    • 745A Using rotates, how many different strings can we generate?
    • 672B Min count of letters changed so that letters are distinct?
  • Recursion
    • Factorial
    • Fibonacci
    • GCD
    • Combination
    • Print the elements of a vector getting the size
    • Towers of Hanoi
    • Reverse a string
    • Binary representation
    • Merge two sorted strings
    • Merge sort
    • DFS
      • Grid of 01, path from top-left to bottom-right exists?
      • ~510B Grid of 0-9, has a cycle of one color?
      • Graph DFS
        • Number of components
        • Has a cycle?
        • Print parts of a bipartite graph
      • Get a tree (by parents) and print height of all the leafs in non-decreasing order.
      • 377A Input a 01 grid (a maze). It is known that 1's are all connected. Change k other 0's to 1's so that the 1's all remain connected. Print "X"s in a "." and "#" grid.
      • 580C Input n and m, an n-vertex tree (edges), and a sequence of n 0 or 1's. The tree is rooted at vertex 1. Find number of leaves of the tree that has a path to root with at most m consecutive 1's.
      • 115A Input a rooted tree (parents). We want to divide its vertices into groups such that no two elements of a group are ancestors of each other. Minimum number of groups?
      • 770C Input n and k, then k numbers (1~n) (the nodes we MUST meet), then n lines: {get t, then t integers (1~(i-1)) (the parents of node i)}. If we meet a node, we must have met all its parents before. Output the minimum number of nodes to be met, then a correct sequence of meets.
      • 832D Input n and q, then a tree of n nodes, then q lines: {get a, b and c}. For three nodes a, b and c, define f(a, b, c) to be the number of common nodes in {the shortest path from a to b} and {the shortest path from a to c}. For each of the q lines, print maximum of f(a, b, c), f(b, c, a) and f(c, a, b).
      • 813C We have a tree, and we play a game on it. Player A puts a piece on node 1, and player B puts one on node x. Player A wants to capture player B's piece, and player B is escaping. If the players are both smart enough, how many turns will the game last? Input n, x and n - 1 lines of edges.
      • 780C Input a tree by edges. Color it with least colors so that for each a, b and c that a is a neighbour to b and c, they have distinct colors. Output the number of colors, and then the color of each node.
    • Backtrack
      • Print all n-digit numbers in base b.
      • A frog can jump 2, 4 or 5 cells foreward. Print all the sequences of jumps, with which it can get to cell n (or "Impossible" if no ways found).
      • Print all subsets of {1, ..., n}.
      • Print all the ways to create the value of n with coins of value 1, 2, 5 and 10.
      • Print all the paths from between two given nodes in a graph.
      • Assuming we can go up, down, left and right, print all the ways from top-left to bottom-right of a grid that goes through all the cells (input n, and n*n 0s or 1s).
      • Assuming we can go up, down, left and right, print number of the ways from top-left to bottom-right of a grid (input n, and n*n 0s or 1s).
      • Solve a Sudoku grid.
      • Put n queens on an n*n chess board so that no two can attack each other.
  • Dynamic Programming
  • Other problems
    • Rotate a matrix 90degs
    • Matrix operations
    • 793B Get n and m and an n*m grid (n lines) of '.', '*' (wall), 'T' and 'S'. Is there a way from 'S' to 'T' with at most two turns (direction switch)?