TopCoder Statistics - Problem Statement

Problem Statement

There is a two-dimensional infinite plane. Toastman painted N of the grid points in the plane black. These grid points are numbered 0 through N-1. The coordinates of point i are (x[i],y[i]). They are chosen in such a way that no two points share the same x-coordinate and no two points share the same y-coordinate.

Toastwoman wants to color three of these N points: some point r will be red, some point g green, and some point b blue. She thinks a coloring is beautiful if x[r] < x[g] < x[b] and at the same time y[r] < y[b] < y[g]. (Note that the order of colors for the y-coordinate is not the same as the order for the x-coordinate.)

In order to have a large set of points, we will generate one using a pseudorandom generator. You will be given the int N specifying the number of points, and eight ints: xzero, xmul, xadd, xmod, yzero, ymul, yadd, and ymod. Generate the coordinates of the points in the following way:

x[0] = xzero
For each i between 1 and N-1, inclusive, x[i] = (x[i-1] * xmul + xadd) % xmod
y[0] = yzero
For each i between 1 and N-1, inclusive, y[i] = (y[i-1] * ymul + yadd) % ymod

Return the number of beautiful colorings for the set of points generated using the above procedure.

Definition

Class:: ThreePoints
Method:: countColoring
Parameters:: int, int, int, int, int, int, int, int, int
Returns:: long
Method signature:: long countColoring(int N, int xzero, int xmul, int xadd, int xmod, int yzero, int ymul, int yadd, int ymod)
(be sure your method is public)

Notes

There is a solution that does not use any properties of the pseudorandom generator. This solution would solve any set of N points within the time limit.

Constraints

N will be between 3 and 300,000, inclusive.
xmod and ymod will be between N and 1,000,000,000, inclusive.
xzero, xmul and xadd will be between 0 and xmod - 1, inclusive.
yzero, ymul and yadd will be between 0 and ymod - 1, inclusive.
No two points will have the same x-coordinate.
No two points will have the same y-coordinate.

Examples

9

3

8

6

11

5

7

8

11

Returns: 8

There are 9 points. The coordinates of points are (3, 5), (8, 10), (4, 1), (5, 4), (2, 3), (0, 7), (6, 2), (10, 0), and (9, 8). There are 8 beautiful coloring.
300000

3

8

6

999999997

5

7

8

999999997

Returns: 748746671709844
300000

985630507

87425790

563581248

999999937

87797782

944618609

944054191

999999937

Returns: 749364484652325
300000

140860447

513229178

410736925

999999937

198517093

601121366

992497434

999999937

Returns: 747826412223783
300000

576911469

473167597

126264043

999999937

676027818

666805780

735431024

999999937

Returns: 752657319963487
300000

80269259

344971858

867370779

999999937

905515918

66834177

343108313

999999937

Returns: 751868702767566
300000

950395907

864670820

255271051

999999937

640893394

845087984

374045907

999999937

Returns: 750191679521870
300000

77796041

515486512

283066250

999999937

950949759

473137279

947136850

999999937

Returns: 748963743244116
300000

430758875

959507598

569775557

999999937

335737684

554542442

191314566

999999937

Returns: 748461278145639
300000

687142135

754682938

919297571

999999937

126412864

597134859

536933579

999999937

Returns: 748857427270630
300000

514580499

794009092

825844212

999999937

463307611

762233169

869992432

999999937

Returns: 748805294362227
300000

165037669

275440669

587917523

999999937

237667668

379784392

762684734

999999937

Returns: 749398911544417
243683

38689739

21253916

20689498

87425665

13330283

346005162

126264043

563581186

Returns: 402739693118750
132327

80269259

11360233

200564998

666805781

170084956

331403152

343108313

735430962

Returns: 64048316216380
2246

640893394

845087984

509375023

864670821

56712022

4944534

27795261

255270989

Returns: 313516312
62705

41443219

374597189

352706932

473137280

463307611

762233169

922855581

947136788

Returns: 6852296316559
145375

237667668

2580979

211803394

275440670

87879259

63739662

448666865

587917461

Returns: 85148446098875
1976

256006816

376133036

229126830

745436683

2279590

69364425

106188726

121982812

Returns: 213054405
82696

423940190

60066384

764740635

940920897

77755853

62194625

83965579

100907262

Returns: 15670664977085
202745

192498320

96959725

349714545

781811136

110074391

74445509

144428827

207049742

Returns: 231404630320163
122027

194694600

422747202

153074830

505566760

176683083

66893823

203905726

504589281

Returns: 50582144751998
51881

10058218

71869316

45019169

82569967

24867950

86950263

11488854

120189350

Returns: 3892083691080
4

9

6

8

10

4

8

5

10

Returns: 2
20

30

3

71

100

78

12

50

100

Returns: 263
300000

99097861

102766912

95284952

123456789

443104491

971853214

569775557

987654321

Returns: 749410681185726
300000

0

1

1

300000

0

1

1

300000

Returns: 0
300000

0

1

1

300000

0

1

299999

300000

Returns: 44999550001
300000

0

1

1

300000

150000

1

1

300000

Returns: 0
300000

0

1

1

300000

150000

1

299999

300000

Returns: 1687477499925001
3

1

3

4

5

2

1

3

4

Returns: 1
3

3

2

0

4

4

2

0

5

Returns: 0
4

3

1

1

8

0

4

1

6

Returns: 2
4

3

4

4

6

0

4

1

6

Returns: 0
5

4

5

6

7

6

4

5

9

Returns: 0
5

2

5

3

7

0

5

5

9

Returns: 4
6

1

1

5

6

0

1

5

6

Returns: 0
6

2

1

6

11

6

1

1

7

Returns: 1
7

4

1

1

10

4

1

1

7

Returns: 0
7

2

7

4

11

1

1

1

7

Returns: 2
8

0

2

3

11

6

1

7

10

Returns: 3
8

5

1

1

10

6

8

8

11

Returns: 8
9

8

1

3

14

12

1

11

14

Returns: 30
9

3

1

5

12

7

4

2

9

Returns: 2
10

8

1

9

10

4

7

9

13

Returns: 23
10

5

1

11

12

12

7

10

13

Returns: 23
3

985630444

87425664

563581185

1000000000

87797719

944618546

944054128

1000000000

Returns: 0
300000

140860384

513229178

410736925

1000000000

198517030

601121303

992497371

1000000000

Returns: 748173821391236
300000

0

1

1

300000

100000

1

299999

300000

Returns: 1999989999800001
300000

432523

4554432

431224

100044587

5425

12523

54254213

100044587

Returns: 750957314536063
300000

99097861

102766912

952849562

999999961

443104491

971853214

569775557

999999987

Returns: 750725641730465
300000

99097861

102766912

95284952

123456789

443104491

971853204

569775557

987654321

Returns: 749458199093005

Statistics

Problem Statement for "ThreePoints"

Problem Statement

Definition

Notes

Constraints

Examples