TopCoder problem "MegaParty" used in Marathon Match 49 (Division I Level One)

Problem Statement



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.


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.


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.


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.


A visualization tool is available for offline testing at


Parameters:int[], int[], double, double
Method signature:double[] arrangement(int[] A, int[] B, double e1, double e2)
(be sure your method is public)


-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.


-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.


Returns: "seed = 1
N = 10
e1 = 79.90537473458491
e2 = 87.73517325544584
Returns: "seed = 2
N = 50
e1 = 69.0075415716353
e2 = 13.65589320322015
Returns: "seed = 3
N = 100
e1 = 36.08279169755407
e2 = 83.35353433161342
Returns: "seed = 4
N = 761
e1 = 49.3674457914687
e2 = 77.57082451444492
Returns: "seed = 5
N = 852
e1 = 11.621835296956831
e2 = 97.48383017983551
Returns: "seed = 6
N = 586
e1 = 27.53708937356408
e2 = 15.397192389252275
Returns: "seed = 7
N = 506
e1 = 88.36666714437418
e2 = 53.13863217801227
Returns: "seed = 8
N = 289
e1 = 64.46620025547209
e2 = 80.53024200739404
Returns: "seed = 9
N = 164
e1 = 22.80606053590618
e2 = 78.18281248212246
Returns: "seed = 10
N = 620
e1 = 14.821168809032962
e2 = 84.22929341728343

Problem url:

Problem stats url:




Problem categories:

Geometry, Graph Theory