PROBLEM LINK:
DIFFICULTY
HARD
PREREQUISITES
Elementary Number Theory, Gaussian Elimination, Dynamic Programming, Cycle Detection
PROBLEM
A knight can make two kinds of moves from (u, v)
- (u + Ax, v + Ay)
- (u + Bx, v + By)
You wish to move the knight from (0, 0) to (X, Y).
You are given a set of K points P = { P1, P2 …, Pk} which should not be touched by the knight.
In how many ways can the knight be moved to (X, Y) without touching any of the P points?
EXPLANATION
First, let us forget about the fact that the answer can be very large and has to be found modulo 1000000007. We will come to this later and see how this affects the overall solution to this problem.
This problem has overall 2 cases.
CASE I: A and B are linearly independent
Since A and B are independent, we can do a linear mapping of all the points to a space defined by the orthogonal vectors A and B.
This means that we replace each point (u, v) with (p, q) such that
p*Ax + q*Bx = u
p*Ay + q*By = v
- If (X, Y) cannot transform to an integer (x’, y’), then the number of ways to even reach (X, Y) is 0.
- If one of the points in P cannot transform to an integer (p, q), then that point will never be touched and can be ignored.
Now, we have some subset of P, lets call it Q, points which must be avoided on the way to (x’, y’). But, the step in this space, instead of A and B, is (0, 1) or (1, 0).
The number of ways of going from (0, 0) to (p, q) when step is (1, 0) or (0, 1) is
ways(p, q) = p+qCp
The case of ignoring the Q points can be solved in several ways
Approach 1. Inclusion Exclusion:
Sort Q, the subset of mapped forbidden points
totalWays = ways(0, dest)
for each subset S of Q
cWays = 1
visit points in S using i = 2 to S.size, in order of appearance in Q
cWays *= ways(S[i] - S[i-1])
sign = (S.size % 2 == 1) ? -1 : 1
totalWays += sign * cWays
Complexity: O(K*2K)
Approach 2. Gaussian Elimination:
Number of ways of reaching destination not touching any Q = Total number of ways of reaching destination - number of ways of reaching destination touching at least 1 point Q
Number of ways of reaching destination touching at least 1 point Q = for i = 1 to Q.size, ways += x(i) * ways(i, dest)
Where x(i) is the number of ways of reaching i’th point without touching any other point.
Let Q.size be Qc.
Now,
ways(0, j) = for i = 1 to Qc, ways += x(i) * ways(i, j)
for all j which are also in Q.
Thus we have Qc equations for Qc variables.
ways(0, 1) = x(1)*ways(1, 1) + x(2)*ways(2, 1) ... + x(Qc)*ways(Qc, 1) ways(0, 2) = x(1)*ways(1, 2) + x(2)*ways(2, 2) ... + x(Qc)*ways(Qc, 2) ways(0, 3) = x(1)*ways(1, 3) + x(2)*ways(2, 3) ... + x(Qc)*ways(Qc, 3) ... ways(0, Qc) = x(1)*ways(1, Qc) + x(2)*ways(2, Qc) ... + x(Qc)*ways(Qc, Qc)
This can be solved using Gaussian Elimination for x in O(N3) time.
Once we have x we can find the number of ways of reaching (x’, y’) while touching at least 1 point Q… and hence, the number of ways of reaching (x’, y’) without touching any Q.
Approach 3: Sorting
By now we know that the points in Q are ordered. Thus,
Sort Q
x(1) = ways(0, 1)
for i = 2 to Q.size
x(i) = ways(0, i)
for j = 1 to i-1
x(i) -= x(j) * ways(j, i)
Thus, we have found x as defined above, in O(N2) time.
Thus this case is solved.
CASE II: A and B are linearly dependent
There are a large number of corner cases to consider carefully.
- A = (0, 0) and B = (0, 0) then answer is X == (0, 0) ? -1 : 0
- If Ax and Bx are 0 and X is not 0, the answer is 0
- If Ay and By are 0 and Y is not 0, the answer is 0
Let Gx be the gcd of Ax and Bx
and, Gy be the gcd of Ay and By
- If X is not divisible by GX or Y is not divisible by GY, the answer is 0
We can ignore all the forbidden points which cannot be reached based on the rules above.
Now, we can scale all X co-ordinates by GX and all Y co-ordinates by GY. By all, we mean we scale only those points that are reachable.
Because of the linear dependence of A and B, we know that both the co-ordinates scale the same way when considering A or B. Thus, we can perform a DP on only the x-coordinate to find the number of ways of reaching X and we know that we will get a result for Y equivalently.
We can perform bellman-form + dynamic programming to compute the number of paths that lead up to the transformed destination - which was originally (x’, y’). We do a bellman-ford twice to catch any possible cycles.
If there is a cycle, then there are infinite number of solutions. Otherwise we have the answer by the DP.
For more clarity regarding this case, refer to the tester’s solution.
All that number theory
Throughout this problem there is requirement of finding Binomial Coefficients modulo 1000000007.
Also, we need to perform a Gaussian Elimination in a Field of 1000000007, which basically means that all divisions performed in the gauss elimination are performed via taking multiplicative modular inverses.
Binomial coefficients can be found by precomputing the factorials modulo 1000000007 and precomputing the inverse factorials modulo 1000000007. Since the largest binomial coefficient we want is not much, we can do the following
inv = Array[10000]
for i = 2 to 10000
inv[i] = modulo_power(i, 1000000005)
fact = Array[10000]
ifact = Array[10000]
fact[1] = ifact[1] = 1
for i = 2 to 10000
fact[i] = fact[i-1] * i mod 1000000007
ifact[i] = ifact[i-1] * inv[i] mod 1000000007
Where fact is the factorials modulo 1000000007 and ifact is the inverse factorials modulo 1000000007.
Now,
binomial(n,r) = fact[n]*ifact[r]*ifact[n-r] mod 1000000007
SETTERS SOLUTION
Can be found here (Link is broken. Will be fixing soon.)
TESTERS SOLUTION
Can be found here
