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.
Idea: Can you perhaps remove the amount of "bad routes" from all possible routes? How can this be done?
A similar problem: https://my.newtonschool.co/playground/code/dhw2vt31pdfp/ (Newton School July Contest Problem D)
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.
Thanks for your reply. I updated the constraints. Previous constraints were incorrect!