KNGHTMOV - Editorial

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[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

6 Likes

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

3 Likes

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

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!

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.

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.

1 Like

At the bottom of case II, rather than Bellman-Ford, we can just do DFS from the origin and return infinity if we encounter a cycle (if we don’t see a cycle then the DFS explores the DAG in topological order). However, it is important to only consider vertices from which the destination is reachable – which can be found beforehand using DFS on the reversed graph – or cycles that don’t affect the answer cause us to get stuck / wrong answer.

The whole thing is complicated by the fact that the graph is infinite, but this can be handled by making use of the fact that outside the (finite) region spanned by blocked squares, the structure is quite regular allowing us to represent each of these half-infinite intervals by a single special vertex.

I probably didn’t explain it very well, but my solution implements this idea.

2 Likes

Given the answer is a finite number of ways. What is the maximum possible of moves you have to make with the problem’s constraints?

For the independent case I think it’s 250500. I’m not sure for the case where they are dependent and opposite directions.

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?

@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.

can you provide some test cases for this question. i spent a lot of time on this and want to see where i went wrong

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??

1 Like

@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.

1 Like

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

@javacode ditto …i got stuck in exactly that part too :frowning:

1 Like

@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.

1 Like

Hi, Please provide the judge-test data or at-least the test case for which my code fails. Link to my (well-commented) code -: http://www.codechef.com/viewsolution/1341487 . I have followed the same method you have mentioned in your editorial and am curious to know where my code went wrong.
Thanks(in advance) for the help provided.

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?

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

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