ShortBugPaths
TCO20 Round 3B · 2020-04-13 · by misof
Problem Statement
The time limit for this problem is 3 seconds.
A bug lives on an N times N square grid. The distance between cells (r1,c1) and (r2,c2) in the grid is |r1-r2| + |c1-c2|.
The bug moves by making short jumps.
You are given the
Given are N, D and the number J of consecutive jumps the bug must make. The bug can start its journey anywhere on the grid. Count all possible paths of the bug, and return that count modulo 10^9 + 7. (Each path is a sequence of J+1 cells the bug stood on, and two paths are distinct if these sequences are distinct.)
Notes
- The bug is not allowed to jump outside the grid.
Constraints
- N will be between 1 and 10^9, inclusive.
- D will be non-empty.
- Elements of D will be between 0 and 10, inclusive.
- Elements of D will be distinct.
- J will be between 0 and 10, inclusive.
3
{1}
1
Returns: 24
The bug starts anywhere on the grid and then jumps to a neighboring cell.
123456789
{0}
3
Returns: 643499475
The bug starts anywhere on the grid and then jumps on the spot three times. The return value is (123456789 * 123456789) mod (10^9 + 7).
5
{0, 10, 2}
4
Returns: 38281
The answer would have been the same for D = {2, 0} because no two cells of this grid have distance 10.
1
{1}
0
Returns: 1
1
{1}
1
Returns: 0
1000
{0,1}
1
Returns: 4996000
There are exactly 10^6 paths where the bug jumps on the spot, and slightly fewer than 4*10^6 paths where it hops to a neighboring cell.
Submissions are judged against all 115 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ShortBugPaths with a public method int count(int N, vector<int> D, int J) · 115 test cases · 2 s / 256 MB per case