Statistics

Problem Statement for "RandomWalkOnGrid"

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.

Definition

Class:
RandomWalkOnGrid
Method:
getExpectation
Parameters:
int, int, int, int, int
Returns:
int
Method signature:
int getExpectation(int x0, int y0, int t, int n, int m)
(be sure your method is public)

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

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

    2

    1

    1

    Returns: 64

  3. 1

    2

    3

    1

    2

    Returns: 352

  4. 123456

    1654321

    20

    20

    20

    Returns: 860242008

  5. 0

    0

    1000000000

    1

    10

    Returns: 0

  6. -887550029

    -425167655

    93615980

    99

    53

    Returns: 386681114

  7. -427580039

    -768715515

    900336294

    5

    49

    Returns: 876992936

  8. 151485118

    207570246

    356694563

    44

    7

    Returns: 940283739

  9. -657127604

    -709966314

    362083632

    72

    43

    Returns: 492048133

  10. 506867352

    -473515706

    175854056

    1

    56

    Returns: 882364172

  11. 661267549

    -811851455

    943422141

    77

    49

    Returns: 103539425

  12. -1000000000

    -1000000000

    200000000

    1

    1

    Returns: 947675421

  13. -780877811

    944328809

    1000000000

    100

    100

    Returns: 390687226

  14. -905752410

    -800789620

    1000000000

    100

    100

    Returns: 907700571

  15. 432668310

    -694681361

    1000000000

    100

    100

    Returns: 586013186

  16. -728880840

    696666363

    1000000000

    100

    100

    Returns: 49540967

  17. 946925817

    -954396094

    1000000000

    100

    100

    Returns: 622917465

  18. -373361022

    956680906

    1000000000

    100

    100

    Returns: 68791639

  19. -75212831

    231384488

    1000000000

    100

    100

    Returns: 588564196

  20. 2453452

    129029

    1000000000

    100

    100

    Returns: 112925438

  21. -1000000000

    -1000000000

    1000000000

    1

    1

    Returns: 623291020

  22. 2349023

    2349082

    1000000000

    100

    100

    Returns: 949235123

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: