RandomWalkOnGrid

SRM 683 · 2016-01-04 · by Arterm

SRM 683 · 2016-01-04 · by Arterm · Advanced Math, Dynamic Programming

Show categories

Class Name: RandomWalkOnGrid

Return Type: int

Method Name: getExpectation

Arg Types: (int, int, int, int, int)

Problem Statement

The two-dimensional plane is divided into a grid of unit square cells. A token is placed onto the cell (x0, y0). You are playing a very simple game with the token. The game consists of exactly t moves.

Each move looks as follows: You choose one of the four cardinal directions (up, down, left, or right) uniformly at random, and you move the token one cell in the chosen direction.

You are given the ints x0, y0, and t. You are also given ints n and m that are used to compute your score at the end of the game. Your score is computed as (x^n * y^m), where (x, y) are the coordinates of the cell that contains the token at the end of the game.

Let E be the expected value of your score. Compute and return the following value: (E * 4^t) modulo 1,000,000,007.

Constraints

x0 and y0 will be between -1,000,000,000 and 1,000,000,000, inclusive.
t will be between 0 and 1,000,000,000, inclusive.
n and m will be between 1 and 100, inclusive.

Examples

2
2
1
1
1
Returns: 16

The token starts in the cell (2, 2). As t=1, you move it exactly once. Hence, with equal probability the token will end in one of the following four cells: (1, 2), (2, 1), (2, 3), and (3,2). The scores for these cells are 2, 2, 6, and 6. Thus, the expected score is E = (2+2+6+6)/4 = 4. This means that you should return the value (4 * 4^1) modulo 1,000,000,007 = 16.

2
2
2
1
1
Returns: 64

1
2
3
1
2
Returns: 352

123456
1654321
20
20
20
Returns: 860242008

0
0
1000000000
1
10
Returns: 0

Submissions are judged against all 22 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RandomWalkOnGrid with a public method int getExpectation(int x0, int y0, int t, int n, int m) · 22 test cases · 2 s / 256 MB per case