The notebook folder contains general-purpose algorithms, and the solutions folder contains the solved problems. Feel free to follow my progress on my main online judge profiles:
· #divide-&-conquer · #brute-force · #greedy · #ad-hoc · #graphs · #geometry · #dynamic-programming · #math · #searching · #miscellaneous ·
- two pointers
- 🥵 codeforces/1041-D
- 🙂 codeforces/381-A
- 🙂 codeforces/6-C
- 😳 uva/967:
pope - 😳 codeforces/279-B
- 😳 codeforces/676-C
- union-find disjoint sets (UFDS)
- segment tree
- 🙂 codeforces/339-D
- lazy propagation
- binary search
- 😳 codeforces/1324-D:
given the A and B arrays, count the quantity of pairs i < j such that A[i]+A[j] > B[i]+B[j]→ diff being the A-B array, count, for all i in [0 .. N-2], how many times -diff[i] < diff[j], for all j in [i+1 .. N-1] - 😳 codeforces/1284-B
- 😳 codeforces/91-B:
given the array a, compute the array d, where d[i] = j-(i+1) for the max j such that a[j] < a[i]→ apply binary search on preprocessed array mn, filled from right to left - 🙂 spoj/PAIRS1:
given the A array, count the quantity of pairs i < j such that A[i]-A[j] == K→ search on the sorted array A by the A[n]+K, for all n in [0 .. N-1] - on answer
- 😳 codeforces/1223-C
- 🥵 codeforces/460-C
- 😳 spoj/AGGRCOW:
given an array A of size N (2 <= N <= 10^5), print the largest minimum distance between any two of C (C <= N) elements choosen any - 😳 uri/2973
- 😳 uva/12097
- 😳 codeforces/1324-D:
- combinatorics
- 🙂 codeforces/131-B
- 🙂 codeforces/459-B:
find the max difference between numbers of a given array and the number of ways to get it - fibonacci numbers
- 😳 uva/10334 → compute (n+2)-th fibonnaci number
- combinations
- binomial coefficient
- 🙂 codeforces/844-B
- 🥵 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)
- multi-combinations
- 😳 codeforces/630-G → C(n+5-1,5) * C(n+3-1,3)
- binomial coefficient
- ad-hoc
- 🙂 uva/10812
- 🙂 uva/11875
- 🙂 codeforces/16-C
- 🙂 uva/10110:
check if the number of divisors of n is odd→ check if n is a perfect square - 🙂 uva/10346
- 🙂 codeforces/1042-A
- 😳 codeforces/573-A
- 🙂 spoj/BISHOPS:
how many bishops can be placed on a n x n chessboard without threatening each other? - 🙂 uva/11723
- 🙂 uva/12791
- arithmetic progression
- sequences
- finding pattern
- 🥵 uva/11718 → compute K * N^(K-1) * sumA using fast power mod
- 😳 uva/10161
- 🙂 codeforces/1324-A
- 🙂 spoj/EIGHTS
- 😳 codeforces/1092-D1 → remove adjacent ones whose absolute difference is even (using a stack)
- 🙂 codeforces/1221-C
- 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 - prime numbers
- 🙂 spoj/PRIONPRI:
prime checking - sieve of eratosthenes
- 🙂 spoj/AMR11E:
print the n-th number that has at least 3 distinct prime factors→ use modified sieve - 🙂 codeforces/230-B:
check if a large n has exactily three distinct positive divisors→ check if sqrt(n) is prime - 😳 codeforces/576-A
- 😳 spoj/PRIME1:
print all primes p in [m .. n], 0 <= m <= n <= 10^9, n-m <= 10^5→ sieve + prime checking - 😳 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:
- 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/10139:
do n! is divisible by m?→ check if the prime factors of m are contained in the prime factors of n! - 🙂 uva/10042
- 🥵 uri/2661:
- 🙂 spoj/PRIONPRI:
- greatest common divisor (GCD)
- 😳 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/822-A
- 🙂 codeforces/854-A:
given n, determine maximum possible proper (a < b) and irreducible fraction a/b such that a+b == n
- 😳 codeforces/75-C:
- module arithmetic
- 😳 uri/2291:
- game theory
- minimax
- 😳 uva/10111:
given a state of a tic tac toe board, check if X will win independent of the O movement→ minimax + memo + backtracking - 😳 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 - optimized
- 🥵 uva/847:
multiplication game→ note that if Stan always multiply by 9 and Ollie by 2, it's still an optimal solution
- 🥵 uva/847:
- 😳 uva/10111:
- minimax
- 🙂 uva/10943
- 😳 uva/10721
- 🙂 uva/10337
- 🙂 uva/10003
- 😳 codeforces/166-E
- 🙂 spoj/TRT → don't memoize the current day
- 🙂 uva/11450
- 😳 codeforces/1061-C → use space saving + all divisors in O(sqrt(n)) to optimize
- 😳 uva/10651 → use bitmasks
- 0-1 knapsack
- 🙂 spoj/SCUBADIV
- 🙂 uri/2498
- 🙂 uva/990:
with recovering - 😳 uri/1487
- 🙂 spoj/KNAPSACK
- 😳 spoj/FISHER:
get the (min) total value and total weight of the optimal knapsack - 😳 uva/10261:
as if there were 2 knapsacks to fill at the same time; with recovering
- 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
- 🙂 spoj/IOIPALIN:
- 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
- 😳 uri/1707:
- coin change
- 😳 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
- 🙂 codeforces/189-A
- 😳 uva/166:
- 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 - 🙂 uva/624:
print the subset of A with the max sum k, k <= K - with repetition
- 🙂 uri/1203:
- traveling salesman problem (TSP)
- longest increasing subsequence (LIS)
- max 1D range sum
- 😳 uva/787:
max 1D range product query→ compute for each sub-range without 0 - kadane
- 🙂 codeforces/1285-B
- 🙂 uva/12640:
find the max range sum considering the possibility of a sub-range of length 0 - 🙂 uva/10684
- 🙂 spoj/MAXSUMSU
- 😳 uva/787:
- max 2D range sum
- traversal
- 🙂 uva/11831 → consider grid as an implicit graph and walk through it, or just rotate the robot, for each received instruction
- 😳 uva/11906 → consider grid as an implicit graph and walk through it avoiding redundant positions (nr, nc)
- 😳 code-jam/2020-1A-pascal-walk-TLE
- bipartite checking
- bridges or articulation points
- 🥵 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
- 🥵 uva/12363:
- flood fill
- topological sorting
- strongly connected components (SCC)
- 😳 uva/11504 → count the number of SCCs without incoming edge from a vertex of another SCC
- depth-first search (DFS)
- 😳 uri/2965
- edge classification
- 🙂 codeforces/510-B:
check if a given implicit undirected graph has a cycle of length >= 4 - 🙂 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:
- specials
- 😳 uva/12442:
given a graph with all vertices with out-degree 1, find the vertice that reaches the most vertices - directed acyclic graph (DAG)
- 🙂 uva/988:
counting paths from 0 to V-1
- 🙂 uva/988:
- tree
- 🙂 spoj/LABYR1:
compute the diameter of a given implicit tree - 🙂 codeforces/115-A:
given a forest, find the length of the longest path - 😳 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
- 🙂 spoj/LABYR1:
- 😳 uva/12442:
- shortest path
- all-pairs
- 🙂 uri/2372
- single-source
- unweighted graph
- 😳 uva/12797 → apply a BFS for each subset of letters possible (only 2^10) using bitmask
- weighted graph
- 😳 uva/11833 → build the graph already with the given constraints
- 🥵 live-archive/3652:
dijkstra on a given implicit graph as a 2D grid - 🥵 uva/11367 → find the shortest path on state-space graph, where each vertex represent a city and a level of car fuel
- 😳 uva/10806:
find the global shortest path from 0 to V-1 (round trip), without repeting edges
- 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)
- 😳 at-coder/ABC137-E:
- unweighted graph
- all-pairs
- minimum spanning tree (MST)
- 🙂 codeforces/1220-A
- 🙂 uri/2968
- 🙂 spoj/SBANK
- 🙂 codeforces/37-A
- 🙂 uva/10141
- 🙂 uri/3024
- 🥵 uri/1368
- 🙂 uri/2242
- 🙂 codeforces/151-A
- 🙂 code-jam/2019-QR-foregone-solution
- 🙂 uri/2963
- 🙂 uri/2879
- 🙂 spoj/EC_CONB
- 🙂 uva/12798
- 🙂 code-jam/2020-1C-overexcited-fan
- 🙂 uri/2884
- 🙂 uva/12015
- 🙂 spoj/ADAQUEUE
- 🙂 uva/11799
- 🙂 codeforces/1285-A
- implementation
- 🙂 uri/1215
- 🙂 codeforces/158-C
- 🙂 uva/105:
skyline - 😳 uri/2971
- 😳 codeforces/1296-C → maps each position of the robot with the string index, and check if a new position has already been mapped before
- 🙂 uri/1975
- 🙂 codeforces/1284-A
- 😳 codeforces/1254-A
- 🙂 codeforces/492-B
- 🙂 code-jam/2020-QR-vestigium
- 😳 codeforces/519-C
- 🙂 codeforces/811-B
- 🙂 uri/1261
- 🙂 uri/1763
- 🙂 codeforces/81-A
- 🙂 codeforces/373-A
- 🙂 uri/1260
- 🙂 codeforces/110-A
- 🙂 codeforces/266-A
- 🙂 uri/2593
- 🙂 spoj/GNY07D
- 🙂 spoj/BUSYMAN:
compute the maximum number of activities (each with start and end times) that you can do without overlapping them (one at a time)→ sort the activites by increasing end time - 🙂 codeforces/545-D
- 🙂 spoj/GERGOVIA
- 🙂 code-jam/2020-QR-parenting-partnering-returns
- 🙂 codeforces/1257-A
- 🙂 codeforces/1324-C → note that it's unnecessary jump to the left, so to minimize d, just jump between the nearest 'R' cells
- 😳 code-jam/2020-1A-pattern-matching
- 🙂 codeforces/1092-B
- 🙂 codeforces/1324-B:
given a sequence of integers, is there a subsequence palindrome of size 3?→ check if there are two equal non-adjacent numbers using brute force - 🙂 codeforces/984-A
- 🙂 uva/10954:
add all - 🙂 spoj/SNGINT:
given an integer n, find the smallest positive integer m > 0 such that the product of digits of m equals n - 😳 codeforces/1237-C2 → sort the points, remove pairs with equal x and y first, then pairs with equal x and finally the rest
- 😳 codeforces/204-B:
given the two-sided values of N cards, what is the minimum number of turns in the cards so that at least half of them are the same front?; they are initially facing upwards - 🙂 codeforces/275-C
- 🙂 spoj/CADYDIST
- 🙂 code-jam/2020-QR-nesting-depth
- interval covering
- 😳 uva/10382 → reduce the problem using pythagoras to one line
- bipartite matching
- restrict coin change
- fast longest increasing subsequence (LIS)
- 😳 uva/481
- loading balance
- iterative
- 🙂 uva/12801
- 🙂 uva/10360
- 🙂 codeforces/633-A:
check if a diophantine equation has positive solution - 🙂 uva/628
- 🙂 uva/725
- 😳 uva/12792:
simulation→ note that if you 'watch' a unique card, the full deck will become sorted as soon as this card reaches its original position - all permutations
- 🙂 uva/750
- all subsets
- 🙂 uva/12455 → use bitmasks
- recursive backtracking
- 🙂 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 - 😳 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 - 🙂 spoj/MKJUMPS:
given an unweighted implicit graph, count the longest possible path→ DFS + 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 - sudoku
- 🙂 uva/989
- pruned permutations
- n-queens
- 😳 uva/11195 → use bitmasks
- 🙂 uva/10344:
- 😳 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