IcelandRingRoad | Topcoder Archive

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.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.