Connection Status:
Competition Arena > WolfPackDivTwo

WolfPackDivTwo

SRM 573 · 2012-12-13 · by tozangezan

SRM 573 · 2012-12-13 · by tozangezan · Dynamic Programming, Math
Class Name: WolfPackDivTwo
Return Type: int
Method Name: calc
Arg Types: (vector<int>, vector<int>, int)
Problem Statement

Problem Statement

Wolf Sothe is a member of the wolf pack called Grid Walkers. The N wolves in the pack are numbered 0 through N-1. (Wolf Sothe is the wolf number 0, but this does not matter.)

At any moment, each wolf is located at some grid point in the plane. Multiple wolves may share the same grid point. For each i, the wolf number i is initially located at (x[i],y[i]). Then there are exactly m rounds in which the wolves move. In each round, each wolf must move from its current grid point to one of the four adjacent grid points. More precisely, the wolf located at (i,j) has to move to (i+1,j), (i-1,j), (i,j+1), or (i,j-1).

The wolves have a goal: all of them have to be located at the same grid point after the m-th round. The grid point at which they all meet is not given - they can choose any grid point.

You are given the int[]s x and y, and the int m. Count and return the number of ways in which the wolves can reach their goal, modulo 1,000,000,007. Two ways of reaching the goal are different if in some round the same wolf moves in a different direction. (Equivalently, two ways of reaching the goal are different if there is some number of rounds x and a wolf y such that the grid point of the wolf y after x rounds of the first way differs from the grid point of the wolf y after x rounds of the second way.)

Constraints

  • x will contain between 2 and 50 elements, inclusive.
  • y will contain the same number of elements as x.
  • m will be between 1 and 50, inclusive.
  • Each element of x and y will be between 0 and 50, inclusive.
  • The points (x[i],y[i]) will be pairwise distinct.
Examples
0)
{3,5}
{0,0}
1
Returns: 1

There are two wolves: one at (3,0) and the other at (5,0). There will be 1 round of movement. Thus, the meeting point has to be (4,0), wolf 0 has to move by (+1,0) and wolf 1 by (-1,0). This is the only way of reaching the goal.

1)
{0,1}
{0,0}
1
Returns: 0

In this case the two wolves cannot be at the same grid point at the end. Note that they both have to move.

2)
{0,2,4}
{0,0,0}
2
Returns: 4

In this case, the meeting point has to be (2,0). Wolf 0 has to go (0,0) -> (1,0) -> (2,0). Wolf 2 has to go (4,0) -> (3,0) -> (2,0). Wolf 1 has 4 possible ways of reaching the meeting point: in the first step he can choose any direction, and in the second step he will then choose the opposite direction.

3)
{33,31,23}
{12,22,30}
17
Returns: 32212804
4)
{34,28,16,12,44,34}
{18,16,4,28,38,24}
38
Returns: 170739128
103)
{7,8}
{8,7}
1
Returns: 2

This time there are two possible meeting points. For each of them there is a unique way in which the wolves can reach it.

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

Coding Area

Language: C++17 · define a public class WolfPackDivTwo with a public method int calc(vector<int> x, vector<int> y, int m) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous