Guys, can someone explain me the solution of this problem? I couldn't understand fully.
№ | Пользователь | Рейтинг |
---|---|---|
1 | jiangly | 3640 |
2 | Benq | 3593 |
3 | tourist | 3572 |
4 | orzdevinwang | 3561 |
5 | cnnfls_csy | 3539 |
6 | ecnerwala | 3534 |
7 | Radewoosh | 3532 |
8 | gyh20 | 3447 |
9 | Rebelz | 3409 |
10 | Geothermal | 3408 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 173 |
2 | adamant | 164 |
3 | awoo | 161 |
4 | TheScrasse | 160 |
5 | nor | 159 |
6 | maroonrk | 156 |
7 | SecondThread | 152 |
8 | pajenegod | 146 |
9 | BledDest | 144 |
10 | Um_nik | 143 |
Название |
---|
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.
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 differenti
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 inO(logMOD)
time for each call. The total time complexity should beO(H+WlogMOD)
.Maybe there are solutions using inclusion-exclusion principal. Here are some problems in Atcoder relate to it. Grid 1 Grid 2