coderdhanraj's blog

A Combinatorics Task
By coderdhanraj, 2 years ago, In English

Hey Everyone,

I am stuck on the following problem. Need help!

Problem: Unique Paths (Hard Version)

You are given a grid consisting of $$$n$$$ rows and $$$m$$$ columns. There are two types of cells good and bad. You can't move in a bad cell. There are $$$k$$$ bad cells in the grid.

You can move only in the right and down direction only. i.e. if you are on cell $$$(i, j)$$$, so you can move to $$$(i + 1, j)$$$ and $$$(i, j + 1)$$$.

You are asked to find the no of ways or no of unique paths to reach cell $$$(n, m)$$$ from cell $$$(1, 1)$$$. As the answer can be large print it modulo $$${10^9 + 7}$$$.

Constraints:

$$${1 \le n, m\le 10^5}$$$, $$${0 \le k \le min(10^3, n * m).}$$$

Sample Example

n = 5, m = 5, k = 2.

bad cells = (1, 2), (3, 3).

answer = 17.

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

Comments Comments (4)
| Write comment?
»
2 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Idea: Can you perhaps remove the amount of "bad routes" from all possible routes? How can this be done?

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

A similar problem: https://my.newtonschool.co/playground/code/dhw2vt31pdfp/ (Newton School July Contest Problem D)

→ Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Hi,

This is an identical problem from the AtCoder Educational DP contest, although with lower limits of $$$k$$$ (in this problem it is $$$3000$$$, while in your problem it is $$$10^6$$$).

Update, your problem constraints have been fixed to $$$10^3$$$, so this is basically an identical problem now.

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

    Thanks for your reply. I updated the constraints. Previous constraints were incorrect!

    → Reply