LegendaryNewbie_'s blog

AtCoder's Problem ABC042 D. Iroha and a Grid

By LegendaryNewbie_, history, 5 years ago, In English

Can anyone please help me explaining the solution of this problem? I don't know how to solve this problem. Statement: We have a grid with H rows and W columns, Iroha is now standing in the top-left cell. She will repeat going right or down to the adjacent cell, until she reaches the bottom-right cell.But she cannot enter the cells in the intersection of the bottom A rows and the leftmost B columns(that is there are A x B forbidden cells).Find the number of ways she can travel to the bottom-right cell. Problem Link

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Denote by $$$L[k]$$$ the number of ways to go $$$(0, 0) \to (k, B - 1)$$$ and by $$$R[k]$$$ the number of ways to go $$$(k, B) \to (H - 1, W - 1)$$$. The answer is then $$$\sum L[k] \cdot R[k]$$$. Can you figure out formulas to calculate $$$L[k]$$$ and $$$R[k]$$$?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hii, what does 'k' stands for? We need to use binomial coefficient right?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Did you read this part $$$(0, 0) \to (k, B - 1)$$$?

      → Reply