DisappearingGridGraph | Topcoder Archive

Problem Statement

This task has a non-standard time limit: 3 seconds.

An R x C grid graph is defined as follows:

The vertices are pairs of integers (r, c) such that 0 <= r < R and 0 <= c < C.
Two vertices (r1, c1) and (r2, c2) are connected by an edge iff abs(r1-r2) + abs(c1-c2) = 1.

The vertices of your grid graph are disappearing, one vertex at a time. Each time a vertex disappears, the edges incident to that vertex disappear as well.

Consider the following pseudocode:

state = seed
repeat N times:
    state = (state * 1103515245 + 12345) modulo 2^31
    rx    = (state div 2^10) modulo R
    state = (state * 1103515245 + 12345) modulo 2^31
    cx    = (state div 2^10) modulo C
    delete the vertex (rx, cx) if it is still present
    add   = the current number of connected components in the graph
    state = (state + add) modulo 2^31

You start with a full R x C grid graph and you execute the pseudocode given above. Determine the number and the sizes of the connected components in the final graph. Return a int[] with three elements: { the number of connected components, the size of the smallest one, the size of the largest one }. If everything got erased, return {0, 0, 0} instead.

Definition

Class:: DisappearingGridGraph
Method:: keepErasing
Parameters:: int, int, int, int
Returns:: int[]
Method signature:: int[] keepErasing(int R, int C, int N, int seed)
(be sure your method is public)

Notes

The reference solution would work for any sequence of N vertex removals. It does not depend on any properties of the pseudorandom generator.

Constraints

R will be between 1 and 3000, inclusive.
C will be between 1 and 3000, inclusive.
N will be between 1 and 1,000,000, inclusive.
seed will be between 0 and (2^31 - 1), inclusive.

Examples

```
1
```
```
7
```
```
4
```
```
47
```
```
Returns: {3, 1, 2 }
```
When executing the pseudocode correctly, we do the following: Erase (0,3). After this step we have 2 connected components. Erase (0,1). After this step we have 3 connected components. Erase (0,6). After this step we still have 3 connected components. Erase (0,3) again. Nothing changes, as (0,3) has already been erased. At the end, we have three connected components: {(0,0)}, {(0,2)}, and {(0,4),(0,5)}.
```
3
```
```
3
```
```
5
```
```
47
```
```
Returns: {3, 1, 2 }
```
We erase (1,2), (0,0), (0,0) again, (2,0), and finally (1,1). At the end there are 3 connected components: one with a single vertex and two containing two vertices each.
```
1000
```
```
1000
```
```
1
```
```
0
```
```
Returns: {1, 999999, 999999 }
```
Regardless of which one vertex gets erased, the rest will still hold together.
```
97
```
```
98
```
```
900
```
```
424
```
```
Returns: {2, 4, 8644 }
```
```
3
```
```
5
```
```
98765
```
```
47
```
```
Returns: {0, 0, 0 }
```
Everything got erased.

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.