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 two months or so.

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)