Kazimov's blog

By Kazimov, history, 4 weeks ago, In English

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

Problem D

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
4 weeks ago, # |
Rev. 29   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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