Problem Statement |
| | N points labeled from 0 to N-1 are drawn on the circle of radius 1 so that the angle between each pair of adjacent points is 360/N degrees. Pairs of points with certain labels will be connected with straight lines. Your task is to find a permutation of the labels for the points which will minimize the sum of lengths of these lines.
Implementation
Your code should implement a single method permute(int[] m). m[i*N+j] = 1 if the points with labels i and j have to be connected with a line, and 0 otherwise. You can deduce N as sqrt(length(m)). The matrix represented by m is symmetrical (m[i*N+j] = m[j*N+i] for all i, j), with diagonal elements m[i*N+i] = 0.
permute should return an array of N integers specifying the permutation of labels. The returned labels will be assigned to points on the circle in clockwise order, starting with first label of the return assigned to the top point.
Here is an example for test 0 (seed = 1) with labels permutation (3, 4, 0, 1, 5, 2, 7, 6).
Scoring
Your score for an individual test case will be the sum of lengths of edges connecting the drawn points. If your return has invalid format, your score for the test case will be -1.
Your overall score will be calculated in the following way: for each test case where your score is not -1, you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is less than this competitor's score) and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1), then multiplied by 1000000 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: | PointsOnTheCircle | | Method: | permute | | Parameters: | int[] | | Returns: | int[] | | Method signature: | int[] permute(int[] m) | | (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 1000 test cases in the final testing. |
| - | The match is rated. |
| |
Constraints |
| - | N will be between 20 and 200, inclusive. |
| - | The probability of each pair of points being connected with a line is constant within one test case, and is chosen randomly and uniformly between 0.5% and 20%. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
N = 8
Edge probability = 20.0%
Number of edges = 9
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 1 0 0 1
0 0 0 0 1 0 1 0
1 1 1 1 0 0 1 0
0 0 0 0 0 0 0 1
0 0 0 1 1 0 0 1
0 0 1 0 0 1 1 0
" | |
|
| 1) | |
| | | Returns:
"seed = 2
N = 20
Edge probability = 17.1%
Number of edges = 46
0 0 1 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0
1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1
0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 1 0 1 1
0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0
1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 0
1 0 1 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0
0 0 1 1 0 0 1 1 1 1 1 1 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0
0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 1
0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0
" | |
|
| 2) | |
| | | Returns: "seed = 3
N = 200
Edge probability = 8.700000000000001%
Number of edges = 1737
" | |
|
| 3) | |
| | | Returns:
"seed = 4
N = 141
Edge probability = 12.700000000000001%
Number of edges = 1288
" | |
|
| 4) | |
| | | Returns: "seed = 5
N = 156
Edge probability = 9.600000000000001%
Number of edges = 1160
" | |
|
| 5) | |
| | | Returns: "seed = 6
N = 82
Edge probability = 6.6000000000000005%
Number of edges = 246
" | |
|
| 6) | |
| | | Returns:
"seed = 7
N = 112
Edge probability = 18.900000000000002%
Number of edges = 1185
" | |
|
| 7) | |
| | | Returns: "seed = 8
N = 105
Edge probability = 9.5%
Number of edges = 495
" | |
|
| 8) | |
| | | Returns: "seed = 9
N = 41
Edge probability = 11.8%
Number of edges = 96
" | |
|
| 9) | |
| | | Returns: "seed = 10
N = 46
Edge probability = 9.9%
Number of edges = 86
" | |
|
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.