Problem Statement |
| | You have been elected as the transport minister of a small country and your job is to build roads between its cities. There are N cities that can be potentially connected with E edges. Each potential connection is formatted as "A B M P", where M is the number of materials needed to connect cities A and B (note that all connections are bi-directional). Building such a connection will earn you P connection points. The residents of the country also want to have R routes (paths of edges) between certain pairs of cities. Each route is formatted as "A B P", where A and B are two distinct cities. Building such a route will earn you P route points. Note it may not be possible to build all the routes. Given a fixed number of materials (NM) build the set of connections that maximizes the product of connection points and route points. Good luck and let's hope you can get re-elected!
Here is a solution for example 0 (seed=1) with NM=24, N=30, E=42 and R=6. The vertices represent cities, while the dashed lines represent potential connections. Green vertices are cities that are endpoints of at least one route. The number of dashes in a connection represent the number of materials required to build that connection. The green connections are those that have been built. Each connection built gives you connection points, so the connection score is 20+24+6+5+9+16=80. Two routes have been completed: 10-12 (17 points), 14-21 (3 points). Hence the route score is 17+3=20, so the total raw score is 80*20=1600.
Implementation
Your code should implement a single method findSolution(int NM, int N, int E, String[] edges, int R, String[] routes). The method should return an int[] containing the ids of edges to be built.
Scoring
Your raw score for a test case is the product of connection points and route points. If your return was invalid (duplicate edges, illegal edges, too many materials used etc.) then your raw score on this test case will be -1.
If your raw score for a test case is negative then your normalized score for that test case is 0. Otherwise, your normalized score for each test case is YOUR/MAX, where YOUR is your raw score and MAX is the largest raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, the sum of all your test scores is multiplied by 1,000,000 and divided by the number of test cases.
Tools
An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages. |
| |
Definition |
| | | Class: | RoadNetwork | | Method: | findSolution | | Parameters: | int, int, int, String[], int, String[] | | Returns: | int[] | | Method signature: | int[] findSolution(int NM, int N, int E, String[] edges, int R, String[] routes) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 10 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission (provisional) test cases. There will be 2000 test cases in the final testing. |
| - | The match is rated. |
| |
Constraints |
| - | NM is the number of available materials. It will be chosen randomly between K/8 and K/4, where K is the number of points you would get for building all the routes. |
| - | N is the number of cities. It will be chosen randomly between 30 and 1000. |
| - | E is the number of potential connections. It will be at least N-1. |
| - | edges is the set of potential connections. Each element of edges is in the format "A B M P", indicating that there is a potential connection between cities A and B that requires M materials and earns you P connection points. A and B cannot be the same (ie., cannot connect a city to itself). A and B are integers from 0 to N-1. M is an integer from 1 to 37. P is set to p*M, where p is chosen randomly between 1 and 5. There exists a path from any city to every other city - all cities can be connected to form one connected component. There will not be any duplicate connections. |
| - | R is the number of routes that need to be completed. It will be chosen randomly between 5 and N/4. |
| - | routes is the set of routes that need to be completed. Each element of routes is in the format "A B P", indicating that completing the route between cities A and B will give you P route points. A and B cannot be the same. A and B are integers from 0 to N-1. P is an integer from 1 to 37. There will not be any duplicate routes. |
| - | Please refer to the visualiser for the full details of the graph construction. |
| - | All generated values are chosen uniformly at random. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
NM = 24 N = 30 E = 42 R = 6
edges
28 15 3 15
21 14 3 9
16 23 2 2
2 8 2 10
0 24 1 5
18 7 2 4
16 0 8 32
1 27 1 1
22 3 2 8
10 9 2 6
5 6 1 2
2 6 5 10
17 7 3 6
16 24 8 40
29 19 1 5
13 11 1 2
17 13 3 12
29 8 3 9
22 19 5 25
3 1 2 8
1 22 5 10
28 20 4 16
25 20 2 4
27 12 1 5
19 8 4 12
1 21 6 6
7 14 3 15
10 18 4 20
6 11 3 6
6 25 4 4
25 11 2 6
6 13 4 20
22 12 6 24
21 26 3 15
21 18 6 24
2 19 5 25
28 13 5 25
17 6 5 25
23 4 7 7
13 15 3 12
21 27 6 6
23 22 9 27
routes
10 12 17
8 18 16
14 11 10
14 21 3
23 18 23
28 24 29
" | |
|
| 1) | |
| | | Returns: "seed = 2
NM = 252 N = 1000 E = 2384 R = 100
" | |
|
| 2) | |
| | | Returns: "seed = 3
NM = 379 N = 867 E = 1837 R = 128
" | |
|
| 3) | |
| | | Returns: "seed = 4
NM = 44 N = 819 E = 1713 R = 25
" | |
|
| 4) | |
| | | Returns: "seed = 5
NM = 135 N = 270 E = 588 R = 41
" | |
|
| 5) | |
| | | Returns: "seed = 6
NM = 61 N = 422 E = 887 R = 26
" | |
|
| 6) | |
| | | Returns: "seed = 7
NM = 15 N = 63 E = 126 R = 5
" | |
|
| 7) | |
| | | Returns: "seed = 8
NM = 60 N = 993 E = 2322 R = 31
" | |
|
| 8) | |
| | | Returns: "seed = 9
NM = 58 N = 712 E = 1793 R = 23
" | |
|
| 9) | |
| | | Returns: "seed = 10
NM = 57 N = 444 E = 1056 R = 25
" | |
|
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)2020, TopCoder, Inc. All rights reserved.
