Competitive Programming

This unofficial editorial for AtCoder Beginner Contest 185 (ABC185) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

Codeforces Polygon supports the full process of creating a programming contest problem. This tutorial walks through statements, generators, validators, checkers, and tests using a sample problem and testlib.h.

What Is Codeforces Polygon?

According to Polygon itself, The mission of Polygon is to provide platform for creation of programming contest problems. Polygon supports the whole development cycle:

• Problem statement writing.
• Test data preparing (generators supported).
• Model solutions (including correct and wittingly incorrect).
• Judging.
• Automatic validation.

Read more →

This unofficial editorial for AtCoder Beginner Contest 179 (ABC179) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

This unofficial editorial for AtCoder Beginner Contest 178 (ABC178) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

Stress testing finds counterexamples by comparing a solution against a brute-force implementation on randomly generated inputs. This C++ tutorial covers test generators, comparison scripts, and custom checkers for problems with multiple valid answers.

I decided to write this article after watching the last screencast made by Errichto. To be more precise when he started making stress testing to find counter-test you can check that here. Errichto has a full video called How to test your solution in Competitive Programming, on Linux? I highly recommend you to check it, basically this article is the same but I am extending it to stress test solutions with multiple answers using a written checker, so let’s jump in.

Read more →

Combinatorial game theory helps determine whether a player can force a win. This tutorial introduces winning and losing positions, Nim, and the Sprague-Grundy theorem through competitive programming examples.

Combinatorial Games

The game is said to be Combinatorial if it satisfies the following conditions:

1. The game is played between two players, we will call them Alice and Bob.
2. The two players alternate playing, Alice plays first.
3. We can define two sets \(F_1\) and \(F_2\) of possible moves for each player, these sets are usually finite, based on these two sets we can classify combinatorial games into:
   • Combinatorial impartial games this happens when \(F_1 = F_2\), this means both players have the same options of moving from each position.
   • Combinatorial partizan games this happens when \(F_1\ne F_2\), this includes games like chess or checkers in which one player moves the white pieces, and the other player moves the black pieces.
4. There is an end position of the game, usually called the terminal position. In normal play rule the player making the last move wins the game, in misère play rules the player making the last move loses the game.
5. The game always ends after some finite number of moves.

Read more →

This tutorial connects maximum independent sets, minimum vertex covers, and maximum matching in bipartite graphs. It explains the ideas and implements matching with max flow and augmenting paths in C++.

Introduction to Independent Sets

The title contains a lot of terms that should be explained separately before we start, given an undirected graph \(G = (V, E)\) we define the following terms:

• Independent Set (IS) : Subset of nodes \(U \subseteq V\) with the following propriety: For any two nodes \(u, v \in U\) nodes \(u, v\) are not adjacent ( There is no direct edge between nodes \(u\) and \(v\) ).
• Maximal Independent Set (MIS) : An independent set is maximal if no node can be added to it without violating the independence condition.
• Maximum Independent Set (MaxIS) : An independent set of maximum cardinality.

Read more →

A monotonic queue finds the minimum in each sliding window in linear time. This tutorial develops a C++ implementation and extends it to minimums in two-dimensional submatrices.

Sliding Window Minimum: The Motivation Problem

Given \(n \times m\) matrix \((1 \le n, m \le 3*10^3)\) you have to calculate the sum of minimum numbers in all sub-matrices of size \(a\times b\) with top left corners in \((i, j)\) over all \(1 \le i \le n-a+1\) and \(1 \le j \le m-b+1\).

Read more →

This unofficial editorial for AtCoder Beginner Contest 185 (ABC185) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

Codeforces Polygon supports the full process of creating a programming contest problem. This tutorial walks through statements, generators, validators, checkers, and tests using a sample problem and testlib.h.

What Is Codeforces Polygon?

According to Polygon itself, The mission of Polygon is to provide platform for creation of programming contest problems. Polygon supports the whole development cycle:

• Problem statement writing.
• Test data preparing (generators supported).
• Model solutions (including correct and wittingly incorrect).
• Judging.
• Automatic validation.

Read more →

This unofficial editorial for AtCoder Beginner Contest 179 (ABC179) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

This unofficial editorial for AtCoder Beginner Contest 178 (ABC178) explains the approaches, time complexities, and C++ solutions for problems A through F.

Read more →

Stress testing finds counterexamples by comparing a solution against a brute-force implementation on randomly generated inputs. This C++ tutorial covers test generators, comparison scripts, and custom checkers for problems with multiple valid answers.

I decided to write this article after watching the last screencast made by Errichto. To be more precise when he started making stress testing to find counter-test you can check that here. Errichto has a full video called How to test your solution in Competitive Programming, on Linux? I highly recommend you to check it, basically this article is the same but I am extending it to stress test solutions with multiple answers using a written checker, so let’s jump in.

Read more →

Combinatorial game theory helps determine whether a player can force a win. This tutorial introduces winning and losing positions, Nim, and the Sprague-Grundy theorem through competitive programming examples.

Combinatorial Games

The game is said to be Combinatorial if it satisfies the following conditions:

1. The game is played between two players, we will call them Alice and Bob.
2. The two players alternate playing, Alice plays first.
3. We can define two sets \(F_1\) and \(F_2\) of possible moves for each player, these sets are usually finite, based on these two sets we can classify combinatorial games into:
   • Combinatorial impartial games this happens when \(F_1 = F_2\), this means both players have the same options of moving from each position.
   • Combinatorial partizan games this happens when \(F_1\ne F_2\), this includes games like chess or checkers in which one player moves the white pieces, and the other player moves the black pieces.
4. There is an end position of the game, usually called the terminal position. In normal play rule the player making the last move wins the game, in misère play rules the player making the last move loses the game.
5. The game always ends after some finite number of moves.

Read more →

This tutorial connects maximum independent sets, minimum vertex covers, and maximum matching in bipartite graphs. It explains the ideas and implements matching with max flow and augmenting paths in C++.

Introduction to Independent Sets

The title contains a lot of terms that should be explained separately before we start, given an undirected graph \(G = (V, E)\) we define the following terms:

• Independent Set (IS) : Subset of nodes \(U \subseteq V\) with the following propriety: For any two nodes \(u, v \in U\) nodes \(u, v\) are not adjacent ( There is no direct edge between nodes \(u\) and \(v\) ).
• Maximal Independent Set (MIS) : An independent set is maximal if no node can be added to it without violating the independence condition.
• Maximum Independent Set (MaxIS) : An independent set of maximum cardinality.

Read more →

A monotonic queue finds the minimum in each sliding window in linear time. This tutorial develops a C++ implementation and extends it to minimums in two-dimensional submatrices.

Sliding Window Minimum: The Motivation Problem

Given \(n \times m\) matrix \((1 \le n, m \le 3*10^3)\) you have to calculate the sum of minimum numbers in all sub-matrices of size \(a\times b\) with top left corners in \((i, j)\) over all \(1 \le i \le n-a+1\) and \(1 \le j \le m-b+1\).

Read more →