CF2041G Grid Game

Claire loves drawing lines. She receives a sheet of paper with an $ n \times n $ grid and begins drawing "lines" on it. Well—the concept of a "line" here is not what we usually think of. Claire refers each line to be a set of consecutive vertical grid cells. When she draws a line, these cells are all covered with black ink. Initially, all the cells are white, and drawing lines turns some of them black. After drawing a few lines, Claire wonders: how many ways she can color an additional white cell black so that the remaining white cells do not form a single connected component. Two cells are directly connected if they share an edge. Two cells $ x $ and $ y $ are indirectly connected if there exists a sequence of cells $ c_0, c_1, \ldots, c_k $ with $ k > 1 $ such that $ c_0 = x $ , $ c_k = y $ , and for every $ i \in \{1, 2, \ldots, k\} $ the cells $ c_i $ and $ c_{i-1} $ are directly connected. A set of cells forms a single connected component if each pair of cells in the set is either directly or indirectly connected. The grid has $ n $ rows and $ n $ columns, both indexed from $ 1 $ to $ n $ . Claire will draw $ q $ lines. The $ i $ -th line is drawn in the $ y_i $ -th column, from the $ s_i $ -th row to the $ f_i $ -th row, where $ s_i \leq f_i $ for each $ i \in \{1, 2, \ldots, q\} $ . Note that the cells that are passed by at least one of the $ q $ lines are colored black. The following figure shows an example of a $ 20\times 20 $ grid with $ q=67 $ lines. The grid cells marked with red star symbols refer to the cells such that, if Claire colors that cell black, all white cells no longer form a single connected component. You may assume that, after drawing the $ q $ lines, the remaining white cells form a single connected component with at least three white cells.

N/A

N/A