PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
As suggested by the problem constraints, there are 2 cases to be dealt with.
Case 1: W≥N and H≥N.
In this case, a O(N^2) solution is possible. We note that Dave will never have to move south or west, except possibly when he’s within N of (0,0) or (W,H). In particular, this means that every shortest path will pass through exactly one point on the diagonal consisting of points of the form (i, N-i) (call this Diagonal A), and exactly one point on the diagonal consisting of points of the form (W-i, H+i-N) (call this Diagonal B). Call a path “clean” if it does not pass through any bad intersections. Call a path “dirty” if it may or may not pass through any bad intersections. A path from P1 to P2 is still considered clean if the only bad intersection is P2 itself. We begin by calculating the minimal distance and number of clean paths from (0,0) to each point on Diagonal A, and from (W,H) to each point on Diagonal B. This can be done using a breadth-first search. We can discard points on a diagonal if there is another point on the same diagonal that can be reached in fewer moves. Now for any point P on or between the two diagonals, we can compute the number of clean paths from (0,0) to P as follows:
For every point on PA on Diagonal A, if P is north/east of PA, calculate the number of dirty paths from PA to P as Binom(dx+dy, dx), where Binom is the binomial coefficient, and dx and dy are the differences in x and y values, respectively. Note that 1000000037 = 421 * 563 * 4219, so the binomial coefficient can be efficiently calculated using Lucas’ Theorem in conjunction with the Chinese Remainder Theorem. Multiply the number of clean paths from (0,0) to PA by the number of dirty paths from PA to P, and add this to our total.
For every bad intersection Pbad south/west of P but north/west of Diagonal A, calculate the number of dirty paths from Pbad to P. Multiply this number by the number of clean paths from (0,0) to Pbad, and subtract this from our total.
Finally, for each point PB on Diagonal B, we multiply the number of clean paths from (0,0) to PB by the number of clean paths from PB to (W,H) and add this to our grand total.
Case 2: W < N or H < N
In this case a O(N^3) algorithm will suffice, although asymtotically faster algorithms do exist. A line sweeping algorithm gets the job done. Assume, without loss of generality, that H < N. We keep track of the shortest distance and number of paths for all points on a vertical line. The line begins at x=0, then we move the line east until it reaches x=W. We proceed using “short jumps” and “long jumps”. A short jump is used to move the line past any bad intersections, and a long jump is used to move the line through a section containing no bad intersections. Short jumps are achieved using a breadth-first search in a small area. For long jumps, we have two lines, L1 and L2 for which no bad intersections are located on or between them, and the shortest distance and number of paths is known for every point on L1. Note that the minimal distances for points on L2 are just the corresponding minimal distances for points on L1 plus the distance between L1 and L2. For each point on P2 on L2, and for each point P1 on L1, we calculate the number of paths from P1 to P2 using binomial coefficients (our restrictions guarantee that all such paths are clean). If it’s possible for a shortest path from (0,0) to P2 to pass through P1, we multiply the number of paths from (0,0) to P1 by the number of paths from P1 to P2 and add this to our total for P2. This process can be sped up with fast multiplication techniques such as Karatsuba multiplication or Number-theoretic Transform, but these are not necessary to pass within the time limit.