Problem Statement
There are N cities in the country. They are numbered from 0 to N-1, inclusive.
We want to organize an onsite programming competition. We have an external sponsor who will pay for S contest sites. We can pick any S distinct cities for these contest sites.
We would like to make it so that students from all cities can take part in the contest. After we choose the contest sites, we will rent some buses to help all other students reach one of the contest sites.
The buses available for rent are large enough: all contestants from the whole country will fit into any single bus.
We will organize a sequence of exactly B = N - S buses. The buses will be numbered from 1 to B, inclusive. Each bus will travel from one city to another city. For each x > 1, bus x will only depart from its starting city after bus x-1 arrives to its destination.
You are free to choose the source and destination for each bus. In particular, the destination of a bus can be any city, not just a contest site. In order to reach a contest site, some students may need to travel via other cities, taking multiple buses.
The cost of booking a bus depends not only on its route but also on the time of day. Having bus number x travel from city y to city z costs (x*(y+4)*(y+z+A) modulo M)+1 coins.
Calculate and return the minimum total cost of getting students from the whole country to the contest sites, given that we can choose where to have the contest sites and also the sequence of buses to get the rest of the country to the contest.
Definition
- Class:
- BusTravel
- Method:
- optimize
- Parameters:
- int, int, int, int
- Returns:
- int
- Method signature:
- int optimize(int N, int S, int M, int A)
- (be sure your method is public)
Notes
- There is nothing specific in the formula for bus rental costs. The reference solution does not depend on any special property of the costs.
- You must book exactly B = N - S buses. (There may be cheaper solutions with more buses, but for logistical reasons we cannot use them.)
Constraints
- N will be between 1 and 16, inclusive.
- S will be between 1 and N, inclusive.
- M will be between 1 and 1,000, inclusive.
- A will be between 0 and M-1, inclusive.
Examples
4
4
47
7
Returns: 0
We can make a contest site in every city. No money for buses needed!
4
3
47
7
Returns: 4
For reference, all possible bus costs are below. (In the table, row x column y has the cost of booking the bus from city x to city y.) Bus 1: -- 33 37 41 41 -- 4 9 8 14 -- 26 24 31 38 -- The cheapest bus we can book is from city 1 to city 2, the cost is 4 coins. The optimal solution is to book this bus and to make contest sites in cities 0, 2, 3.
4
2
47
7
Returns: 8
Costs for bus #1 are the same as in the previous example. Costs for bus 2 are as follows: Bus 2: -- 18 26 34 34 -- 7 17 15 27 -- 4 47 14 28 -- The optimal solution here looks as follows: Bus #1 is booked from city 1 to city 2. Its cost is 4. Bus #2 is booked from city 2 to city 3. Its cost is also 4. The contest sites will be in cities 0 and 3. Students from city 1 will take both buses to get to city 3. Students from city 2 will take bus #2 to get to city 3.
4
1
47
7
Returns: 25
Bus 3: -- 3 15 27 27 -- 10 25 22 40 -- 29 23 44 18 -- Here we need to get everyone to the same city. The optimal solution differs from the previous one quite significantly: Bus #1 is booked from city 2 to city 0. Its cost is 8. Bus #2 is booked from city 3 to city 1. Its cost is 14. Bus #3 is booked from city 0 to city 1. Its cost is 3. The only contest site will be in city 1. We can easily verify that students from all other cities can reach it using some of the buses we booked. Note that taking the optimal solution for the previous example and then booking bus #3 as in this solution is NOT a valid solution. Remember that buses are numbered in chronological order. If we have buses 1->2, 2->3, and only then 0->1, students from city 0 will not be able to reach city 3.
4
1
47
17
Returns: 30
Different A gives us different bus rental costs and leads to a different solution.
14
4
1
0
Returns: 10
Each bus can be booked for one coin. We can, for example, book buses from cities 0 through 9 to city 12, and then organize contest sites in cities 10 through 13.
1
1
1
0
Returns: 0
1
1
42
23
Returns: 0
2
1
1
0
Returns: 1
2
1
42
23
Returns: 13
13
13
42
23
Returns: 0
16
16
7
3
Returns: 0
8
1
244
146
Returns: 72
8
3
228
157
Returns: 29
3
2
2
0
Returns: 1
7
4
3
2
Returns: 3
9
4
27
14
Returns: 6
6
1
109
76
Returns: 45
8
5
23
1
Returns: 6
5
3
6
4
Returns: 2
9
5
5
2
Returns: 4
6
4
7
4
Returns: 2
8
6
47
35
Returns: 4
7
3
3
1
Returns: 4
12
7
46
38
Returns: 6
4
3
28
15
Returns: 1
7
5
15
0
Returns: 2
5
1
6
4
Returns: 4
12
9
479
187
Returns: 15
15
1
62
58
Returns: 34
14
11
66
31
Returns: 3
6
3
175
45
Returns: 16
10
4
9
2
Returns: 6
14
13
114
13
Returns: 1
7
4
2
1
Returns: 3
4
2
3
0
Returns: 2
5
2
358
253
Returns: 47
11
8
2
0
Returns: 3
5
3
2
0
Returns: 2
9
2
2
1
Returns: 7
3
2
20
17
Returns: 1
12
5
7
2
Returns: 7
11
1
7
3
Returns: 11
8
3
327
32
Returns: 38
11
2
488
421
Returns: 56
3
2
6
5
Returns: 1
10
9
5
2
Returns: 1
15
6
15
0
Returns: 9
12
2
491
141
Returns: 119
13
9
2
1
Returns: 4
3
2
452
35
Returns: 145
14
13
7
4
Returns: 1
16
1
103
52
Returns: 40
16
1
18
3
Returns: 15
16
1
57
21
Returns: 24
16
2
77
11
Returns: 22
16
2
220
12
Returns: 34
16
2
71
50
Returns: 24
16
3
48
13
Returns: 13
16
3
45
29
Returns: 13
16
3
60
59
Returns: 13
16
4
418
345
Returns: 51
16
4
2
1
Returns: 12
16
4
2
1
Returns: 12
16
5
480
314
Returns: 17
16
5
50
6
Returns: 11
16
5
39
10
Returns: 14
16
6
214
127
Returns: 38
16
6
188
128
Returns: 14
16
6
52
35
Returns: 10
16
7
3
2
Returns: 9
16
7
347
193
Returns: 33
16
7
2
0
Returns: 9
16
8
7
3
Returns: 8
16
8
2
1
Returns: 8
16
8
14
0
Returns: 8
16
9
9
8
Returns: 7
16
9
128
98
Returns: 9
16
9
489
322
Returns: 30
16
10
79
65
Returns: 6
16
10
154
22
Returns: 11
16
10
233
227
Returns: 9
16
11
5
3
Returns: 5
16
11
480
305
Returns: 5
16
11
7
4
Returns: 5
16
12
119
95
Returns: 4
16
12
26
12
Returns: 4
16
12
5
3
Returns: 4
16
13
77
32
Returns: 3
16
13
303
182
Returns: 3
16
13
3
2
Returns: 3
16
14
5
4
Returns: 2
16
14
24
22
Returns: 2
16
14
39
35
Returns: 2
16
15
3
2
Returns: 1
16
15
15
11
Returns: 1
16
15
28
19
Returns: 1
16
1
945
64
Returns: 87
16
1
955
566
Returns: 103
16
1
958
584
Returns: 201
16
1
943
263
Returns: 209
16
1
965
395
Returns: 320
16
1
950
630
Returns: 182
16
1
905
814
Returns: 209
16
1
953
674
Returns: 160
16
1
903
104
Returns: 163
16
1
900
270
Returns: 166
16
1
961
741
Returns: 186
16
1
969
9
Returns: 251
16
1
940
581
Returns: 235
16
1
954
235
Returns: 233
16
1
930
535
Returns: 217
5
4
3
2
Returns: 1