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

# | User | Rating |
---|---|---|

1 | tourist | 3707 |

2 | Benq | 3672 |

3 | Radewoosh | 3627 |

4 | ksun48 | 3547 |

5 | Miracle03 | 3480 |

6 | ecnerwala | 3400 |

7 | peehs_moorhsum | 3384 |

8 | maroonrk | 3361 |

9 | sunset | 3338 |

10 | Um_nik | 3320 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 208 |

2 | Um_nik | 197 |

3 | YouKn0wWho | 192 |

4 | Errichto | 182 |

5 | sus | 181 |

6 | awoo | 180 |

7 | tourist | 175 |

8 | -is-this-fft- | 171 |

8 | SecondThread | 171 |

10 | Ashishgup | 170 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/25/2021 05:11:25 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 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