TopCoder Statistics - Problem Statement

Problem Statement

You are given an array L containing N integers. Count the number of ways in which we can choose three indices (i,j,k) such that 0 <= i < j < k <= N-1 and it is possible to constuct a non-degenerate triangle whose side lengths are L[i]+L[j], L[j]+L[k], and L[k]+L[i].

In a non-degenerate triangle, all sides have positive lengths and the triangle has a positive area.

You are given N, the int[] B containing a prefix of L, and ints seed and MX. Use the following pseudocode to generate the array L:

A[0] = seed
for i=1 to N-1:
	A[i] = (A[i-1]*1103515245 + 12345) modulo 2147483648

for i=0 to len(B)-1:
        L[i] = B[i]

for i=len(B) to N-1:
	L[i] = 2*(A[i] modulo MX) - MX + 1

Definition

Class:: WeirdTriangle
Method:: findAllTriangle
Parameters:: int, int[], int, int
Returns:: long
Method signature:: long findAllTriangle(int N, int[] B, int seed, int MX)
(be sure your method is public)

Notes

The reference solution would correctly solve any case that matches the constraints. It does not depend on the properties of the pseudorandom generator.

Constraints

N will be between 1 and 10,000,000,000,000,000, inclusive.
P will be between 1 and 10,000,000,000,000,000, inclusive.
K will be between 1 and 1,000, inclusive.
Q will be between 1 and 1,000, inclusive.

Examples

10

{}

1750922050

8

Returns: 4
7

{}

2075602252

1

Returns: 0
3

{}

494950342

10

Returns: 0
8

{}

70378672

1

Returns: 0
6

{}

264646134

8

Returns: 4
2

{}

676091577

4

Returns: 0
10

{}

1309482292

3

Returns: 1
2

{}

754008222

10

Returns: 0
10

{}

1205060313

10

Returns: 35
4

{}

1705037773

9

Returns: 0
5

{}

2136900802

6

Returns: 4
7

{}

1166000150

7

Returns: 0
10

{}

212246046

2

Returns: 10
8

{}

627040792

3

Returns: 4
9

{}

1411469942

7

Returns: 0
9

{}

540644843

8

Returns: 4
9

{}

653947645

9

Returns: 20
3

{}

1874331151

10

Returns: 0
5

{}

1127588379

2

Returns: 1
5

{}

378547861

10

Returns: 0
878

{}

1200488756

591919704

Returns: 7583156
783

{}

1654455436

573133184

Returns: 10507399
197

{}

1125921982

443968234

Returns: 166650
282

{}

761860527

317419489

Returns: 302621
790

{}

436660867

785215622

Returns: 7840920
722

{}

321452109

516807615

Returns: 7711320
408

{}

956976691

664151721

Returns: 1235780
129

{}

1047450488

96979331

Returns: 50116
619

{}

532092973

300991558

Returns: 4965115
710

{}

240310130

898462571

Returns: 3697960
372

{}

1865032335

945249167

Returns: 573800
505

{}

1034557013

338164467

Returns: 2081156
587

{}

518631548

104258565

Returns: 3466100
94

{}

1349479681

515252864

Returns: 15180
288

{}

500028333

709593790

Returns: 573800
497

{}

955817035

931796815

Returns: 1975354
11

{}

1201511483

546198263

Returns: 20
883

{}

1026808419

73167262

Returns: 14985824
43

{}

865795756

484167898

Returns: 1330
28

{}

1295542407

669075737

Returns: 969
610

{}

1523817532

468518033

Returns: 3428425
313

{}

1815017703

724265351

Returns: 644956
894

{}

16046445

736293260

Returns: 15187425
399

{}

54325464

578066358

Returns: 1004731
226

{}

634777297

845882894

Returns: 182104
881

{}

2146423612

868848804

Returns: 7456420
470

{}

992665623

59960574

Returns: 2135445
694

{}

1424252721

944780527

Returns: 4869634
76

{}

2132772181

522132461

Returns: 5984
711

{}

944713465

127003263

Returns: 7207200
104848

{}

1949438613

606818147

Returns: 15760547427720
193189

{}

14869290

545323634

Returns: 142814623706531
163115

{}

650693027

217231727

Returns: 87827649363146
151685

{}

43132439

803334472

Returns: 49279084910230
100670

{}

602849813

590338671

Returns: 15661127337064
155373

{}

1377440638

458299728

Returns: 63947649101160
116625

{}

2023748507

948952604

Returns: 23306461165120
117828

{}

1952174195

597021011

Returns: 23802971441040
108294

{}

945090185

840301273

Returns: 14842852869456
159475

{}

361914252

218627967

Returns: 79659162303445
152070

{}

1112731298

362351933

Returns: 70771934546764
156199

{}

1621359950

297472662

Returns: 72969341185884
165362

{}

1373975591

532784606

Returns: 92369524241180
105087

{}

678203608

736355672

Returns: 22360447539144
126115

{}

1280364321

247574369

Returns: 37155139414540
164272

{}

271121615

928731693

Returns: 59937103361464
150902

{}

1514948843

626995903

Returns: 47937783289165
115788

{}

1298226314

382868759

Returns: 26070880057160
168295

{}

944297987

262279642

Returns: 93660826203021
145379

{}

420641150

766472152

Returns: 51636912016105
186943

{}

53152274

686746176

Returns: 121143948351436
186716

{}

1470432491

264076384

Returns: 128532687331660
176665

{}

1147998265

317445694

Returns: 103296292581790
181433

{}

1539006921

702607738

Returns: 117692969589325
137177

{}

1934432670

611254313

Returns: 34913125159935
198346

{}

793053933

821993910

Returns: 99927931420324
194363

{}

1188980791

756851177

Returns: 127890423877600
143308

{}

1289281920

215425689

Returns: 61064234296010
170485

{}

2027162583

940892359

Returns: 68370348890304
160859

{}

1096150947

583509508

Returns: 64724322028159
200000

{}

1357410167

1000000000

Returns: 134735254241210
200000

{}

1841327620

1000000000

Returns: 134284499743926
200000

{}

369638263

1000000000

Returns: 134245539476244
200000

{}

1869900635

1000000000

Returns: 134561767948630
200000

{}

665449132

1000000000

Returns: 133877952998159
200000

{}

1341492706

1000000000

Returns: 135113101654444
200000

{}

2132616390

1000000000

Returns: 135400215268220
200000

{}

925114302

1000000000

Returns: 133618884593649
200000

{}

629354088

1000000000

Returns: 134301817837760
200000

{}

344393154

1000000000

Returns: 133886594373840
200000

{}

263564335

1000000000

Returns: 134579109872480
200000

{}

1120867350

1000000000

Returns: 132865177840724
200000

{}

1576180211

1000000000

Returns: 134267183138924
200000

{}

1747486995

1000000000

Returns: 135239207594396
200000

{}

1905566284

1000000000

Returns: 133817473779240
200000

{}

862900849

1000000000

Returns: 134094098960584
200000

{}

1250058840

1000000000

Returns: 135034868445400
200000

{}

1089798308

1000000000

Returns: 135413275542336
200000

{}

1197974970

1000000000

Returns: 133990319887820
200000

{}

2144832642

1000000000

Returns: 134813371696475
200000

{}

1400364773

1000000000

Returns: 131716432167320
200000

{}

2029146920

1000000000

Returns: 134011936110780
200000

{}

1655267225

1000000000

Returns: 135670298301740
200000

{}

350219294

1000000000

Returns: 134345119586405
200000

{}

1045239213

1000000000

Returns: 135047905215854
200000

{}

219528633

1000000000

Returns: 132088616998591
200000

{}

2011090959

1000000000

Returns: 134774309195660
200000

{}

1468167105

1000000000

Returns: 135300114397395
200000

{}

187060233

1000000000

Returns: 135849098736186
200000

{}

977976402

1000000000

Returns: 133623199659300
200000

{}

2072095429

1000000000

Returns: 135805474397901
200000

{}

412774151

1000000000

Returns: 134974041276620
200000

{}

2125840146

1000000000

Returns: 133942772379724
200000

{}

540967508

1000000000

Returns: 134822053277100
200000

{}

170509160

1000000000

Returns: 135060942825360
200000

{}

471757619

1000000000

Returns: 134016259634335
200000

{}

306130985

1000000000

Returns: 134457747690266
200000

{}

133300994

1000000000

Returns: 133795878473180
200000

{}

1053264425

1000000000

Returns: 134206586745045
200000

{}

1878683563

1000000000

Returns: 133502412933240
200000

{}

1202573680

1000000000

Returns: 134340788992760
200000

{}

1783925253

1000000000

Returns: 135617996162320
200000

{}

570529854

1000000000

Returns: 134566103289916
200000

{}

1894469241

1000000000

Returns: 133265365250280
200000

{}

1810761295

1000000000

Returns: 132933970147780
200000

{}

1500046312

1000000000

Returns: 133929806830005
200000

{}

1845972063

1000000000

Returns: 135587492789476
200000

{}

100541644

1000000000

Returns: 133450669483820
200000

{}

637357039

1000000000

Returns: 135465525037150
200000

{}

2092373660

1000000000

Returns: 134739593307956
200000

{}

980055881

1000000000

Returns: 135792388917800
200000

{}

1301607285

1000000000

Returns: 134765629664764
200000

{}

1298279874

1000000000

Returns: 134184949595060
200000

{}

1745660406

1000000000

Returns: 134739593307956
200000

{}

1137842239

1000000000

Returns: 134657166968489
200000

{}

823326571

1000000000

Returns: 133774285490595
200000

{}

1727941113

1000000000

Returns: 133446358133309
200000

{}

835551276

1000000000

Returns: 135004452577169
200000

{}

1805134212

1000000000

Returns: 134730915267620
200000

{}

378702407

1000000000

Returns: 134375436347824
200000

{}

1399612940

1000000000

Returns: 135740055403036
200000

{}

1415003740

1000000000

Returns: 134418753918284
200000

{}

1000635618

1000000000

Returns: 136727930133964
200000

{}

843485896

1000000000

Returns: 133239522491365
200000

{}

339297542

1000000000

Returns: 134947978082820
200000

{}

857122854

1000000000

Returns: 135000107826016
200000

{984318927, 276683799, 537606889, 345598068, 319665682, 925880661, 918162212, 205615200, 417866444, 288849361, 651164576, 43836185, 83709695, 951092754, 271997836, 170681446, 656404863, 632136226, 104326044, 633925452, 200719182, 466081518, 408275179, 490432853, 387286117, 12845510, 958433643, 144755732, 985359531, 972181164, 279894601, 572306860, 299008902, 556356824, 266164049, 924537189, 233087990, 983993523, 850401612, 844772997, 444573491, 619485010, 842366007, 423229812, 119961382, 367702065, 230508372, 896650539, 764997128, 811489387, 326089113, 918907360, 911415908, 77759800, 31777102, 78799893, 944025028, 527678321, 749729433, 629787602, 993762040, 551064628, 29160255, 385576524, 21977171, 894099937, 97274455, 761943618, 880152010, 655594069, 404088197, 540614434, 264136423, 671365064, 432932637, 327608327, 625017379, 352265226, 688993713, 665911374, 135388687, 228135002, 477855651, 334518329, 251258840, 717797956, 160128989, 523449605, 382888282, 326305129, 53478520, 646812009, 762342359, 620808336, 632743553, 193029272, 145880074, 388948384, 443844578, 710303617}

1265206609

1000000000

Returns: 135966931111680
200000

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}

79772418

1000000000

Returns: 134327797770211
200000

{-893407457, -210839383, -366045207, -110269421, -343408817, -385872951, -384139358, -946502183, -637952935, -748037738, -446672845, -343351919, -166356557, -695052450, -100532707, -523414318, -143645646, -459557726, -106127319, -374503879, -161046129, -576481927, -632006091, -970892592, -518340399, -493646128, -250287549, -320497114, -582006821, -124739221, -60895614, -991857462, -168030565, -515934470, -527248709, -347189703, -499695231, -351486947, -75821041, -739598422, -398068283, -868308617, -9304690, -811517391, -508393875, -840650024, -633188511, -852891883, -969204972, -985672256, -968173052, -702846104, -832791731, -653358308, -329348626, -89752026, -370039030, -247079471, -307662208, -625157659, -962226996, -33106926, -768172664, -87554133, -367672171, -709127843, -652746619, -800888813, -294375882, -506867661, -175532033, -843152922, -670255444, -18806398, -129099879, -1402459, -210528658, -560227844, -491608326, -437451061, -912721696, -843167471, -645269876, -448420540, -22076158, -778220396, -293501427, -584335233, -522370692, -205280400, -436867751, -339844838, -757711291, -93598233, -980699401, -134620042, -973646635, -255275719, -247172934, -609073943}

1713629187

1000000000

Returns: 133964383488729
3

{-2, -3, -5}

0

10

Returns: 0

L = B = {-2, -3, -5}. The only triple of indices is (0,1,2), but the corresponding side lengths are -5, -8, and -7. A non-degenerate triangle must have positive side lengths, so there are no valid triples of indices and the answer is zero.
4

{1, 4, 6}

200

100

Returns: 1

Here, L = {1, 4, 6, -45}. The triple (i,j,k) = (0,1,2) gives us edge lengths 5, 10, and 7. These are indeed side lengths of a non-degenerate triangle. For any other triple of indices two of the side lengths will be negative, so there are no other valid triples.
3

{2,10,16}

0

20

Returns: 1

Here we can prove that the triplet (0,1,2) is valid, so the answer is 1.
2

{5,6}

0

10

Returns: 0

Since N=2, there are no triples of indices, hence the answer is zero.
200000

{}

777818934

1000000000

Returns: 133390319026380

Note that B may be empty.
200000

{ }

777818934

1000000000

Returns: 133390319026380
200000

{-2, -3, -5 }

0

10

Returns: 166386823420740
5

{0, 0, 0, 0, 0 }

0

30

Returns: 0
3

{-2, -3, -5 }

0

10

Returns: 0

Statistics

Problem Statement for "WeirdTriangle"

Problem Statement

Definition

Notes

Constraints

Examples