Access my public notebook, a Notion workspace where I do my notes while studying and coding general-purpose algorithms. The book I recommend for studying is "Competitive Programming 3: The new lower bound of programming contests" by Steven Halim.
Feel free to follow my progress on my main online judge profiles:
- #greedy
- #dynamic-programming
- #ad-hoc
- #divide-&-conquer
- #techniques
- #searching
- #math
- #graphs
- #brute-force
- #computational-geometry
- iterative
- 📗 icpc/2014-01-uva-12801
- 📗 uva/725
- 📗 uva/10360
- 📗 uva/628
- 📙 icpc/2014-01-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 subsets
- 📗 uva/12455 → use bitmasks
- all permutations
- 📗 uva/750
- 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 - 📗 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 - 📙 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 - pruned permutations
- sudoku
- 📗 uva/989
- n-queens
- 📙 uva/11195 → use bitmasks
- 📗 uva/10344:
- specials
- tree traversal
- 📗 spoj/ONP:
transform the algebraic expression with brackets into reverse polish notation (RPN)→ consider the given expression as the in-order traversal in a binary tree, then print post-order traversal recursively without building the tree
- 📗 spoj/ONP:
- tree traversal
- traversal
- 📗 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
- 📙 uva/12442:
given a graph with all vertices with out-degree 1, find the vertice that reaches the most vertices - 📙 uva/11906 → consider grid as an implicit graph and walk through it avoiding redundant positions (nr, nc)
- flood fill
- bipartite checking
- strongly connected components (SCC)
- 📙 uva/11504:
count the number of SCCs without incoming edge from a vertex of another SCC
- 📙 uva/11504:
- topological sorting
- bridges and articulation points
- 📗 uva/796
- depth-first search (DFS)
- 📗 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 - 📙 icpc/2019-01-uri-2965
- 📗 codeforces/104-C:
- shortest path
- single-source
- unweighted graph
- 📙 icpc/2014-01-uva-12797 → apply a BFS for each subset of letters possible (only 2^10) using bitmask
- weighted graph
- unweighted graph
- all-pairs
- 📗 uri/2372
- single-source
- minimum spanning tree (MST)
- ad-hoc
- 📗 uva/10812
- 📗 uva/11875
- 📗 icpc/2014-01-uva-12791
- 📗 uva/10346
- 📗 uva/11723
- 📗 codeforces/1042-A
- sequences
- arithmetic progression
- finding pattern
- 📙 uva/10161
- 📗 spoj/EIGHTS
- 📗 codeforces/1324-A
- 📙 codeforces/1092-D1 → remove adjacent ones whose absolute difference is even (using a stack)
- 📗 codeforces/1221-C
- 📕 uva/11718 → compute K * N^(K-1) * sumA using fast power mod
- 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 - greatest common divisor (GCD)
- 📗 codeforces/822-A
- 📗 codeforces/854-A:
given n, determine maximum possible proper (a < b) and irreducible fraction a/b such that a+b == n
- 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 - 📙 codeforces/576-A
- 📗 spoj/AMR11E:
print the n-th number that has at least 3 distinct prime factors→ use modified sieve - 📙 spoj/PRIME1:
print all primes p in [m .. n], 0 <= m <= n <= 10^9, n-m <= 10^5→ sieve + prime checking
- 📙 uva/10539:
- 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!
- 📕 uri/2661:
- 📗 spoj/PRIONPRI:
- module arithmetic
- 📗 uva/10176:
is a given binary number of 100 digits divisible by 131071?
- 📗 uva/10176:
- 📙 uri/2291:
- combinatorics
- fibonacci numbers
- 📙 uva/10334 → compute (n+2)-th fibonnaci number
- binomial coefficient
- 📗 codeforces/844-B
- 📕 icpc/2019-01-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)
- fibonacci numbers
- 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
- segment tree
- 📗 codeforces/339-D
- lazy propagation
- binary search
- 📗 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] - 📙 codeforces/1284-B
- 📙 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/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 - on answer
- 📙 icpc/2019-01-uri-2973
- 📙 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 - 📙 codeforces/1223-C
- 📕 codeforces/460-C
- 📙 uva/12097
- 📗 spoj/PAIRS1:
- two pointers
- 📙 codeforces/279-B
- 📕 codeforces/1041-D
- 📗 codeforces/381-A
- 📙 uva/967:
pope - 📙 codeforces/676-C
- 📗 codeforces/6-C
- 📙 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
- 📗 codeforces/1220-A
- 📗 code-jam/2020-1C-overexcited-fan
- 📗 spoj/ADAQUEUE
- 📗 icpc/2019-01-uri-2963
- 📗 uri/2242
- 📗 icpc/2019-02-uri-3024
- 📗 codeforces/37-A
- 📗 icpc/2019-01-uri-2968
- 📗 spoj/SBANK
- 📗 spoj/EC_CONB
- 📗 codeforces/1285-A
- 📗 uva/12015
- 📗 uri/2879
- 📗 codeforces/151-A
- 📗 icpc/2014-01-uva-12798
- 📕 uri/1368
- 📗 uri/2884
- 📗 uva/10141
- 📗 code-jam/2019-QR-foregone-solution
- 📗 uva/11799
- implementation
- 📗 codeforces/266-A
- 📗 uri/1261
- 📗 uri/1763
- 📗 uri/1260
- 📗 uri/2593
- 📗 spoj/GNY07D
- 📙 icpc/2019-01-uri-2971
- 📗 codeforces/158-C
- 📗 codeforces/373-A
- 📗 uri/1975
- 📙 codeforces/1254-A
- 📗 uri/1215
- 📙 codeforces/1296-C → maps each position of the robot with the string index, and check if a new position has already been mapped before
- 📗 codeforces/1284-A
- 📗 codeforces/811-B
- 📙 codeforces/519-C
- 📗 codeforces/81-A
- 📗 codeforces/492-B
- 📗 code-jam/2020-QR-vestigium
- 📗 codeforces/110-A
- 📙 codeforces/1061-C → use space saving + all divisors in O(sqrt(n)) to optimize
- 📗 uva/10943
- 📙 uva/10721
- 📗 uva/10003
- 📗 uva/10337
- 📗 uva/11450
- 📙 uva/10651 → use bitmasks
- 📙 codeforces/166-E
- 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:
- longest increasing subsequence (LIS)
- coin change (CC)
- max 2D range sum
- traveling salesman problem (TSP)
- 0-1 knapsack
- 📙 uri/1487
- 📗 spoj/KNAPSACK
- 📗 spoj/SCUBADIV
- 📗 uri/2498
- subset sum
- max 1D range sum
- 📙 uva/787:
max 1D range product query→ compute for each sub-range without 0 - kadane
- 📗 uva/12640:
find the max range sum considering the possibility of a sub-range of length 0 - 📗 uva/10684
- 📗 codeforces/1285-B
- 📗 spoj/MAXSUMSU
- 📗 uva/12640:
- 📙 uva/787:
- longest common subsequence (LCS)
- 📗 spoj/ADASEQEN
- 📗 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
- 📙 code-jam/2020-1A-pattern-matching → note that only the prefix and suffix constraints matter
- 📗 codeforces/275-C
- 📗 spoj/GERGOVIA
- 📗 spoj/SNGINT:
given an integer n, find the smallest positive integer m > 0 such that the product of digits of m equals n - 📗 code-jam/2020-QR-parenting-partnering-returns
- 📗 codeforces/545-D
- 📗 codeforces/1092-B
- 📙 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/1257-A
- 📗 uva/10954:
add all - 📗 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/1324-C → note that it's unnecessary jump to the left, so to minimize d, just jump between the nearest 'R' cells
- 📗 spoj/CADYDIST
- 📗 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/984-A
- 📗 code-jam/2020-QR-nesting-depth
- 📙 codeforces/1237-C2 → sort the points, remove pairs with equal x and y first, then pairs with equal x and finally the rest
- loading balance
- interval covering
- 📙 uva/10382:
reduce the problem using pythagoras to one line
- 📙 uva/10382:
- fast longest increasing subsequence (LIS)
- 📙 uva/481
- bipartite matching