Algorithms

In bipartite graph theory and combinatorial optimization, one of the most fundamental questions is: When can every vertex on the left side of a bipartite graph be matched to a distinct vertex on the right side? While maximum flow and augmenting path algorithms (such as Hopcroft–Karp or Kuhn’s algorithm) allow us to compute a maximum matching for a fixed graph, Hall’s Marriage Theorem (proved by Philip Hall in 1935) gives a clean necessary and sufficient structural condition for a complete matching to exist. In competitive programming, Hall’s theorem often allows us to bypass building an explicit flow network altogether—transforming matching feasibility problems into algebraic inequalities, prefix/interval checks, or Sum Over Subsets Dynamic Programming (SOS DP). ...

Counting the number of valid bracket (parenthesis) sequences formed by $n$ opening brackets ( and $n$ closing brackets ) is one of the most celebrated problems in combinatorics and computer science. Whether you are parsing expressions, counting binary trees, or analyzing stack permutations, the answer is always the $n$-th Catalan number: \[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}. \]In this post, we will formally define valid bracket sequences, build geometric intuition using lattice paths (Dyck paths), and prove the closed-form formula using André’s Reflection Principle as well as the first-return recurrence relation. ...

In combinatorics and algorithm design, a classic family of counting problems asks: How many ways can we choose $k$ items from $n$ distinct types when repetition is allowed? Equivalently, how many integer solutions exist for a linear equation under various boundary constraints? This post breaks down the Stars and Bars (also known as the dividers or balls and urns) method across three canonical scenarios: Unbounded repetition ($x_i \ge 0$) At least one of each type ($x_i \ge 1$) Lower and upper bounds ($l_i \le x_i \le u_i$) via Inclusion-Exclusion and Dynamic Programming 1. Combinations with Repetition ($x_i \ge 0$) Problem Statement Suppose we have $n$ types of items and want to select $k$ items in total, where: ...