TopCoder Statistics - Problem Statement

Problem Statement

NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.

Manhattan can be represented as an infinite two-dimensional plane with a Cartesian coordinate system. Manhattan is crossed by horizontal and vertical streets parallel to the axes. Each point with integer coordinates lies on the intersection of two streets.

Manao is in charge of the Manhattan Police Department. He is currently investigating patrol routes. There are N control intersections numbered from 0 to N-1 in Manhattan. A patrol route is a pair {A, B} of control intersections. When a squad is completing a patrol route, it moves only along the streets and takes the shortest path from A to B. When there are multiple shortest paths from A to B, the squad can take any of them. Two paths intersect if there is an intersection that belongs to both of them. Two patrol routes intersect if no matter which paths the squads completing them choose, these paths intersect.

You are given ints AX, BX, MX, AY, BY, MY. The X-coordinates of the intersections are computed as follows:

X₀ = BX
X_i = (AX * X_i-1 + BX) mod MX for 0 &lt i &lt N

Y-coordinates are computed correspondingly using AY, BY, MY. The X-coordinates will be pairwise distinct, as will be the Y-coordinates.

We treat routes {A, B} and {B, A} as the same. Consider the pairs of routes {{A, B}, {C, D}} such that all points A, B, C and D are distinct. Return the number of such pairs which intersect.

Definition

Class:: ManhattanPatrol
Method:: countIntersections
Parameters:: int, int, int, int, int, int, int
Returns:: long
Method signature:: long countIntersections(int N, int AX, int BX, int MX, int AY, int BY, int MY)
(be sure your method is public)

Constraints

N will be between 4 and 500, inclusive.
MX will be between 4 and 40000, inclusive.
AX will be between 1 and MX-1, inclusive.
BX will be between 1 and MX-1, inclusive.
MY will be between 4 and 40000, inclusive.
AY will be between 1 and MY-1, inclusive.
BY will be between 1 and MY-1, inclusive.
All elements in the sequence of X-coordinates generated according to the statement will be distinct.
All elements in the sequence of Y-coordinates generated according to the statement will be distinct.

Examples

4

1

2

11

2

2

13

Returns: 1

The control intersections are: 0: (2, 2) 1: (4, 6) 2: (6, 1) 3: (8, 4) Routes {0, 3} and {1, 2} intersect.
7

1

2

11

2

2

13

Returns: 2

This case has the same seed as the previous one, but contains three more control intersections. In addition to {0, 3} - {1, 2}, routes {0, 3} and {2, 6} also intersect.
6

1

2

7

1

1

6

Returns: 5
7

1

1

11

13

1

16

Returns: 0
20

6

1

211

13

11

186

Returns: 862
500

124

66

11266

13368

15623

21521

Returns: 428883537
4

1

1

4

1

1

4

Returns: 0
4

1

3

4

3

2

7

Returns: 1
380

1823

10845

24666

6040

25246

29665

Returns: 142466311
337

4486

20517

24451

1992

873

19308

Returns: 83448168
101

4006

1049

5597

5880

14371

36663

Returns: 741979
358

7472

5190

8924

2817

16436

33946

Returns: 117158504
222

8210

27662

30862

12803

31111

32785

Returns: 17294687
45

2943

413

30953

32712

35901

37367

Returns: 25122
68

1037

8935

10091

7489

5034

16146

Returns: 105644
125

1716

679

9615

3025

3510

12840

Returns: 1712586
23

4688

15956

21676

3098

1773

3757

Returns: 1365
497

2406

16746

26893

30913

30802

33285

Returns: 423806447
131

14587

7497

23319

22362

5827

33446

Returns: 1942331
269

1957

6970

8508

4026

867

4098

Returns: 34290152
286

13745

5209

30409

20280

20740

22534

Returns: 46445592
102

1429

3854

6179

4119

2841

4506

Returns: 670498
61

26618

18384

32623

3743

10296

13098

Returns: 85021
335

17936

24266

37945

6387

13590

18636

Returns: 91875077
427

1284

231

2798

8498

22757

28541

Returns: 233629798
165

10717

11530

15104

3545

5745

39913

Returns: 4338846
471

14882

3001

34939

4825

4360

10366

Returns: 360698755
399

13894

3389

25798

17880

8810

18159

Returns: 163810061
351

1293

552

21647

9808

1098

9941

Returns: 103812316
83

8562

7949

16489

9209

27446

29912

Returns: 296885
136

18107

20574

20963

9147

5061

9244

Returns: 2140176
31

17627

12988

30388

999

1195

1522

Returns: 6009
226

17037

5079

38869

36337

8304

38727

Returns: 18747216
80

11406

12859

24434

14137

4711

16117

Returns: 250839
160

3229

4172

26727

5426

10363

28591

Returns: 4737779
23

2559

3541

4356

11677

11311

27560

Returns: 1466
282

29797

426

31656

138

17087

39827

Returns: 43710743
45

19781

14658

26712

4374

5276

11764

Returns: 30894
304

3524

10073

17503

17334

24794

30902

Returns: 58563193
57

733

1222

4048

1756

519

3854

Returns: 79665
341

23908

16404

29644

32016

28077

39889

Returns: 98501264
167

30366

3027

36579

1456

32544

33116

Returns: 4763863
362

17452

17280

26137

14184

4034

15386

Returns: 119391057
382

10787

13962

25341

1601

3324

8416

Returns: 146056452
15

3240

17492

22700

17173

17780

18836

Returns: 342
27

3035

4128

9992

16421

9521

17618

Returns: 2272
211

11513

5026

19614

12140

228

15178

Returns: 12721462
100

1630

7643

9870

10367

197

21934

Returns: 602196
168

10103

12600

19645

21810

5471

33758

Returns: 5506928
260

10532

9770

22478

11376

3295

22342

Returns: 32395430
9

3928

16535

16846

4862

4879

8978

Returns: 32
23

25549

1424

32610

26591

35243

35504

Returns: 907
480

25858

25114

29255

14055

1030

35791

Returns: 360709436
380

18252

6742

23893

9096

13003

35152

Returns: 143668554
35

19334

24270

38197

621

62

1950

Returns: 7868
122

8250

19217

31260

5039

23303

29917

Returns: 1478742
119

188

5450

15058

8135

2682

10930

Returns: 1321425
19

20363

16039

36001

6467

7922

29548

Returns: 615
162

4225

3390

4418

5213

6374

8443

Returns: 4179761
500

1763

5892

12781

3217

3529

4036

Returns: 431849238
500

7827

6973

11789

10684

15122

39135

Returns: 435361312
500

1763

22343

34097

10396

23492

31511

Returns: 450675891
500

3918

11286

12778

7393

7100

16757

Returns: 455539467
500

2383

2326

10404

6741

20476

21282

Returns: 464463753
500

11506

23735

25471

15299

20725

22071

Returns: 466759793
500

2822

2284

3171

2911

10186

17156

Returns: 471632975
500

1410

4760

6767

28892

14896

32786

Returns: 474238379
500

9211

3868

20547

4894

4866

4913

Returns: 480330893
500

32422

22998

35704

17857

31876

37866

Returns: 482778654
500

10245

998

30029

16519

73

30813

Returns: 484078917
500

11989

9746

14817

10752

15968

16858

Returns: 484896488
500

11917

3051

17335

379

3365

7158

Returns: 487545394
500

3034

13154

17110

12848

13601

26744

Returns: 488147864
500

23114

18984

30078

20594

19415

35664

Returns: 492711511
500

8719

12919

17716

681

12322

29332

Returns: 390618877
500

19758

14303

20322

1014

9262

17387

Returns: 379860052
500

28103

1107

34391

21487

22075

32315

Returns: 376346913
500

21274

3373

35318

4219

964

21686

Returns: 371761765
500

9809

9547

10409

26986

8280

34645

Returns: 370960154
500

11545

8100

15818

8611

6679

34895

Returns: 364130488
500

1

1

10000

1

1

10000

Returns: 0
500

2723

121

4363

6873

5226

10133

Returns: 363972219
500

1

1

26088

21432

26039

29638

Returns: 506398043

Statistics

Problem Statement for "ManhattanPatrol"

Problem Statement

Definition

Constraints

Examples