FrogsOnGrid
2015 TCO Final · 2015-04-08 · by sugim48
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".
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.
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.
Submissions are judged against all 104 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FrogsOnGrid with a public method string isPossible(int H, int W, vector<int> r, vector<int> c) · 104 test cases · 2 s / 256 MB per case