TopCoder Statistics - Problem Statement

Problem Statement

You are given an array A that contains N integers, and a positive int limit.

We will use the term subarray to denote any non-empty contiguous segment of the array A. Two subarrays are distinct if they start or end at a different index in A. (Distinct subarrays may contain the same sequence of elements.)

A subarray is called modest if the product of all its elements doesn't exceed limit. Note that a subarray with a negative product is always modest.

Count and return the number of distinct modest subarrays in the given array A.

To keep the input small, the array A is given in the following format: You are given a non-empty int[] Aprefix and ints spread and offset. Use the following pseudocode to generate A:

p = length( Aprefix )
for i = 0 .. p-1:
    A[i] = Aprefix[i]
seed = abs( A[p-1] )
for i = p .. N-1:
    seed = (seed * 1103515245 + 12345) modulo 2^31
    A[i] = (seed modulo spread) + offset

Definition

Class:: ProductThreshold
Method:: subarrayCount
Parameters:: int, int, int[], int, int
Returns:: long
Method signature:: long subarrayCount(int N, int limit, int[] Aprefix, int spread, int offset)
(be sure your method is public)

Notes

The reference solution does not depend on any properties of the pseudorandom generator.
The last two constraints imply that all elements of A will always be between -10^9 and 10^9, inclusive.

Constraints

N will be between 1 and 100,000, inclusive.
limit will be between 1 and 10^9, inclusive.
Aprefix will contain between 1 and min(N,500) elements, inclusive.
Each element of Aprefix will be between -10^9 and 10^9, inclusive.
spread will be between 1 and 2*10^9 + 1, inclusive.
offset will be greater than or equal to -10^9.
spread-1+offset will be less than or equal to 10^9.

Examples

5

5

{1,2,3,-4,5}

1

1

Returns: 13

We are given the entire sequence A in the array Aprefix. Modest subarrays are subarrays with product not exceeding 5. All 8 subarrays that contain the element -4 are modest. Additionally, subarrays {1}, {1,2}, {2}, {3}, and {5} are modest. That gives us a total of 13 modest subarrays.
10

8

{2,2,2,2,2,2,2,2,2,2}

1

47

Returns: 27

Each subarray of length 1, 2, or 3 is modest. No other subarray is modest.
20

999888777

{47}

7654321

1

Returns: 21

The array A you should generate looks as follows: {47, 4139827, 3367492, 890643, 113351, 7314474, 5690828, 5571137, 3860068, 2551091, 3662623, 379062, 3134150, 5405018, 2518354, 5390370, 4216741, 5130660, 4174938, 2342215}. Each one-element subarray is modest, and the subarray {47, 4139827} is also modest.
5

8

{3,0,3,0,3}

47

47

Returns: 15

Each subarray of the array {3,0,3,0,3} has a product that does not exceed 8.
1000

1

{-1}

1

2

Returns: 1000

This array looks as follows: {-1, 2, 2, 2, 2, ...}. Only the substrings that contain the element at index 0 are modest.
100

47

{1}

1

1

Returns: 5050
99845

172004433

{757852577}

302408965

555028144

Returns: 0
99856

77724106

{-156890680}

1802972625

-881668151

Returns: 2492810093
99018

208992476

{-202829192}

345544458

-480429170

Returns: 2451190590
99045

320125150

{1}

2

0

Returns: 4905005535
99057

702621676

{271762128}

406686405

-99655695

Returns: 2453193030
99774

537724598

{0}

3

0

Returns: 4977475425
99588

426511205

{-227212422}

840616349

-911795186

Returns: 2479492230
99912

435485192

{37961475}

739407229

-545439652

Returns: 2495675312
99482

905568839

{-208322112}

1465369421

-725491665

Returns: 2474251193
99150

756423687

{848255057}

262345785

603852457

Returns: 58920
99306

683785224

{-2}

2

-2

Returns: 2468349095
99380

705219027

{-1}

1

-1

Returns: 4938241890
99422

834545592

{-131465952}

49999769

-144333910

Returns: 2471233232
99108

551799677

{-838794650}

445996712

-932515447

Returns: 2455648470
99437

233099500

{633477497}

310579493

328251536

Returns: 0
99819

572269799

{446628851}

765347782

23848791

Returns: 76444
99986

92157021

{1}

1

1

Returns: 4998650091
99290

885050008

{-209193157}

768325684

-879848184

Returns: 2464675670
99885

681737737

{5274431}

891005113

-422346591

Returns: 2494326069
99387

930726681

{848694200}

1325851054

-347297535

Returns: 2469375279
99726

390747231

{407151756}

40189822

392297362

Returns: 0
99947

708119189

{181115754}

31227628

170683966

Returns: 99947
100000

27370081

{-291269111}

2000000001

-1000000000

Returns: 2499998139
99497

501900836

{356513461}

460368686

-91161516

Returns: 2475018307
99833

725494757

{256692856}

635749346

-335306171

Returns: 2491746179
99428

491649947

{419185043}

912407980

-109934952

Returns: 2471124047
99949

400742920

{30699504}

182758146

-99570731

Returns: 2497500053
99263

542191161

{-521606591}

402483918

-786734535

Returns: 2463335424
99760

686351450

{-679763776}

636540532

-800293690

Returns: 2488064280
99651

136831963

{538389819}

1283658508

-647287324

Returns: 2482642632
99908

246848320

{-2}

3

-2

Returns: 4990854186
99901

602645330

{-240645271}

170462107

-394797094

Returns: 2495102401
99057

392442147

{33358748}

1212137494

-897491233

Returns: 2453137319
99265

679706936

{-2}

1

-2

Returns: 2464824203
99526

712384352

{1}

5

-2

Returns: 4952762101
99612

451271020

{-573544062}

962704638

-933062131

Returns: 2480690093
99623

46848457

{179822279}

183335348

54906749

Returns: 0
99697

907417408

{607983929}

10213891

597842632

Returns: 99697
99484

738264022

{514251866}

207105816

489542610

Returns: 99484
99739

825703950

{205646926}

920094926

-676167797

Returns: 2487030794
99639

981333188

{277056509}

469811285

-17566343

Returns: 2482065477
99161

372367589

{415334278}

1374988581

-722913986

Returns: 2458288839
99842

930351686

{1}

2

1

Returns: 5839077
99787

214535844

{-786717963}

16749284

-792982339

Returns: 2489411236
99047

497431957

{-456454765}

745754657

-730389391

Returns: 2452627851
99271

78991334

{-706952522}

128235658

-789185472

Returns: 2463732496
99847

13994817

{-413947828}

218656292

-628678655

Returns: 2492405776
99422

70041985

{230936738}

57012000

204146300

Returns: 0
99289

668933209

{-189977117}

410843407

-350176521

Returns: 2464638182
99928

341934531

{232839291}

185447317

72843414

Returns: 99928
99795

436930186

{155816593}

1732255087

-787403138

Returns: 2489795453
99799

748067975

{4111247}

700575494

-24511368

Returns: 2490014135
99154

379160100

{384216247}

187627330

349992366

Returns: 16113
99350

777565500

{0}

2

-1

Returns: 4935260925
99059

328189558

{-391614116}

721300329

-482155816

Returns: 2453252862
99499

407935618

{-428069394}

412834960

-515818612

Returns: 2475062500
99374

640758861

{2}

1

2

Returns: 2881440
99994

533887763

{666768745}

238562363

542878885

Returns: 0
99300

795097653

{-1}

4

-1

Returns: 4930294650
99513

660079438

{0}

1

0

Returns: 4951468341
99983

768838872

{135970066}

626344826

-331323868

Returns: 2499229727
99263

877318246

{269744854}

738331512

-277209964

Returns: 2463331120
99890

122036539

{-623406681}

606395373

-786878409

Returns: 2494552970
99367

892749216

{-659571465}

765734594

-693729716

Returns: 2468505921
99296

275205851

{192535108}

555382279

-104533773

Returns: 2464980918
99662

107180954

{1}

3

-1

Returns: 4966306953
99392

869435486

{-7406018}

1604146192

-851845720

Returns: 2469752831
99706

145545806

{-241902572}

507029289

-630007779

Returns: 2485371462
99696

366294969

{0}

4

-2

Returns: 4969696056
99148

398694542

{524594073}

761376799

153951229

Returns: 33776
10

8

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

1

47

Returns: 27
100000

1

{-1, 1, 1, 2, -1, 3, 2, 2, -1, 0, 0, 2, -1, 0, -1, -1, 2, 3, 2, 2, 2, 3, 2, 1, 0, 1, 3, 1, 0, 2, -1, 0, -1, 2, 3, 0, 3, 2, 0, 3, 0, 1, -1, 2, 0, -1, 2, 3, -1, 3, -1, -1, -1, -1, -1, 0, 2, 3, -1, 3, 2, 0, 2, -1, 0, 3, 0, -1, 3, 3, -1, 1, 1, -1, 0, -1, 1, 0, 3, 3, 1, 0, 1, 2, 1, 3, 0, 1, -1, 1, 0, 2, -1, 0, 0, 2, 0, 1, 2, -1, 3, -1, 2, 0, 1, 3, 0, 1, 1, 1, 2, -1, 3, -1, -1, 2, 0, 0, -1, 1, -1, 2, 1, 1, -1, 2, -1, 0, 2, 0, 2, 1, 2, 0, 2, 0, 1, 0, -1, -1, 2, 2, 1, 3, 0, 1, 3, 1, -1, 3, 3, 0, -1, 1, -1, -1, -1, 0, 2, 2, 3, 0, -1, 1, -1, -1, -1, 3, 2, -1, 3, 1, 0, 2, 2, 1, -1, 2, 3, 0, 3, 3, 3, 3, 2, 3, 0, 2, -1, 3, 3, 0, 2, 0, 0, -1, 1, 0, 3, -1, 3, 0, 3, -1, 3, -1, 3, -1, 2, 2, 2, 3, 3, 1, 0, 1, 0, 1, 2, 3, 3, 1, -1, 3, 2, 0, 3, 1, -1, 2, -1, 0, 0, 3, 2, 0, 3, 1, 2, 3, 1, 0, 0, 3, 2, 1, 2, 0, 0, 0, -1, 1, -1, 2, 0, 0, 0, 1, -1, 2, 2, -1, 3, 3, 1, 3, -1, 0, 2, 2, 2, 0, 0, 3, 1, 3, 2, -1, 0, 0, 3, 2, 3, 0, 0, 1, 3, 2, 1, -1, 0, -1, -1, 2, 0, 3, 1, 1, 2, 2, 1, 0, 0, 3, 1, 2, -1, 1, -1, 2, 2, 3, 1, 3, 2, -1, 1, 1, -1, 3, 3, 3, 0, -1, 1, 1, 0, 0, 0, 3, 3, 0, -1, -1, 1, 3, -1, 3, 2, 0, 2, 1, 1, 1, 2, -1, 1, -1, -1, -1, 0, 3, 3, 3, 0, 2, 3, 2, 3, -1, 1, 0, 2, -1, 2, -1, 0, 3, -1, -1, 1, -1, 3, 3, 1, 1, 1, 0, -1, 1, 0, 2, 2, -1, 2, -1, 2, 1, 2, -1, 3, 1, 2, 2, 1, 0, 2, 3, 1, -1, 0, 3, -1, -1, 3, 3, 1, 2, 0, 1, 1, 3, 0, -1, 1, 0, -1, 1, 2, -1, 1, 1, 2, -1, 1, 1, 3, 2, 2, 0, 2, 3, 0, 0, 3, 1, -1, 3, -1, 0, 2, 1, 2, 3, 1, -1, 1, -1, 1, 1, 1, 1, 1, 1, 1, 3, -1, 2, 1, -1, -1, 0, 1, 2, 1, 2, -1, 3, 1, 1, 0, 0, 3, 0, 1, 2, 0, -1, -1, 2, 3, 2, -1, 0, -1, -1, 0, 1, 2, 2, -1, -1, 0, 1, 2, -1, -1, 2, -1, 0 }

3

-1

Returns: 5000049162
5

5

{1, 2, 3, -4, 5 }

1

1

Returns: 13
100000

10

{1 }

1

1

Returns: 5000050000
100000

1

{1 }

1

-1

Returns: 5000050000
100000

100000

{1 }

200000

-100000

Returns: 2500083445
100000

20000

{999 }

9182932

-2827381

Returns: 2500034991
100000

100

{0 }

1

0

Returns: 5000050000
100000

100000000

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

1231

-141

Returns: 4933739368
6

5

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

2

2

Returns: 18
100000

10000

{0 }

201

-100

Returns: 4990614009
100000

1000000000

{0 }

1

1

Returns: 5000050000
100000

100000000

{1 }

1

1

Returns: 5000050000
100000

1000000000

{1 }

1

1

Returns: 5000050000
100000

123456789

{42, 13, -7, 0, 55, 101, 1337, 666, 123, 456, 789, 12345, 67890, -13, -17, 5, -42, 11, 0, 77, 777777777, -888888888, -999999999, -666666666 }

99999937

73472039

Returns: 2350800
98980

324243

{2, 5, 0, -1 }

654346

-354346

Returns: 2449500646
100000

2

{1 }

1

1

Returns: 5000050000
100000

47

{1 }

1

1

Returns: 5000050000
100000

995959113

{568009989, -457264404, 645908748, 752768535, 653764759, 833336657, 269071273, 995959113, -689947107, -163968554, -243191514, 270944826, 142281858, 245661295, -733508702, 55046011, -970150832, 940779439, -194828409, 550865646, -792799694, 52803612, 17263201, 459483494, -200174938, 651572788, 438353993, 674045337, -529855474, 603283730, -778575334, -232016748, -120495950, 219414106, -747780797, 65873915, -898282585, -785715569, -294015648, 172718242, -250126090, -780433670, -838304396, 766779451, 810328684, 396912547, -661806395, -478942167, 217798398, -618762372, -738094252, 873231219, 516796118, 326996126, -737183240, -516048428, -614048258, 678644246, -448417297, 897316776, 380997970, -192736001, 369127583, -347966441, 80213232, 930224870, -584121491, 777448238, 727393108, -586567300, 408419355, -94884461, -293515621, 805026346, 630448989, -820541824, -570668998, -751566358, 273212583, -629698522, -106090982, -766933821, -730061535, 960734398, 268840671, -166438984, -869722579, -147605952, -997501622, 307249230, -282855854, -436947303, 478330953, -840108015, -658253328, 861625471, 464503125, 891479273, 944349235, 598164360, -55480653, 14513675, 879093985, 105896749, -176243023, 629200811, -655326434, 148901578, -172565377, -867045426, -487866661, 155003842, 82555047, 206050877, -869586211, 932890560, -651020502, 517282197, 460818712, -920396487, -668515460, -513448574, 899339083, -239746931, 431107566, 840684271, -112625239, -746698141, -58303563, -387466735, -238075881, -733174281, -251480558, -534715948, 1180508, -491147031, -4441413, 462495416, 548756502, -417416798, 650098898, 435428889, -665336364, -511693046, -844677592, 86195241, -313599251, 829401073, -168284196, -875027113, -19130570, 770566204, 488795305, -598414386, 300469341, 920848842, 165720852, -22625819, 470018324, 807777414, -610782253, 143694526, 530603363, 753295963, -58492491, 681360000, 743855324, 835033547, -279552664, 967246916, 423182374, -694403651, -774415167, -859738849, -817772084, 922772882, -188706052, 199294012, -553239218, -17077306, -953634014, 349991573, -179237550, -573964994, 71173763, -829721522, -251555020, -847539869, 296267182, -141295541, 75719099, 983605169, -595128902, 617512915, 500917489, 632626162, 726782064, 432593735, -861219135, -798412227, -804212067, -105458849, 673707858, -817569441, 430262619, -480726328, -936267248, 243547166, 755767083, -358701519, 496257365, -968409957, -805594965, -884456573, -779824461, -737661999, 153428723, -213904851, 850128352, -734412998, -461435502, 912131740, 586465343, -392286576, -289586656, 532218570, 324787975, 544908208, -367727744, 232689134, -892702190, 20553397, 273225041, -851150524, -137496739, 368426646, -957922867, 206782750, -6840642, 355839463, 811822283, -849949295, -69045635, -526031335, -297132830, 240404445, -689962364, 423168316, 132471654, 253317965, -90107900, 162288467, -364119292, -677450291, -374432815, -983602171, -834606955, 724579890, 856671719, -631219681, -842317497, -800600819, -774304264, 575909911, -193065250, -514708424, 874867766, 749917483, -843707319, 323788866, -217699313, 661701058, -821002066, 51702028, 73540564, -699507185, 555518717, -655478878, -600663297, 967688927, -680585862, -813428605, 185580096, -878351278, -277440255, -738052204, -956047995, -110112655, -446314640, 63616784, 127226214, 456924672, 335604666, 53207619, 944382078, -964206299, 310762479, 206791305, 699584122, 495411802, 928258270, -791196370, -653965589, -565394243, 859442818, 675204694, 204474924, 550950621, 975418659, 454390807, -48592746, -732924921, 504585297, -407967398, -12926788, -714834187, 795727021, 576208088, 741623613, 402265508, -96261039, 231322186, -905514941, -28932131, -293512312, 750715573, 73104711, -746175969, 354084903, 962282673, -139236197, -442622882, -75425599, -324976084, 957250549, 883943748, 79347910, 58750532, 327924837, -30433312, 823092588, 744781894, 62343280, 884162180, -222824554, 139373621, -886450875, -837788135, -732377439, -295445312, 623247180, 230051753, 194571865, -463640054, -107301746, 550959491, 492182777, 613734951, -459785661, -804468277, 64021507, -805685536, -767680762, -486178376, -37141300, -112464432, 355209375, 195833114, -915662663, -521486050, -697247984, 577156768, -373457180, -69248716, 509174918, 33148371, -92399057, 607260311, -910152085, 860352016, -898100701, -199396110, 816589058, 709552443, -182836415, 47844957, 812486319, 673244992, 484162542, 227238926, 155654922, -196731952, -844863413, 210556300, -720368476, 511523858, 119575732, -891739498, 830902426, 948467821, -930360932, -108388949, 418273480, 346816763, -129520564, -621755642, 942895092, -867436949, 432888, 835988029, -411329607, 94680947, 102378431, -31144, -272958596, 579550689, 659878598, 470557190, 985098122, 997506640, 260272598, 430137071, -31599869, -582904631, 985949536, 867702820, 561750629, -346089082, 32417553, 259422648, 279093428, -246235182, -991666162, 440958824, -176235197, 172294412, 833938637, -138515339, -246391774, 550024650, 770323599, -930238829, -366009563, -989618407, 905229949, -145900038, 358534540, 900137443, -990417314, -918442855, 299855956, -51161494, 115376883, 578172522, 326908185, -730845712, 861769712, 535250144, -936275847, 259579287, -715327618, 677720603, 395719848, 86259698, -966827135, -949998662, -511831097, 759676844, 320953533, -487877042, 858717154, 901164684, 917879174, -648959432, -162420337, 409445317, 925479191, 308664023, -952247646, -976901846, 682809107, -535978337, 252816377, -285713280, 322864839, 910364771, -691298545, 645429788, -812361272, -102138767, -537568966, -179986065, 512772054, 394427716, -551772182, -998386245, 672707727, 325951102, -171501598, 254929962 }

553774280

-654008054

Returns: 2500050198
100000

1000

{0, 1 }

47

-7

Returns: 4997818854
100000

2

{-1 }

1

-1

Returns: 5000050000
100000

9

{1 }

21

-10

Returns: 4999131009
100000

1000000000

{1, 2 }

10

-5

Returns: 5000013293
100000

1

{1 }

1

1

Returns: 5000050000
10

3

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

100

0

Returns: 48
33

7

{1, -1, -1, 1, -2, -1, 1, 1, -1, 2, 0, -1, -1, 1, 1, -1, -2, -1, -1, 1, 2, 1, 1, -1, 1, -1, 3, -1, 2, 1, -1, -1, 1 }

10000

0

Returns: 536
100000

1000000000

{-1 }

1

-1

Returns: 5000050000
3

1

{-2, -2 }

1000000000

0

Returns: 3
100000

100000000

{1, 2 }

50

60

Returns: 398803
100000

2

{4, 3, 1, 1, 1, -1, -1, -1, 1, 1, 2, 3, 4, 3, 1, 1, 1, -1, -1, -1, -1, 1, 1, 2, 3 }

5

-2

Returns: 4999940649
100

2

{5 }

3

-1

Returns: 5047
2

1

{1 }

1234567890

-300000000

Returns: 1

Statistics

Problem Statement for "ProductThreshold"

Problem Statement

Definition

Notes

Constraints

Examples