FrogsOnGrid | Topcoder Archive

Problem Statement

There is a rectangular grid with H rows and W columns. The cells have coordinates between (0, 0) and (H-1, W-1), inclusive.

For each valid i, the cell (r[i], c[i]) is empty, and every other cell is occupied by exactly one frog.

Simultaneously, each frog will jump exactly once. The frog on the cell (i, j) can jump either to the cell ((i+1) mod H, j) or to the cell (i, (j+1) mod W).

Return "Possible" if the frogs can jump in such a way that the set of cells occupied by frogs after the jump will be exactly the same as the set of cells occupied by frogs before the jump. Otherwise, return "Impossible".

Definition

Class:: FrogsOnGrid
Method:: isPossible
Parameters:: int, int, int[], int[]
Returns:: String
Method signature:: String isPossible(int H, int W, int[] r, int[] c)
(be sure your method is public)

Constraints

H and W will be between 2 and 10^6, inclusive.
r and c will contain between 1 and min(50, H*W-1) elements, inclusive.
r and c will contain the same number of elements.
Each element of r will be between 0 and H-1, inclusive.
Each element of c will be between 0 and W-1, inclusive.
All the coordinate pairs (r[i], c[i]) will be distinct.

Examples

```
2
```
```
3
```
```
{1}
```
```
{2}
```
```
Returns: "Possible"
```
Here is the configuration of frogs before the jump and after the jump. (Letters represent frogs, a grey cell is an empty cell. Rows are numbered top to bottom, columns left to right.)
```
2
```
```
2
```
```
{1}
```
```
{1}
```
```
Returns: "Impossible"
```
The frog on the cell (0, 1) has to avoid jumping to the empty cell (1, 1), so it will jump to the cell (0, 0). Similarly, the frog on the cell (1, 0) will also jump to the cell (0, 0). They will land on the same cell. As a result, the set of occupied cells will change.
```
4
```
```
3
```
```
{3, 3}
```
```
{0, 2}
```
```
Returns: "Possible"
```
Here is the configuration of frogs before the jump and after the jump.
```
3
```
```
4
```
```
{2, 2}
```
```
{0, 3}
```
```
Returns: "Impossible"
```
```
10
```
```
10
```
```
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
```
```
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
```
```
Returns: "Possible"
```
If all frogs jump from the cell (i, j) to the cell (i, (j+1)%W), the set of occupied cells will not change.

{5578, 171360, 165651, 78698, 225921, 206965, 219577, 31188, 95271, 3881}

{206522, 597301, 111837, 393869, 619930, 579804, 537067, 582524, 555054, 55212}

Returns: "Possible"

{61520, 51697, 92473, 104497, 91831, 100161, 103372, 30392, 13589, 76957}

{698703, 804971, 626783, 455865, 138050, 542439, 467457, 432845, 895035, 173098}

Returns: "Impossible"

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.