TopCoder Statistics - Problem Statement

Problem Statement

Petya likes donuts. He tries to find them everywhere. For example if he is given a grid where each cell contains a '0' or '.' he will construct donuts from the cells.

To make the donuts:

Petya first selects a rectangle of cells of width, w, and height, h, where both are at least 3.
Then he removes a rectangular hole of width w-2 and height h-2 centered in the larger rectangle.
For the remaining cells (a closed rectangular ring) to be a valid donut, all of the cells must contain '0' (because donuts are shaped like zeros). Cells in the hole can contain anything since they are not part of the donut.

Here is an example with three overlapping donuts.

..........
.00000000.
.0......0.
.0.000000.
.0.0...00.
.0.0...00.
.0.000000.
.0......0.
.00000000.
..........

The grid in this problem will be pseudo-randomly generated using the following method:
You are given four ints: H (the grid height), W (the grid width), seed and threshold. Let x₀=seed and for all i>=0 let x_i+1 = (x_i * 25173 + 13849) modulo 65536. Process the cells of the matrix in row major order (i.e., first row left to right, second row left to right, etc.). Each time you process a cell, calculate the next x_i (starting with x₁ for the upper left corner). If it is greater than or equal to threshold, the current cell will contain a '.', otherwise it will contain a '0'.

Return the number of distinct donuts in the figure. Two donuts are considered distinct if they either have different width or height, or if the top left hand corner is in a different location (i.e., overlapping donuts are counted).

Definition

Class:: DonutsOnTheGrid
Method:: calc
Parameters:: int, int, int, int
Returns:: long
Method signature:: long calc(int H, int W, int seed, int threshold)
(be sure your method is public)

Notes

The random generation of the input is only for keeping the input size small. The author's solution does not depend on any properties of the generator, and would work fast enough for any input of allowed dimensions.

Constraints

H will be between 1 and 350, inclusive.
W will be between 1 and 350, inclusive.
seed will be between 0 and 65535, inclusive.
threshold will be between 0 and 65536, inclusive.

Examples

350

350

1

65536

Returns: 3687647076
257

210

36894

19420

Returns: 5
36

48

1809

31235

Returns: 12
37

327

46242

20375

Returns: 1
344

43

14547

58855

Returns: 118610
88

70

9249

26807

Returns: 2
343

113

31408

48903

Returns: 19106
28

298

2230

44929

Returns: 1441
142

50

16772

36823

Returns: 132
145

187

31639

8116

Returns: 0
210

117

47189

32284

Returns: 167
236

296

18596

11592

Returns: 0
90

302

8868

34097

Returns: 251
111

162

20883

24601

Returns: 15
58

228

26591

38876

Returns: 507
116

5

13227

3500

Returns: 0
159

271

9823

14191

Returns: 1
185

57

7141

54393

Returns: 22040
350

6

9177

24060

Returns: 1
232

78

2604

15579

Returns: 0
58

339

31350

30053

Returns: 55
87

128

22200

6058

Returns: 0
332

92

23376

36548

Returns: 618
342

43

32274

34220

Returns: 144
170

131

5360

14631

Returns: 0
252

14

27833

50994

Returns: 2623
177

291

25861

23037

Returns: 15
257

324

11534

24451

Returns: 68
61

159

16367

25481

Returns: 9
157

258

29276

32454

Returns: 258
247

335

25750

38020

Returns: 2310
148

297

22764

49608

Returns: 25364
128

85

29741

14905

Returns: 0
289

150

38488

10128

Returns: 0
79

335

2858

45733

Returns: 5570
198

175

8375

57823

Returns: 259018
113

39

20603

32353

Returns: 19
84

155

31640

20327

Returns: 2
271

103

31946

42843

Returns: 2750
1

317

6663

40637

Returns: 0
164

178

7093

44248

Returns: 4266
117

201

21586

25785

Returns: 11
137

329

21739

38377

Returns: 1362
74

271

53821

18211

Returns: 6
337

146

11266

32607

Returns: 280
275

161

26701

5489

Returns: 0
34

138

27276

32211

Returns: 36
207

189

32002

20079

Returns: 3
77

92

54161

8096

Returns: 0
131

277

17232

1609

Returns: 0
251

159

31420

12125

Returns: 0
26

85

22149

30947

Returns: 2
144

344

19882

24373

Returns: 29
26

57

42540

31153

Returns: 3
141

210

7024

9850

Returns: 0
177

29

5314

17954

Returns: 0
34

212

55601

12810

Returns: 0
15

322

44752

25529

Returns: 4
147

61

26266

21365

Returns: 2
299

315

32741

40857

Returns: 5813
316

2

29740

31558

Returns: 0
173

63

29829

10822

Returns: 0
133

169

29040

42661

Returns: 2421
256

346

43261

30973

Returns: 334
202

307

33208

14191

Returns: 0
167

202

4347

6688

Returns: 0
179

204

27759

39877

Returns: 1623
62

343

45172

42965

Returns: 2467
33

223

51755

46224

Returns: 1520
279

122

7519

28479

Returns: 73
143

258

23322

58335

Returns: 333898
283

40

28914

33605

Returns: 105
267

278

46046

4060

Returns: 0
307

145

762

39524

Returns: 2004
341

86

30629

28399

Returns: 46
278

77

19466

56497

Returns: 93822
289

255

6393

24667

Returns: 40
111

289

22295

24038

Returns: 11
88

271

34773

26050

Returns: 14
76

185

20146

43512

Returns: 1444
142

350

30442

28900

Returns: 120
224

208

9140

26890

Returns: 39
253

320

35102

41083

Returns: 4241
209

344

32100

31801

Returns: 394
27

260

16065

45582

Returns: 1420
108

142

58731

30877

Returns: 76
146

222

6728

8748

Returns: 0
164

201

25496

31906

Returns: 111
343

41

21235

3094

Returns: 0
37

25

9527

57274

Returns: 3068
292

265

47961

3378

Returns: 0
115

342

7018

28648

Returns: 84
26

330

27463

30105

Returns: 32
211

105

29178

4226

Returns: 0
290

108

16735

45368

Returns: 5682
269

77

29375

24455

Returns: 17
95

287

7659

5075

Returns: 0
69

118

23578

38344

Returns: 210
172

106

39212

19924

Returns: 2
131

152

14115

7519

Returns: 0
127

176

23449

17627

Returns: 0
5

5

222

55555

Returns: 4

Here is an example of the grid: 00000 00.0. .0000 00.00 00000
350

350

1354

65500

Returns: 2909504310
349

317

23566

65000

Returns: 263790994
350

347

11

63500

Returns: 23150152
337

340

244

62111

Returns: 6654659
5

6

121

58000

Returns: 3

Here is the grid and three donuts in it: 00000. XXX... XXX... ..XXX. 0.0000 X.X... X.X... ..X.X. 0.000. X.X... X.X... ..XXX. 000.00 XXX... X.X... ...... 000.00 ...... XXX... ......
4

5

6

50000

Returns: 1

The grid is: 0.0.0 00000 .00.0 0.000
4

4

1

65536

Returns: 9

Here, the grid is completely filled by 0's. There are 9 possible placements of a donut: XXX. XXX. .XXX .XXX .... .... XXXX .... XXXX X.X. X.X. .X.X .X.X XXX. .XXX X..X XXXX X..X XXX. X.X. .XXX .X.X X.X. .X.X XXXX X..X X..X .... XXX. .... .XXX XXX. .XXX .... XXXX XXXX
344

347

1

65535

Returns: 3468398770
350

350

0

65536

Returns: 3687647076
350

350

1

0

Returns: 0
320

320

4091

30872

Returns: 294
350

350

2

65534

Returns: 3634680381
333

333

33333

33333

Returns: 903
100

100

1

65536

Returns: 23532201
350

350

1218

31245

Returns: 545
350

350

12312

0

Returns: 0
350

350

1

65000

Returns: 291635119
350

350

4325

65536

Returns: 3687647076
350

350

65535

65536

Returns: 3687647076
350

350

222

65536

Returns: 3687647076
349

349

24356

52576

Returns: 163585

Statistics

Problem Statement for "DonutsOnTheGrid"

Problem Statement

Definition

Notes

Constraints

Examples