Problem Statement
Time limit is 3 seconds.
The main road on Iceland is the Ring Road: a highway loop that goes around the whole island.
There are N towns on the Ring Road. They are numbered from 0 to N-1 in the order in which the road visits them. As the road is cyclic, after town N-1 it returns to town 0.
In winter the Ring Road needs to be maintained, otherwise it won't be usable due to too much snow. For each i, we know the cost C[i] of maintaining the segment between towns i and ((i+1) modulo N). Once a segment is maintained, it can be used in both directions.
We have polled all P people who live in Iceland. For each of them we know the town L[j] where they live and the town W[j] where they work.
We want to make sure that everybody can get to work. Calculate and return the minimum total cost of doing so.
In order to keep the input data small, the values C, L and W will be pseudorandomly generated. Please use the pseudocode below.
for i in 0 .. N-1:
state = (state * 1103515245 + 12345) modulo 2^31
C[i] = 1 + ((state / 10) modulo M)
for j in 0 .. P-1:
state = (state * 1103515245 + 12345) modulo 2^31
L[j] = ((state / 10) modulo N)
state = (state * 1103515245 + 12345) modulo 2^31
W[j] = ((state / 10) modulo N)
Definition
- Class:
- IcelandRingRoad
- Method:
- solve
- Parameters:
- int, int, int, long
- Returns:
- int
- Method signature:
- int solve(int N, int P, int M, long state)
- (be sure your method is public)
Notes
- The reference solution does not depend on the input being pseudorandom.
Constraints
- N will be between 3 and 500,000, inclusive.
- P will be between 1 and 100,000, inclusive.
- M will be between 1 and 1000, inclusive.
- state will be between 0 and 2^31 - 1, inclusive.
Examples
10
2
1000
474747
Returns: 1161
The road maintenance costs are C = { 253, 325, 395, 132, 427, 50, 582, 52, 573, 747 }. There are two people. One lives in town 2 and works in town 4, the other lives in town 6 and works in town 8. The optimal solution is to maintain road segments 2-3, 3-4, 6-7, and 7-8. The total cost of doing so is 395+132+582+52 = 1161.
3
47
1000
420042
Returns: 991
Here the road maintenance costs are C = { 373, 801, 618 }. Clearly, we want to maintain roads 0-1 and 2-0, and we want to leave the most expensive road 1-2 covered by snow.
100
12
1
12345
Returns: 83
L = { 30, 17, 11, 18, 81, 1, 44, 35, 61, 41, 98, 0 } W = { 24, 28, 38, 70, 67, 88, 79, 44, 67, 61, 35, 63 } Each road's maintenance cost is 1. The optimal solution is to maintain 83 roads: the roads 61-62-...-99-0-1-...-43-44.
500000
100000
1000
474447
Returns: 249891233
499997
99997
997
2352366
Returns: 249270130
14
1
441
594466506
Returns: 110
17
5
352
276411073
Returns: 2519
19
4
402
660953937
Returns: 2350
4
7
429
707195153
Returns: 420
3
1
1
283260218
Returns: 0
18
6
560
9809442
Returns: 3903
13
5
438
247011036
Returns: 2526
10
5
527
385561480
Returns: 1724
17
2
35
602310784
Returns: 101
14
6
705
379516815
Returns: 3080
13
5
589
818082095
Returns: 2740
9
2
808
902613028
Returns: 189
4
2
342
105169864
Returns: 229
14
5
393
545789166
Returns: 2103
20
7
259
104258888
Returns: 2286
10
6
866
359552046
Returns: 2752
9
4
763
118268043
Returns: 2018
16
5
362
724619612
Returns: 1970
12
7
830
256605994
Returns: 3867
20
3
366
571965507
Returns: 2278
4
4
320
604235495
Returns: 227
15
3
968
784058147
Returns: 2523
19
7
227
651057817
Returns: 1361
6
6
862
222357206
Returns: 1671
15
4
260
648024763
Returns: 1191
20
2
455
16310367
Returns: 1729
8
5
643
863645037
Returns: 2597
5
1
273
548934239
Returns: 0
20
4
802
861002056
Returns: 3613
16
3
941
815161857
Returns: 5540
404349
497
937
760408746
Returns: 188068999
483666
1069
591
260940257
Returns: 142353818
427703
3815
982
930735750
Returns: 209690173
490674
43
482
988878479
Returns: 112868113
426040
19
140
784281966
Returns: 26173627
474661
3655
111
286544298
Returns: 26523908
458185
1
425
72117357
Returns: 34612767
448398
1
43
150794607
Returns: 1729370
423747
100000
206
840829695
Returns: 43945685
464840
100000
578
609173462
Returns: 134689062
401309
5
856
161670309
Returns: 118634581
471230
1119
899
667919250
Returns: 211227638
430736
3
127
23852118
Returns: 16766999
411611
567
901
588255571
Returns: 184276253
440326
166
564
622510786
Returns: 122486484
499932
297
577
527479943
Returns: 142601060
444920
2
424
448443766
Returns: 38949578
446365
1012
613
149950278
Returns: 136311912
408327
80880
925
495279163
Returns: 189099634
485583
16969
446
869380778
Returns: 108489969
473915
74211
801
847423726
Returns: 189903411
437700
40247
774
263195265
Returns: 169424011
446162
1365
474
24260175
Returns: 105633916
477034
15
963
494488687
Returns: 199017393
436279
1
844
729714784
Returns: 9618627
437624
3
556
518276962
Returns: 37810361
450292
4
901
559272524
Returns: 95587829
492938
56489
593
334682124
Returns: 146324130
454014
75
962
110252490
Returns: 211790758
467160
926
977
357293695
Returns: 227399868
470646
2493
836
100051728
Returns: 196394377
481582
14098
52
375574708
Returns: 12752566
476393
3
650
866619587
Returns: 83492210
435115
363
297
224634685
Returns: 64202938
460948
967
958
832904610
Returns: 219919011
457730
1136
160
623077931
Returns: 36761246
462875
1
433
930045747
Returns: 36391544
459952
100000
629
874709996
Returns: 144632333
433780
616
311
132981064
Returns: 67317654
422249
13707
510
457410644
Returns: 107833347
430737
100000
321
595702143
Returns: 69432397
403023
7879
632
599484617
Returns: 127195761
423527
4446
186
658188387
Returns: 39583602
423784
7
421
64715109
Returns: 69329902
429415
22148
953
642031201
Returns: 204704052
452152
1
762
78153605
Returns: 18319963
473425
4102
394
536148941
Returns: 93301182
497236
28613
749
131516507
Returns: 186489895
467010
4932
89
847718052
Returns: 20977311
455088
9900
873
662807300
Returns: 198776498
422915
63950
450
640306370
Returns: 95299645
412284
6778
443
804158884
Returns: 91436095
425774
1837
869
80090326
Returns: 184936785
417368
54595
666
697184247
Returns: 139401311
413741
504
810
99546047
Returns: 166116255
446813
1
640
87319693
Returns: 56708437
478846
181
520
276680942
Returns: 122734815
493489
628
936
603609901
Returns: 229714590
408185
693
500
746861204
Returns: 101610632
431629
7979
8
632549435
Returns: 1942780