Problem Statement |
| | In this problem you will be drawing a graph on a plane. Each vertex will be drawn as a point, and each edge will be drawn as a line segment between two vertices. Each edge has a desired length - the length it should have on the drawing. Your task is to assign to each vertex integer coordinates from a limited area so that the ratio of the actual edge length to the desired length is as similar across all edges as possible.
Implementation
Your code must implement one method plot(int NV, int[] edges):
-
NV is the number of vertices in the graph.
-
edges describes the desired lengths of the edges in the graph: the i-th edge connects vertices edges[3*i] and edges[3*i+1] and has the desired length of edges[3*i+2].
-
Each vertex present in the graph is used in at least one edge. No pair of vertices is connected by two different edges.
The return from this method will describe the assigned coordinates of the graph vertices. It must contain exactly 2*NV elements and give the coordinates of the j-th vertex as (ret[2*j], ret[2*j+1]). Each coordinate of each vertex must be between 0 and 700, inclusive. All vertices must be placed in distinct points.
Scoring
For each test case we will calculate your raw score. If your solution produced an invalid return (contained invalid number of elements, placed two vertices at the same point etc.), raw score for this test case will be 0. Otherwise, raw score will be calculated as follows. For each edge of the graph, its actual length on the drawing and the ratio "actual length / desired length" are calculated. Then minimal and maximal ratios across all edges are selected, and the raw score for a test case is calculated as MIN_RATIO/MAX_RATIO.
Your overall score will be the average of your raw scores over all test cases, multiplied by 1,000,000.
Test Case Generation
To generate the desired lengths of the graph edges, we will use the following procedure:
-
Assign random integer coordinates from [0, 700] x [0, 700] to each vertex of the graph, so that the coordinates of all vertices are distinct.
-
Calculate actual lengths of edges based on these coordinates.
-
Pick a random distortion percentage P between 0 and 99, inclusive.
-
For each edge, multiply its length by 1.1^G with probability P (and keep the length unchanged with probability 1-P). G is sampled from normal distribution with mean 0.0 and standard deviation 1.0. The new lengths are capped to be between 1 and 991, inclusive.
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: | GraphDrawing | | Method: | plot | | Parameters: | int, int[] | | Returns: | int[] | | Method signature: | int[] plot(int NV, int[] edges) | | (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. |
| - | The match is rated. |
| |
Constraints |
| - | The number of vertices NV will be between 10 and 1000, inclusive. |
| - | The number of edges will be between NV - 1 and NV * min(10, (NV - 1) / 4), inclusive. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
Number of vertices NV = 5
Number of edges NE = 5
Required edge lengths:
0-1 = 265
1-2 = 296
1-3 = 210
0-4 = 421
0-3 = 96
" | |
|
| 1) | |
| | | Returns:
"seed = 2
Number of vertices NV = 20
Number of edges NE = 69
Required edge lengths:
0-11 = 425
1-15 = 250
2-12 = 684
3-19 = 94
4-6 = 566
5-8 = 79
4-7 = 336
5-9 = 384
10-19 = 546
0-13 = 712
14-17 = 110
10-16 = 193
6-18 = 412
9-10 = 315
8-17 = 130
5-15 = 306
1-7 = 611
10-17 = 125
4-10 = 175
2-18 = 436
0-9 = 641
0-10 = 353
4-19 = 448
7-16 = 193
7-9 = 165
0-14 = 426
8-13 = 421
1-18 = 644
12-19 = 96
4-14 = 221
0-19 = 598
8-19 = 381
11-17 = 202
8-9 = 241
9-16 = 347
7-8 = 343
1-13 = 555
7-17 = 243
13-18 = 544
12-14 = 445
0-1 = 312
9-14 = 330
16-19 = 333
2-16 = 381
8-16 = 317
6-16 = 494
1-5 = 227
3-4 = 467
7-11 = 345
3-16 = 310
7-13 = 460
15-17 = 426
3-7 = 87
1-19 = 592
17-18 = 276
3-6 = 203
7-12 = 224
7-18 = 116
2-13 = 742
0-5 = 223
11-14 = 110
6-19 = 117
1-17 = 444
1-11 = 616
1-4 = 387
15-16 = 552
13-19 = 286
10-14 = 132
1-12 = 688
" | |
|
| 2) | |
| | | Returns: "seed = 3
Number of vertices NV = 1000
Number of edges NE = 7395
" | |
|
| 3) | |
| | | Returns: "seed = 4
Number of vertices NV = 761
Number of edges NE = 3992
" | |
|
| 4) | |
| | | Returns: "seed = 5
Number of vertices NV = 852
Number of edges NE = 4228
" | |
|
| 5) | |
| | | Returns: "seed = 6
Number of vertices NV = 586
Number of edges NE = 1714
" | |
|
| 6) | |
| | | Returns: "seed = 7
Number of vertices NV = 506
Number of edges NE = 1181
" | |
|
| 7) | |
| | | Returns: "seed = 8
Number of vertices NV = 289
Number of edges NE = 1617
" | |
|
| 8) | |
| | | Returns: "seed = 9
Number of vertices NV = 164
Number of edges NE = 1470
" | |
|
| 9) | |
| | | Returns: "seed = 10
Number of vertices NV = 620
Number of edges NE = 4353
" | |
|
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.