I have a grid containing $$$10^6$$$ rows and $$$10^6$$$ columns. I also have coordinates of $$$N$$$ cells of this grid each of which has either a red ball, or a blue ball, or both (one ball of each color). When a person visits a cell, he/she can collect all the balls from that cell. The target is to reach the bottom-right cell from the top-left cell by collecting at least one ball of each color. From one cell, it's only possible to visit the cell on its right or the cell below it. Upper bound of $$$N$$$ is $$$1000$$$.
The problem is to find the number of different paths that has at least one cell with blue ball and at least one cell with red ball in it. Two paths are different if there is at least one cell that belongs to only one of them.
How can I solve this efficiently?
Inclusion-exclusion?
Do you know how to solve the same problem except we have obstacles instead of balls? There is a problem: 559C - Gerald and Giant Chess on CF which is exactly that. Read here or here for a solution.
So, how to turn the problem with obstacles to a problem with paths? The answer to your problem is (# of paths) — (# of paths with obstacles at blue balls) — (# of paths with obstacles at red balls) + (# of paths with obstacles at all balls). Can you see why?