Skip to content

Latest commit

 

History

History
367 lines (353 loc) · 24.4 KB

README.md

File metadata and controls

367 lines (353 loc) · 24.4 KB
Raw

Feel free to follow my progress on my main online judge profiles:


Solutions index

· #strings · #divide-&-conquer · #ad-hoc · #miscellaneous · #data-structures · #geometry · #brute-force · #graphs · #greedy · #math · #dynamic-programming ·

dynamic programming

  • 🙂 uva/10943
  • 😳 uri/2699: given a 1000-digit number S with some digits hidden, determine the minimum S possible such that S % N == 0
  • 😳 codeforces/166-E
  • 🙂 timus/1225
  • 😳 codeforces/608-C
  • 🙂 uva/10911 → use bitmasks
  • 🙂 uva/10337
  • 🙂 spoj/RPLB
  • 😳 uva/10721
  • 🙂 uva/11450
  • 🙂 spoj/LINEUP → use bitmask
  • 🙂 kattis/narrowartgallery: narrow art gallery
  • 🙂 uva/11000
  • 🙂 uva/10003
  • 😳 uva/10651 → use bitmask
  • 🙂 spoj/TRT → don't memoize the current day
  • 😳 codeforces/1061-C → use space saving + all divisors in O(sqrt(n)) to optimize
  • LCS reduced to LIS
    • 😳 uva/10635
    • 😳 uva/12747: edit distance with only inserting and deleting between two permutations from 1 to N
  • 0-1 knapsack
  • coin change
    • 🙂 codeforces/189-A
    • 😳 uva/166: coin change with limited amount of coins + greedy coin change with unlimited amount of coins; I don't know why, but it works without memo
    • 🙂 uva/11407 → consider the coins as the perfect squares
  • longest common subsequence (LCS)
    • 🙂 spoj/IOIPALIN: given a string, determine the minimal quantity of characters to be inserted into it in order to obtain a palindrome → compute length of string minus lcs between string and reversed string
    • 🙂 spoj/ADASEQEN
  • digit
    • 😳 uri/1707: given two numbers x and y, compute the sum of the decimal digits of the odd numbers in the range [min(x,y) .. max(x,y)]
    • 🙂 spoj/CPCRC1C
  • max 1D range sum
  • max 2D range sum
    • 🙂 uva/108
    • 🥵 uva/10755: max 3D range sum → use max 2D range sum in two of the three dimensions and max 1D range sum (kadane) on the third dimension
  • longest increasing subsequence (LIS)
    • 😳 uva/11456 → find the max(lis[i]+lds[i]-1) for all i in [0 .. N-1], being i where the subsequence starts
    • 🥵 uva/481
    • 😳 uva/10131 → sort elephants based on increasing kg, then apply LDS on iq
    • 😳 uri/1517
  • longest palindromic subsequence (LPS)
  • traveling salesman problem (TSP)
  • subset sum
    • 🙂 uri/1203: check if any subset of A has a sum equal to K
    • 😳 uva/10616: given an array of size N, count how many subsets of size M have their sum divisible by D → use module arithmetic
    • 😳 uva/11658: find the smallest sum s of a subset of A, s >= S → scan as %d.%d
    • 😳 uri/2089 → optimize memory
    • 🙂 uva/624: print the subset of A with the max sum k, k <= K
    • with repetition

math

  • number theory
    • 😳 uri/2291: print n-th divine number, the one that is equal to the sum of the sum of each divisor from 1 to n → think like sieve
    • 😳 uva/547: find the longest DDF sequence → pre-process a array f, where f[i] is the sum of digits of all positive factors of i; think like sieve
    • greatest common divisor (GCD)
      • 🙂 codeforces/822-A
      • 😳 codeforces/75-C: find the gcd(a, b) that is in a query range [lo .. hi] → note that all divisors of gcd(a, b) are also divisors of a and b
      • 🙂 codeforces/854-A: given n, determine maximum possible proper (a < b) and irreducible fraction a/b such that a+b == n
    • module arithmetic
      • 🙂 uva/10176: is a given binary number of 100 digits divisible by 131071?
      • 🙂 uva/374: compute (a^n) % m, where a <= 2^31 and n <= 2^31 → use fast power with mod
    • prime numbers
      • 🙂 spoj/PRIONPRI: prime checking
      • sieve of eratosthenes
        • 😳 uva/10539: compute the quantity of non-prime numbers in [lo .. hi] which are divisible by only a single prime number, 0 < lo <= hi < 10^12 → generate all powers of each prime number
        • 🙂 spoj/AMR11E: print the n-th number that has at least 3 distinct prime factors → use modified sieve
        • 😳 codeforces/576-A
        • 🙂 codeforces/230-B: check if a large n has exactily three distinct positive divisors → check if sqrt(n) is prime
        • 😳 spoj/PRIME1: print all primes p in [m .. n], 0 <= m <= n <= 10^9, n-m <= 10^5 → sieve + prime checking
      • prime factorization
        • 🥵 uri/2661: compute the number of divisors of n that can be written as the product of two or more distinct prime numbers (without repetition), 1 <= n <= 10^12 → note that the product of any combination of prime factors of a number will always be a divisor of that number
        • 🙂 uva/10042
        • 😳 uva/10139: do n! is divisible by m? → check if the prime factors of m are contained in the prime factors of n!
  • matrix exponentiation
    • 🙂 uva/10229 → transform the fibonacci recurrence into a matrix exponentiation
  • game theory
    • minimax
      • 😳 uva/12484: alberto and wanderley take one of two cards at the edges of the cards sequence, alberto want maximize it → fill memo table in row-major order
      • 😳 uva/10111: given a state of a tic tac toe board, check if X will win independent of the O movement → minimax + memo + backtracking
      • optimized
        • 🥵 uva/847: multiplication game → note that if Stan always multiply by 9 and Ollie by 2, it's still an optimal solution
  • ad-hoc
  • combinatorics
    • 🙂 codeforces/459-B: find the max difference between numbers of a given array and the number of ways to get it
    • 🙂 codeforces/131-B
    • combinations
      • multi-combinations
      • binomial coefficient
        • 🥵 uri/2972: calculate the sum of C(N, k)%2 for all k in [0 .. n], i.e., how many odd combinations of k heads between n coins there are → just compute 2^qtyBitsOn(n)
        • 🙂 codeforces/844-B

greedy

graphs

  • maximum flow
    • 🙂 uva/820
    • 😳 uva/10779 → each friend receives 1 flow unit of a sticker and offers a flow of other sticker; Bob also offers, but he receives 1 flow unit of each sticker; maximized it
    • minimum cost
  • shortest path
    • all-pairs
    • single-source
      • negative-weighted and cycle graph
        • 😳 at-coder/ABC137-E: longest distance from 0 to V-1, checking for positive cycle that are part of that path (0 to V-1)
      • weighted graph
        • 😳 uva/11833 → build the graph already with the given constraints
        • 😳 uva/12144: almost shortest path
        • 🥵 live-archive/3652: dijkstra on a given implicit graph as a 2D grid
        • 😳 uva/10806: find the global shortest path from 0 to V-1 (round trip), without repeting edges
        • 🥵 uva/11367 → find the shortest path on state-space graph, where each vertex represent a city and a level of car fuel
      • unweighted graph
        • 😳 uva/12797 → apply a BFS for each subset of letters possible (only 2^10) using bitmask
  • minimum spanning tree (MST)
    • 🙂 uva/1174
    • 🙂 uva/11710
    • 🙂 uva/10034
    • 🙂 spoj/MST
    • minimum spanning subgraph
      • 😳 uva/10397: given an implicit complete graph and some edges, compute the cost of the minimum spanning subgraph
    • minimax path
      • 🙂 uva/10048
      • 😳 uva/10099: maximin path; find the minimum cost of the maximum path from s to t → apply kruskal to get the maximum spanning tree, but stop it when s and t connect
  • traversal
    • 😳 uva/11906 → consider grid as an implicit graph and walk through it avoiding redundant positions (nr, nc)
    • 🙂 uva/11831 → consider grid as an implicit graph and walk through it, or just rotate the robot, for each received instruction
    • 😳 code-jam/2020-1A-pascal-walk-TLE
    • bridges or articulation points
      • 🥵 codeforces/178-B3: given an undirected graph, count how many bridge edges exists between 2 query vertices → group the vertices connected by non-bridge edge during dfs; generate a tree considering each group as a vertice, and using only the bridge edges; find the distance between 2 query vertices of that tree with LCA in O(1)
      • 🥵 uva/12363: given an undirected graph, check if there is a unique path between 2 query vertices → there is a unique path between s and t if the path between them is formed only by bridge edges; for optimize, keep sets for the vertices that are on the same connected component in the pruned graph (with only bridge edges)
      • 🙂 uva/796
    • topological sorting
    • flood fill
      • 🙂 uva/11094
      • 🥵 uva/1103 → consider each pixel as a vertex of an implicit graph, then identify each hieroglyph counting the number of white CCs within it
    • depth-first search (DFS)
    • strongly connected components (SCC)
      • 😳 uva/11504 → count the number of SCCs without incoming edge from a vertex of another SCC
    • edge classification
      • 🙂 codeforces/104-C: check if the given undirected graph can be represented as a set of three or more rooted trees, whose roots are connected by a simple cycle → check if the graph is connective and has only one cycle
      • 🙂 codeforces/510-B: check if a given implicit undirected graph has a cycle of length >= 4
  • specials
    • 😳 uva/12442: given a graph with all vertices with out-degree 1, find the vertice that reaches the most vertices
    • tree
      • 😳 spoj/ONP: infix to postfix conversion → see that the given expression is the in-order traversal in a binary tree, then print post-order traversal recursively without building the tree
      • 🙂 codeforces/115-A: given a forest, find the length of the longest path
      • 🙂 spoj/LABYR1: compute the diameter of a given implicit tree
      • lowest common ancestor (LCA)
        • 🙂 timus/1471: given a weighted tree, find the distance between 2 query vertices
        • 😳 uva/12238: given a weighted tree, find the distance between 2 query vertices
    • directed acyclic graph (DAG)
      • 🙂 uva/988: counting paths from 0 to V-1
    • bipartite
      • bipartite checking
      • max cardinality bipartite matching
        • 😳 uva/10080: max number of preys that can hide safely from an predator attack → consider a bipartite graph with edges that connect a gopher (prey) to an reachable hole
        • 😳 uva/11262 → binary search on answer + MCBM

brute force

  • iterative
  • recursive backtracking
    • 🙂 code-jam/2020-QR-indicium-TLE: generate M, where M[i][j] is any value in [1 .. N] (2 <= N <= 5), but without repeting a value in same line or column, and with the sum of the main diagonal equal to K
    • 😳 uva/10503: given domino pieces, check if it is possible to arrive at a target piece from an initial piece using N intermediate pieces (possibly rotating them) → DFS + backtracking
    • 🙂 live-archive/2883: chess with a single horse against up to 8 pawns; print the length of the minimum sequence of horse moves if it wins
    • 🙂 uva/10344: check if some arithmetic expression of 5 given numbers will result in 23 → check all combination of operators for each permutation of the given numbers
    • 🙂 spoj/MKJUMPS: given an unweighted implicit graph, count the longest possible path → DFS + backtracking
    • sudoku
    • pruned permutations
    • n-queens

geometry

data structures

  • sparse table
  • union-find disjoint sets (UFDS)
  • segment tree
    • 🙂 codeforces/339-D
    • 🙂 live-archive/6139: range product query
    • lazy propagation
      • 😳 uri/2658 → build a segment tree for RSQ, but store an array of size 9 in tree[v], where tree[v][n] indicates the frequency that the note n appears in that interval
      • 😳 uva/11402 → build a segment tree for RSQ, but keep in lazy[v] the type of pending operation to be performed in that interval of A

miscellaneous

ad-hoc

divide & conquer

  • 😳 codeforces/768-B → knowing the size of the final array with a little math, use the same idea to query a range in a segment tree

strings

  • suffix array
    • 😳 spoj/SARRAY: just build a suffix array in O(N * log N)