Connection Status:
Competition Arena > DisappearingGridGraph

DisappearingGridGraph

TCO19 Japan Regional · 2019-08-01 · by misof

TCO19 Japan Regional · 2019-08-01 · by misof · Graph Theory
Class Name: DisappearingGridGraph
Return Type: int[]
Method Name: keepErasing
Arg Types: (int, int, int, int)
Problem Statement

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.

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
0)
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)}.

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

2)
1000
1000
1
0
Returns: {1, 999999, 999999 }

Regardless of which one vertex gets erased, the rest will still hold together.

3)
97
98
900
424
Returns: {2, 4, 8644 }
4)
3
5
98765
47
Returns: {0, 0, 0 }

Everything got erased.

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

Coding Area

Language: C++17 · define a public class DisappearingGridGraph with a public method vector<int> keepErasing(int R, int C, int N, int seed) · 132 test cases · 2 s / 256 MB per case

Submitting as anonymous