### Kazimov's blog

By Kazimov, history, 4 weeks ago,

Guys, can someone explain me the solution of this problem? I couldn't understand fully.

Problem D

• +1

 » 4 weeks ago, # | ← Rev. 29 →   0 This problem is related to the problem of finding the number of routes between the top-left cell $(1,1)$ and the right-bottom cell $(H,W)$ of a rectangular grid with $H$ rows and $W$ columns, where the move allowed from cell $(x,y)$ is either to the right adjacent cell $(x,y+1)$ or to the down adjacent cell $(x+1,y)$. It is well-known that the total number of routes on such grid with no forbidden cells is $\binom{(H-1)+(W-1)}{H-1} = \binom{(H-1)+(W-1)}{W-1}$ This result may be used to solve the problem when the bottom-left corner sub-grid with $A$ rows and $B$ columns which contains $A\times B$ cells is forbidden by dividing the problem into mutually disjoint sub-problems such that the total number of routes is the sum of the total number of routes in each disjoint sub-problem. For example, any route between the top-left cell and the bottom-right cell passes through exactly one cell on the straight line $x+y = c$. A possible application of this idea is to select one of these lines, let it be the straight line $x+y = c$ which passes through the top-right corner cell of the forbidden sub-grid $(H-A+1,B)$, and define the sub-problem as to count the number of routes that pass through cell $(x,y)$ which lies on such line. By definition, $y = (H-A+1)+B-x$. The solution of this sub-problem is the product of the number of routes between cells $(1,1)$ and $(x,y)$ in the top-left sub-grid with $x$ rows and $y$ columns times the number of routes between cell $(x,y)$ and cell $(H,W)$ in the lower-right sub-grid with $H-x+1$ rows and $W-y+1$ columns, where both sub-grids do not contain forbidden cells. Therefore, the answer to this sub-problem can be expressed using the aforementioned result as follows.$f(x) = \binom{(x-1)+(y-1)}{x-1} \times \binom{(H-x)+(W-y)}{H-x} = \binom{(H-A)+B-1}{x-1} \times \binom{A+(W-B)-1}{H-x}$where $m \le x \le H-A$ and $m = \max((H-A)-(W-B)+1,1)$Therefore, the answer to the problem can be expressed as follows.$\sum\limits_{x = m}^{H-A} f(x)$Note that the value of $x$ for any cell on the selected straight line cannot be less than $(H-A)-(W-B)+1$, as $y = W$ at the intersection point with the line $x = (H-A)-(W-B)+1$. Points on the selected straight line with $x$ less than such value lie outside the $H\times W$ grid.
 » 4 weeks ago, # |   0 Use the picture in the editorial. Take the grid as 0-indexed. We want to go to (H-A-1,i) from (0,0), and there are $C_{H-A-1+i}^{i}$ ways to do it. Then we go one step down to (H-A,i), one way to do it. Finally go from (H-A,i) to (H-1,W-1), $C_{A-1+W-i-1}^{W-X-1}$ ways to do it. Note that choosing different i guarantee the paths to be different. So the final answer is: $\sum_{i=b}^{W-1}C_{H-A-1+i}^{i} * C_{A-1+W-i-1}^{W-X-1}$Using this formula, we can implement it by enumerating i, and precalculate factorial to calculate combinations in O(logMOD) time for each call. The total time complexity should be O(H+WlogMOD).Maybe there are solutions using inclusion-exclusion principal. Here are some problems in Atcoder relate to it. Grid 1 Grid 2