Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags

Problem Statement:

Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags
Summary:
Given an integer matrix with size m x n with m <= 10, n <= 10^5, find the number of connected components in segment [l, r] of the matrix (i.e. rectangle (0, l) -> (m-1, r)). Two cells belong to the same connected component if they are adjacent (share the same edge) and have the same value.
There are q <= 10^5 such queries.

Solution:
A cool problem which can be solved using Segment Tree. This is made possible by the following observation: Consider two adjacent segments [l, m] and [m+1, r]. If we know the number of components on each segment, then we can iterate along the cells where the two segments meet to see if we can combine any adjacent components.

Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Problem Statement:
Codeforces Round #356 (Div. 2) E / (Div. 1) C - Bear and Square Grid

Summary:
A \(N \times N\) grid where a cell is either empty or not, has the following properties: an empty cell is connected to its up, left, right, or bottom neighbour if its neighbour is also an empty cell. Compute the largest possible connected component in the grid, if we can perform one operation of transforming a \(k \times k\) square in the grid into empty cells.