Problem Statement |
| | Introduction
You want to run a party and to invite all your friends to come. The problem is, not all of your friends like each other. You want to place everybody in as little room as possible so that everybody feels as comfortable as possible.
Details
The relationships between your friends are described with a NxN matrix a: aij=1 denotes that i and j are friends, aij=-1 denotes that i and j are enemies, and aij=0 means that i and j feel neutral about each other. Moreover, the feelings of some of your friends are more important to you than the feelings of other, bi denoting the importance of person i to you.
Placing N people in the room is modeled as arranging N points on the plane. To calculate the quality of the arrangement, the following rules are used:
-
no two points can be placed closer than 10, so if the distance between points i and j is strictly less than 10, the quality of the arrangement is equal to 0.
-
the happiness of person i hi is the number of his friends who are placed at distance not greater than e1 from him minus the number of his enemies who are placed at distance not greater than e2 from him.
-
the area of the arrangement is (max (xi) - min (xi) + 20) * (max (yi) - min (yi) + 20).
-
finally, the quality of the arrangement is the sum of hi*bi over all points divided by the area of the arrangement.
Implementation
You will be given int[]s A and B (aij=A[i*N+j], bi=B[i]) and doubles e1 and e2 (you can deduce N as the number of elements in B).
Your return will describe the arrangement of the points on the plane and must contain exactly 2*N elements, elements 2*i and 2*i+1 being x and y-coordinates of point i on the plane.
Scoring
Your score for an individual test case will be the quality of the arrangement described with your return. Negative scores will be replaced with 0.
Your overall score will the sum of YOU/BEST, where YOU = your score and BEST = the best score for anyone on that test case.
Test Generation
To generate a, first the numbers p(1) and p(-1) are chosen between 0.1 and 0.5. Each element of a above the diagonal (a[i][j] with j>i) is generated randomly and independently so that it is 1 with probability p(1), -1 with probability p(-1) and 0 with probability (1-p(1)-p(-1)). The elements below the diagonal are then set to mirror those above (aij=aji). After this a is modified for 2*N*N iterations in the following way: on each iteration, a random triple of distinct indices i1, i2 and i3 is chosen, and if the set of elements a[i1][i2], a[i1][i3] and a[i2][i3] contains one -1 and two 1 or three -1, the triple is considered to be unstable and element a[i1][i2] is inverted.
Visualization
A visualization tool is available for offline testing at http://www.topcoder.com/contest/problem/MegaParty/manual.html. |
| |
Definition |
| | | Class: | MegaParty | | Method: | arrangement | | Parameters: | int[], int[], double, double | | Returns: | double[] | | Method signature: | double[] arrangement(int[] A, int[] B, double e1, double e2) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | All parameters (except for A) are chosen randomly and uniformly (except for N in first three tests). |
| - | Euclidean distance is used to calculate the distance between two points. |
| - | Invalid return of any kind will result in zero absolute score for that test case. |
| - | The memory limit is 1024 MB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Constraints |
| - | N will be between 10 and 1000, inclusive. |
| - | e1 and e2 will be between 10 and 100, inclusive. |
| - | Each element of A will be 1, -1 or 0, A[i*N+i]=0, A[i*N+j]=A[j*N+i]. |
| - | Each element of B will be between 0 and 10, inclusive. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
N = 10
e1 = 79.90537473458491
e2 = 87.73517325544584
" | |
|
| 1) | |
| | | Returns: "seed = 2
N = 50
e1 = 69.0075415716353
e2 = 13.65589320322015
" | |
|
| 2) | |
| | | Returns: "seed = 3
N = 100
e1 = 36.08279169755407
e2 = 83.35353433161342
" | |
|
| 3) | |
| | | Returns: "seed = 4
N = 761
e1 = 49.3674457914687
e2 = 77.57082451444492
" | |
|
| 4) | |
| | | Returns: "seed = 5
N = 852
e1 = 11.621835296956831
e2 = 97.48383017983551
" | |
|
| 5) | |
| | | Returns: "seed = 6
N = 586
e1 = 27.53708937356408
e2 = 15.397192389252275
" | |
|
| 6) | |
| | | Returns: "seed = 7
N = 506
e1 = 88.36666714437418
e2 = 53.13863217801227
" | |
|
| 7) | |
| | | Returns: "seed = 8
N = 289
e1 = 64.46620025547209
e2 = 80.53024200739404
" | |
|
| 8) | |
| | | Returns: "seed = 9
N = 164
e1 = 22.80606053590618
e2 = 78.18281248212246
" | |
|
| 9) | |
| | | Returns: "seed = 10
N = 620
e1 = 14.821168809032962
e2 = 84.22929341728343
" | |
|
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.