IcelandRingRoad
SRM 810 · 2021-07-22 · by misof
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)
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.
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
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class IcelandRingRoad with a public method int solve(int N, int P, int M, long long state) · 95 test cases · 2 s / 256 MB per case