CF1738G Anti-Increasing Addicts

You are given an $ n \times n $ grid. We write $ (i, j) $ to denote the cell in the $ i $ -th row and $ j $ -th column. For each cell, you are told whether yon can delete it or not. Given an integer $ k $ , you are asked to delete exactly $ (n-k+1)^2 $ cells from the grid such that the following condition holds. - You cannot find $ k $ not deleted cells $ (x_1, y_1), (x_2, y_2), \dots, (x_k, y_k) $ that are strictly increasing, i.e., $ x_i < x_{i+1} $ and $ y_i < y_{i+1} $ for all $ 1 \leq i < k $ . Your task is to find a solution, or report that it is impossible.

N/A

N/A

For the first test case, you only have to delete cell $ (1, 1) $ . For the second test case, you could choose to delete cells $ (1,1) $ , $ (1,2) $ , $ (4,3) $ and $ (4,4) $ . For the third test case, it is no solution because the cells in the diagonal will always form a strictly increasing sequence of length $ 5 $ .