TopCoder Statistics - 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.

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.
3000

3000

1000000

42

Returns: {1051, 1, 8052391 }
2996

5

580534

1948501517

Returns: {0, 0, 0 }
2995

2993

411478

175701600

Returns: {43, 1, 8561927 }
2998

1

11

1133040875

Returns: {12, 5, 976 }
3000

1

595139

1836955051

Returns: {0, 0, 0 }
2992

2992

463703

1039591800

Returns: {48, 1, 8500192 }
2

2996

630169

1468508435

Returns: {0, 0, 0 }
2991

2992

131596

1434210114

Returns: {2, 1, 8818466 }
47

2996

532998

1085916001

Returns: {3070, 1, 3 }
47

2992

229171

2023059399

Returns: {16957, 1, 14 }
47

2998

707637

1229727803

Returns: {919, 1, 3 }
2992

2993

558561

172270288

Returns: {124, 1, 8413571 }
3000

2994

272886

948917258

Returns: {11, 1, 8713244 }
47

2991

508978

1087222470

Returns: {3461, 1, 3 }
192

2999

178568

355519765

Returns: {2722, 1, 418675 }
5

2993

820339

1870943262

Returns: {0, 0, 0 }
2996

2

942873

2026408624

Returns: {0, 0, 0 }
2995

1

3463

1485905588

Returns: {647, 1, 5 }
2998

2990

492614

853308887

Returns: {65, 1, 8484595 }
192

47

37331

1477705088

Returns: {131, 1, 2 }
2997

47

465485

1940892

Returns: {4755, 1, 4 }
47

2998

387186

88998632

Returns: {7877, 1, 5 }
2993

2

5937

2108757054

Returns: {1032, 1, 14 }
2991

3000

590984

42895311

Returns: {139, 1, 8400947 }
5

2990

71231

1453170456

Returns: {126, 1, 2 }
2

2992

12411

528916607

Returns: {592, 1, 4 }
1

5

56510

1321413367

Returns: {0, 0, 0 }
2992

192

649056

346617440

Returns: {72257, 1, 47 }
3000

2995

999541

492182829

Returns: {1012, 1, 8038377 }
2998

2998

950648

1300568894

Returns: {832, 1, 8084779 }
3000

192

532546

502796335

Returns: {62316, 1, 129 }
2999

2999

455694

284290351

Returns: {57, 1, 8549637 }
2994

3000

791625

1052781061

Returns: {413, 1, 8223932 }
2996

2995

485031

97040700

Returns: {68, 1, 8500700 }
47

2999

290233

102151484

Returns: {13543, 1, 10 }
2991

2994

809296

1130699910

Returns: {427, 1, 8180693 }
3000

2997

757515

468300517

Returns: {357, 1, 8264142 }
3000

2996

432114

879909240

Returns: {50, 1, 8565918 }
5

47

424757

1429174780

Returns: {0, 0, 0 }
2996

47

652661

1830200175

Returns: {1311, 1, 3 }
2996

2

611146

242563618

Returns: {0, 0, 0 }
2997

2993

220842

1244362723

Returns: {5, 1, 8751823 }
2991

2999

466874

1891726748

Returns: {56, 1, 8514990 }
2995

2

19015

2060295352

Returns: {222, 1, 3 }
1

1

908248

1964529467

Returns: {0, 0, 0 }
2999

2993

107487

1301697396

Returns: {1, 8869143, 8869143 }
47

2990

353010

2136870386

Returns: {9626, 1, 9 }
2998

2992

328194

99073865

Returns: {13, 1, 8650163 }
2997

2999

715685

1619264208

Returns: {301, 1, 8299732 }
2

2990

20444

334718070

Returns: {191, 1, 2 }
3000

2998

235322

1983085133

Returns: {4, 1, 8761711 }
2990

2997

654779

597387838

Returns: {245, 1, 8329448 }
5

2997

50381

2144595767

Returns: {481, 1, 3 }
2999

2996

536082

1720060055

Returns: {98, 1, 8464325 }
47

5

431964

447805518

Returns: {0, 0, 0 }
2990

3000

460585

402545275

Returns: {61, 1, 8521001 }
2997

2995

785312

844576579

Returns: {391, 1, 8223834 }
2995

2997

138951

2094311409

Returns: {1, 8838152, 8838152 }
2995

47

509044

398184188

Returns: {3624, 1, 3 }
2996

1

655050

349278773

Returns: {0, 0, 0 }
2992

2991

747916

1316725677

Returns: {374, 1, 8231351 }
47

2

754593

761358727

Returns: {0, 0, 0 }
3000

2992

640285

2036088828

Returns: {201, 1, 8357919 }
1

2997

10246

1606747649

Returns: {89, 1, 2 }
47

2995

164706

454791749

Returns: {18140, 1, 48 }
2992

2990

148599

722198280

Returns: {1, 8798774, 8798774 }
2990

5

16509

1691293679

Returns: {2135, 1, 34 }
2996

47

309199

942936922

Returns: {12211, 1, 8 }
2996

5

106866

153700843

Returns: {13, 1, 1 }
2991

192

981946

390384469

Returns: {66772, 1, 15 }
2995

2998

836235

1827507600

Returns: {500, 1, 8179937 }
2999

2998

763125

2107368689

Returns: {365, 1, 8259412 }
1

2991

51456

1840506704

Returns: {0, 0, 0 }
47

2999

100971

1437375278

Returns: {10664, 1, 247 }
2998

2

826046

805196287

Returns: {0, 0, 0 }
2998

3000

726412

513342065

Returns: {318, 1, 8295734 }
2992

2991

566149

2119888712

Returns: {105, 1, 8400342 }
2995

192

811705

1241566301

Returns: {73725, 1, 24 }
5

2

46363

27067550

Returns: {0, 0, 0 }
2993

2996

582496

923670932

Returns: {136, 1, 8402788 }
2996

2996

212230

1921564817

Returns: {5, 1, 8766269 }
2

2994

442265

475863717

Returns: {0, 0, 0 }
2998

2998

793549

2137947429

Returns: {456, 1, 8227805 }
2993

2

240885

1162101126

Returns: {0, 0, 0 }
2997

2

12882

819222983

Returns: {558, 1, 4 }
2998

2996

361918

1456006488

Returns: {22, 1, 8627197 }
2999

5

62019

1145921960

Returns: {229, 1, 3 }
5

2990

29810

1812898707

Returns: {1569, 1, 8 }
3000

2991

6228

490428354

Returns: {1, 8966774, 8966774 }
1

2993

8722

1600605750

Returns: {146, 1, 2 }
3000

2991

419918

164647511

Returns: {39, 1, 8562603 }
2998

2995

938608

32134090

Returns: {796, 1, 8087206 }
47

1

830213

208686395

Returns: {0, 0, 0 }
2991

1

14285

211560378

Returns: {23, 1, 1 }
2997

2999

94134

1190803699

Returns: {1, 8894362, 8894362 }
2997

2996

929736

280319007

Returns: {770, 1, 8094487 }
2994

2994

639850

1897296966

Returns: {197, 1, 8346195 }
2999

2998

754435

386253728

Returns: {328, 1, 8266967 }
2993

2998

983866

421869180

Returns: {1007, 1, 8040278 }
2997

2997

310056

127958513

Returns: {13, 1, 8677212 }
1

2991

9194

956934778

Returns: {135, 1, 2 }
5

1

448407

1787838088

Returns: {0, 0, 0 }
2998

192

810713

1613667693

Returns: {74151, 1, 25 }
2999

2993

78731

170172939

Returns: {1, 8897632, 8897632 }
2992

192

951812

75299242

Returns: {68393, 1, 21 }
192

47

40118

1254627237

Returns: {111, 1, 2 }
2998

3000

175537

626459750

Returns: {4, 1, 8820154 }
2992

47

298991

2080174925

Returns: {12715, 1, 9 }
3000

2999

429623

1931485369

Returns: {35, 1, 8577462 }
2990

1

847869

2093174743

Returns: {0, 0, 0 }
3000

2998

393154

1296605483

Returns: {38, 1, 8609265 }
2994

2997

37284

1154162604

Returns: {1, 8935812, 8935812 }
192

2999

106266

462328888

Returns: {429, 1, 478423 }
2

2996

696091

633475780

Returns: {0, 0, 0 }
1

2993

167766

170833432

Returns: {0, 0, 0 }
2998

3000

154684

1141028568

Returns: {3, 1, 8840651 }
2993

2995

689136

479048571

Returns: {275, 1, 8300579 }
2991

2990

966603

1211853205

Returns: {790, 1, 8032933 }
2992

2999

968849

670327101

Returns: {861, 1, 8053782 }
2996

47

186350

977113992

Returns: {18464, 1, 28 }
2995

2991

994486

175238726

Returns: {1089, 1, 8015453 }
94

43

632

2045012644

Returns: {2, 7, 3462 }
2

27

16

139348540

Returns: {5, 2, 18 }
74

15

304

1833897564

Returns: {3, 2, 845 }
34

63

360

1460491220

Returns: {2, 3, 1805 }
38

15

180

17831312

Returns: {2, 2, 422 }
1000

1000

1000000

24124

Returns: {115742, 1, 80 }

Statistics

Problem Statement for "DisappearingGridGraph"

Problem Statement

Definition

Notes

Constraints

Examples