I am Tomasz Idziaszek and this is the place where I collect my writings on algorithms in competitive programming. I have started in March 2018 and I plan to publish a new article every three months or so. I also invite you to check out the list of books I have edited and written.
The notes
Dynamic programming on trees with minimal memory
A detailed analysis how to solve a classical dynamic programming problem on a tree, but using as little memory as possible. Explains inefficiencies of a standard approach (vectors, recursion), shows various representations of trees in the memory (with clever ways to compress, but still allowing to traverse them), and some tricks to optimize DP calculations.
Published in March 2018
Survey of knapsack problems
Description of various variants of the knapsack problem solved using mostly dynamic programming. Includes 0-1, unbounded and bounded knapsacks, as well as knapsacks with items of different costs, items of limited life time, items with dependencies etc.
Published in May 2018 (work in progress; the first part available)
Counting perfect matchings in grids and planar graphs
Description of algorithms for calculating perfect matchings in certain classes of graphs. Discusses hardness of this problem for general graphs due to calculation of a permanent, and shows two ingenious algorithms which reduces this problem for grids and planar graphs to calculation of a determinant of cleverly modified matrices.
Published in September 2018 (work in progress; the first part available)
Increasing subsequences and related problems
Description of algorithms for various problems related to finding increasing subsequences in a sequence of integers.
Published in December 2018 (work in progress; the first part available)
Maximum-subarray and related problems
Description of algorithms for finding a contiguous subarray of the largest sum, within a given array of numbers. Discusses various classic algorithms, as well as not so classic ones which solve a variant in which we find several disjoint subarrays.
Published in March 2019 (work in progress; the first part available)
Algorithms for arithmetic in Fibonacci and golden ratio representations
Discussion of alternative ways of representing integers using Fibonacci numbers and positional numeral system with irrational base equal to golden ratio. Includes efficient algorithms for arithmetic operations performed directly on these representations.
Published in July 2019 (work in progress; the first part available)
Solutions to problems from IOI 2018
Detailed solutions to all six problems from the International Olympiad in Informatics 2018, hosted in Tsukuba, Japan.
Published in December 2019