KNGHTMOV - Editorial

dynamic-programming
editorial
gauss-elim
number-theory
sep12

#1

PROBLEM LINK:

Practice
Contest

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* - 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* = modulo_power(i, 1000000005)
fact = Array[10000]
ifact = Array[10000]
fact[1] = ifact[1] = 1
for i = 2 to 10000
    fact* = fact[i-1] * i mod 1000000007
    ifact* = ifact[i-1] * inv* 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


#10

Hah, look at 1st line http://www.codechef.com/viewsolution/1314837


#11

@damians: I think codechef uses the SPOJ judge. So, SPOJ will have to update their servers.


#12

Hey guys. This Editorial was really difficult for me to write.

Please tell me if there are details missing and how I can improve this editorial!


#13

I think it’s well written. One detail: “1e7” is not a good abbreviation for 1000000007 because usually 1e7 means 10^7 (even in C++).

edit: I didn’t know the Gaussian elimination method for solving such a problem, it’s pretty nice.

edit2: Don’t know what do you mean by “Bellman Ford”, but it’s usually a shortest path finding algorithm, which doesn’t run very fast. So possibly u mean something different here.


#14

Yes, I mean the Bellman Ford.

Bellman Ford is is a shortest path algorithm, but also a generic technique for doing dynamic programming over paths.

Such as, in this case, we want to find the number of paths, not the shortest path. Thus the relaxation step for each edge simply happens to be

ways[tail] += ways[head] * ways(head, tail)

I will add details to the editorial in some time.


#15

Since in the case with non linearly independent moves the range of reachable points could be infinite, how did you determine the limits of the range for DP?


#16

@MarioYC As mentioned by Sumudu, you only need to consider a sufficient margin outside the range of values, since you will get cycles very quickly. I will try to verify from more solutions and update the editorial with these details.


#17

I am still stuck in handling only this case ,considering the graph becomes infinite.
For example : If we have two vectors (5,0) and (-3,0) and we have to reach some P(7,0) , and we have some points blocked( { (1,0) , (3,0) , (5,0) } .In this case, I don’t get how one can check for a cycle,using DFS in this (considering infinite number of reachable points).Can you please explain in this case, on how to limit the vertices??


#18

@javadecoder: First reduce the problem to points in a line. The point is to realize that you can’t have blocked cells beyond 500. So if you can reach any cell greater than 1000, you can do a infinite loop for sure, so you shouldn’t go further than these points.


#19

Maybe you could provide your submission id? It would be easier to find the test case you couldn’t beat with that info.


#20

@javadecoder “gcd” is (1, 0) so we are interested in all points of form (x, 0). Special vertices represent everything left of the blocked cells (so x < 1) and everything to the right (x > 5) (in addition to 5 “normal” vertices). If we can reach a special vertex, we can reach any point in that region. From the left we can reach x = 1…5. From the right we can reach x = 3…5. Two edges (-3 and +5) out of each normal unblocked vertex. In this case the answer is infinity since there is at least one path to the goal (L->2->R), and the goal is in one of the unbounded regions.


#21

Try this case: (your code gives fpe)

2 0 0

1 0 -1 0

Another case: (solution is 1 instead of -1)

3 3 3

3 3 -1 -1

-1 -1 2 2 6 6

Where are you doing the cycle detection mentioned in the editorial?


#22

Thanks a lot for the explanation ,now I get it :slight_smile: .The editorial mentions nothing of handling this case.


#23

I will add it to the Editorial :slight_smile: Thanks!


#24

Please explain / give some reference for Bellman Ford + Dynamic Programming.


#25

my solution id is http://www.codechef.com/viewsolution/1349935
i have done it in i different way and i know that i have missed some cases just want to know which one i meissed


#26

please help


#27

Will the links to the solution by tester and setter ever be updated ?


#28

Don’t think they exist. :stuck_out_tongue: