Problem Statement
You are standing on coordinate 0 of the real axis.
Somewhere along the axis there are also N boxes, numbered from 0 to N-1. Initially, box i is located at the integer coordinate B[i]. These coordinates are not necessarily distinct - some boxes may share the same starting coordinate. Arbitrarily many boxes may share the same coordinate at any moment.
Your task is complete when all the boxes are standing on the ground at the same integer coordinate. You have to complete this task as quickly as possible. You get to choose that final coordinate and the specific strategy used to get all the boxes to that coordinate. Only the boxes matter, your final position does not: as soon as all the boxes are at the same coordinate, the task is complete regardless of your position at that moment.
At any moment, you can spend one second to move one step left or right (i.e., increase or decrease your coordinate by 1).
You can also instantly pick up a box that's at your current coordinate or put down the box you are currently carrying. You cannot carry more than one box at the same time.
Calculate and return the minimum time needed to finish your task.
In order to keep the input size small, we will use a pseudorandom array B. Please use the pseudocode below to generate it.
for i = 0 to length(Bprefix)-1:
B[i] = Bprefix[i]
state = seed
spread = bhi - blo + 1
for i = length(Bprefix) to N-1:
state = (state * 1103515245 + 12345) modulo 2^31
B[i] = blo + (state modulo spread)
Definition
- Class:
- CollectBoxes
- Method:
- collect
- Parameters:
- int, int[], int, int, int
- Returns:
- long
- Method signature:
- long collect(int N, int[] Bprefix, int seed, int blo, int bhi)
- (be sure your method is public)
Notes
- The reference solution does not use the assumption that B is pseudorandom. It would correctly solve the task for any array B of the maximum allowed length.
- The pseudocode used to generate B guarantees that all the generated values will lie between blo and bhi, inclusive. Note that the values in Bprefix may lie outside this range.
Constraints
- N will be between 1 and 500,000, inclusive.
- Bprefix will have between 0 and min(N, 200) elements, inclusive.
- Each element of Bprefix will be between -10^9 and 10^9, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- blo will be between -10^9 and 10^9, inclusive.
- bhi will be between blo and 10^9, inclusive.
Examples
2
{11, 10}
0
0
0
Returns: 11
There is a box at coordinate 11 and another at coordinate 10. The optimal solution is to make 10 steps right, pick up the box that's there, take another step right, and put down the box you're carrying.
5
{10, 10, 11, 10, 10}
0
0
0
Returns: 12
Here the optimal strategy is to take 11 steps right, pick up the only box that's at coordinate 11, take a step back, and put the box down.
2
{-10, -11}
0
0
0
Returns: 11
Remember that coordinates of boxes can be negative. This is essentially the same as Example 0 but in the opposite direction.
2
{-47, 47}
0
0
0
Returns: 141
This test case has two optimal solutions: you go to one of the boxes, pick it up and bring it to the other box.
9
{10, 20, 30}
47
-20
100
Returns: 322
Watch out for integer overflow when generating the array B. The array you should get for this example looks as follows: B = {10, 20, 30, 3, 34, 34, 59, -1, 81}.
1
{42}
0
0
0
Returns: 0
2
{47, 47}
3
3
3
Returns: 0
3
{-5, -5, -5}
56
66
77
Returns: 0
3
{1000000000, -1000000000, 1000000000}
47
47
47
Returns: 3000000000
Watch out for integer overflow also when computing the answer itself: it does not always fit into a 32-bit variable.
500000
{}
47
-1000000000
1000000000
Returns: 526657236972880
499999
{}
43
-1000000000
1000000000
Returns: 526120454326314
1
{-244415920}
268543586
-76182073
188933013
Returns: 0
2
{225763432, -262404342}
1105644294
-169875016
100465896
Returns: 713931206
3
{321907874, -912149200, 707427139}
1797583853
-949190840
414390307
Returns: 2917244804
4
{321907874, -912149200, 707427139}
1797583853
-949190840
414390307
Returns: 3601855988
4
{-433479563, 701332470, 34126712, 554472260}
39237771
751726524
970109601
Returns: 2755842902
5
{218843449, -81522475, -505977928, -489453286, 123712903}
1542245923
-480204100
-50337639
Returns: 2594452657
14
{218843449, -81522475, -505977928, -489453286, 123712903}
1542245923
-480204100
-50337639
Returns: 4986223959
6
{-196481985, 539170708, 476612671, -240966370, 290585286, -265745783}
841741944
-487569197
693525474
Returns: 3728540320
9
{-196481985, 539170708, 476612671, -240966370, 290585286, -265745783}
841741944
-487569197
693525474
Returns: 5915554578
7
{-282894943, -789660271, -220809979, 242001581, -176271038, 91578333, 159916785}
1085916001
-791482223
393305594
Returns: 3397452746
8
{990747172, 501538326, 815967122, -280895907, -530659052, 11529699, 598112195, -763463914}
1789542187
-241833013
298487089
Returns: 8438169652
9
{887959676, 659867242, 739380085, -486788011, 737557846, 192424730, 979997081, -438240430, -233470194}
172270288
-329541336
39266199
Returns: 7962069944
10
{674316394, -150717718, -441130792, 568116295, 115400992, 717159364, -525541371, 302115634, -755325017, 347346664}
889428824
-184241253
42385974
Returns: 8430620880
11
{296049526, 988059624, 198388330, -679590550, -46761288, -967379265, -634292933, 174657722, 346809166, 727290075, 635244579}
355519765
-839787498
-429306377
Returns: 10095250238
12
{745166065, 336837972, 174382664, 23297791, 680053598, 722004112, -64528369, -214925920, 972420610, 630323715, -928742964, 305220252}
1138224035
383606019
931003043
Returns: 9247367264
13
{110176952, 447640732, 953124880, 13204312, 963706465, 520817493, 370790402, 714714006, -323557564, 781400885, -952254171, 238927994, -478119486}
907804592
-257047206
-73065678
Returns: 11175262446
14
{-620588111, 8872672, 977756959, -573345557, -725387768, -788649548, -706525175, 568563933, 685996642, 223252306, -261147456, 132585332, -157411936, -767888905}
1146177193
-999029554
-46687623
Returns: 13505149400
21
{-620588111, 8872672, 977756959, -573345557, -725387768, -788649548, -706525175, 568563933, 685996642, 223252306, -261147456, 132585332, -157411936, -767888905}
1146177193
-999029554
-46687623
Returns: 17494297076
15
{-855765286, -207044734, -955500684, -432532202, -910438738, -698410786, -610920584, 587302245, 98777291, 794376754, 54378527, -568037045, 681659391, 659732697, 743089873}
2124698091
-25920656
134461676
Returns: 17094799472
16
{218346924, -978552345, 492576398, -841418179, -623927783, 794808693, -676659381, 979672758, 167037723, -273414772, 364779377, 862060937, -899743159, 884503005, 335838501, -496412373}
263002937
-735541697
-186685354
Returns: 18893006800
18
{218346924, -978552345, 492576398, -841418179, -623927783, 794808693, -676659381, 979672758, 167037723, -273414772, 364779377, 862060937, -899743159, 884503005, 335838501, -496412373}
263002937
-735541697
-186685354
Returns: 21414062766
17
{-349895911, -884267766, 888174316, 176511143, -339293317, -486498083, 315659396, 925178406, 576287602, 148661791, -675290191, 180961941, 245021573, 637300973, -413392074, 329265128, 843188163}
346617440
54959887
208945414
Returns: 14986117989
18
{195121343, -887939001, -753908586, -112063069, -103112468, -240343423, 946926126, -349715553, 211869837, 813102598, 631496845, 50667406, 283466714, -700099444, -863556885, 90653906, -748601833, 939811981}
1981116652
402205168
689762860
Returns: 17741801568
19
{768807448, -961607802, -66740280, 738761557, 211030055, 121255140, 639419634, -857854825, 678507827, 694847453, -382321406, 683079334, 513452933, 52701343, 78884025, -754910855, 621247157, -473609470, -243679816}
1422105126
-641547116
-6657619
Returns: 18195329828
29
{768807448, -961607802, -66740280, 738761557, 211030055, 121255140, 639419634, -857854825, 678507827, 694847453, -382321406, 683079334, 513452933, 52701343, 78884025, -754910855, 621247157, -473609470, -243679816}
1422105126
-641547116
-6657619
Returns: 25272965290
20
{-789147576, 440824976, -13295416, -11022626, -405604670, 370163018, 170207757, 473209613, 493100911, 479992311, 972926621, -948924258, 203017608, -593512725, 769746512, 459429568, -383554748, -912197593, 657437654, -434650045}
2073107849
-852970324
-176003241
Returns: 19080083776
29
{-789147576, 440824976, -13295416, -11022626, -405604670, 370163018, 170207757, 473209613, 493100911, 479992311, 972926621, -948924258, 203017608, -593512725, 769746512, 459429568, -383554748, -912197593, 657437654, -434650045}
2073107849
-852970324
-176003241
Returns: 27729142382
496469
{}
2050067571
-47303013
47303013
Returns: 23377925606560
497996
{}
392755518
-18936
1784871
Returns: 448419369031
457130
{}
400206914
-6
6
Returns: 2952742
488196
{}
242563618
-46570
46570
Returns: 22750929362
468987
{}
898538742
-252450649
252450649
Returns: 121317635392206
470804
{}
235240045
-15368424
14184897
Returns: 6932943106738
479976
{}
1880671616
-51
51
Returns: 24729848
458116
{}
729061624
-25005
25005
Returns: 11458448943
470512
{}
99073865
-2
2
Returns: 1129528
490172
{}
779372551
-2
3
Returns: 1469463
461528
{}
1708937855
-582193225
620809318
Returns: 255021345201232
450049
{}
1650855086
-5221776
5221776
Returns: 2350739955215
483505
{}
1720060055
829473381
870024774
Returns: 9798607312868
490454
{}
750893228
-159376807
159376807
Returns: 76565164021754
475919
{}
1406159933
-339716497
339716497
Returns: 166842504218473
476025
{}
320361304
-17
31
Returns: 11656405
456075
{}
1533974457
-405136693
240774617
Returns: 150694724240788
483803
{}
905302894
-2023
2023
Returns: 978591304
495584
{}
1036425125
0
0
Returns: 0
488607
{}
1716184327
-328247072
34516607
Returns: 87582005466125
460294
{}
454791749
105909461
410239580
Returns: 70499494841582
461019
{}
710429624
-577176581
687928699
Returns: 263260807991100
472827
{}
523104350
-2475059
2475059
Returns: 1169633015125
492036
{}
1349285998
-849921446
891808377
Returns: 452829448801557
458878
{}
1418230283
-69752548
181513990
Returns: 57204169940488
477073
{}
2107368689
935404739
935404746
Returns: 937313027
456626
{}
1885893272
-283374690
-208345325
Returns: 17078425307747
499455
{}
805196287
-11445
11445
Returns: 5711209271
491114
{}
113301998
-339
339
Returns: 166839349
468944
{}
311775786
-26356348
662912312
Returns: 166045949110588
493864
{}
27067550
-2928
2928
Returns: 1445558127
474207
{}
1592078892
294148553
294148556
Returns: 295096963
493877
{}
1286708360
-453793777
453793777
Returns: 227065226127944
477414
{}
1492517263
-3
3
Returns: 1634660
465055
{}
1162101126
-937032332
937032332
Returns: 467103179662570
451572
{}
1688417412
-157762
1816099
Returns: 445448482046
454441
{}
281126873
-10
10
Returns: 4760358
463416
{}
976808686
-3263
3263
Returns: 1512049771
450389
{}
490428354
-171405373
400151437
Returns: 124010783684927
480868
{}
920232792
-3
3
Returns: 1649292
471328
{}
1480581755
-895656803
-227850343
Returns: 162493764553851
489909
{}
939197325
-3486763
819957301
Returns: 191473723935131
462515
{}
385572705
-2
2
Returns: 1108560
469925
{}
1336545990
-7592037
48283786
Returns: 13135991798896
455893
{}
1087525279
-56
56
Returns: 25752440
474737
{}
757722369
-32726130
32726130
Returns: 15466903647364
487690
{}
822004006
-91742851
-75386943
Returns: 3994842665975
478025
{}
1787838088
-165344300
165344300
Returns: 78615430007072
497294
{}
1613667693
-294
294
Returns: 146391276
452596
{}
1037122419
-736633016
-442482161
Returns: 67470583420382
2
{100, 100 }
0
0
0
Returns: 0
2
{1, 1 }
1
1
1
Returns: 0
3
{1000000000, -1000000000, 1000000000 }
47
47
47
Returns: 3000000000
50000
{1 }
11465
0
10000
Returns: 250263956
2
{4, 4 }
1
10
20
Returns: 0
1000
{-5, 10 }
47
-20
-10
Returns: 5453