RingCountry
2021 HF Prelim · 2021-03-02 · by misof
Problem Statement
Ring Country has a capital city and N towns. The towns are built on a circle around the capital and they are numbered from 0 to N-1 in clockwise order.
All roads in Ring Country are one-directional. There are three types of roads:
- Road from the capital city to town i with length Lout[i].
- Road from town i to town (i+1) modulo N with length Laround[i].
- Road from town i back to the capital city with length Lin[i].
The royal tax collector lives in the capital. She needs to visit all the towns to collect taxes. On each day she must start her trip in the capital, visit one or more towns and then return to the capital and terminate her trip there. The maximum total length traveled on each day is Lday.
Calculate and return the minimum number of days the tax collector needs to visit each of the towns at least once. (She may visit the same town on multiple days if she wants.) If she cannot visit all the towns, return -1 instead.
In order to keep the input size small, the road lenghts are pseudorandom. Please use the following pseudocode to generate your input.
state = seed
for i = 0 .. N-1:
state = (state * 1103515245 + 12345) modulo 2^31
Lout[i] = 1 + (state modulo Mout)
state = (state * 1103515245 + 12345) modulo 2^31
Laround[i] = 1 + (state modulo Maround)
state = (state * 1103515245 + 12345) modulo 2^31
Lin[i] = 1 + (state modulo Min)
Notes
- The reference solution does not depend on the input being random, it would correctly solve any input that matches the size constraints.
Constraints
- N will be between 2 and 100,000, inclusive.
- seed will be between 0 and 2^31 - 1, inclusive.
- Lday, Mout, Maround and Min will each be between 1 and 10^9, inclusive.
4 100 123456789 60 40 50 Returns: 1
There are N = 4 towns around the capital city. The generated road lengths are as follows: Lout = { 31, 58, 29, 12 } Laround = { 12, 15, 14, 33 } Lin = { 31, 28, 49, 22 } During the generation of those arrays, the variable "state" has the following values: 231794730, 1126946331, 1757975480, 850994577, 1634557174, 707246327, 1397699428, 1035569613, 1904890498, 1335160211, 1434329552, 1273099721 The tax collector can visit all the towns in one day. The optimal route is capital-0-1-2-3-capital, its total length is 31 + 12 + 15 + 14 + 22 = 94.
4 71 123456789 60 40 50 Returns: 2
The same country as in Example 0 but now the maximum length traveled each day is only 71. There is no way to visit all the towns in one day. One possible solution for two days is to go capital-0-1-capital in one day (total length 71) and capital-2-3-capital in the other day (total length 65).
4 70 123456789 60 40 50 Returns: -1
The tax collector cannot reach town 1.
100000 1000000 47474747 2000 2000 2000 Returns: 101
This is a country of maximum size. The average road length in this country is approximately 1000. With Lday = 10^6 we can expect that the tax collector can visit slightly fewer than 1000 towns each day, so she should need a bit more than 100 days to collect all taxes.
2 1000000 47 1000 10 1000 Returns: 1
3 759 57 1000 1 1000 Returns: 1
Answer is 1 but only if you travel more than one complete cycle: C-0-1-2-0-1-C.
Submissions are judged against all 119 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RingCountry with a public method int travel(int N, int Lday, int seed, int Mout, int Maround, int Min) · 119 test cases · 2 s / 256 MB per case