TopCoder problem "Planarity" used in TCO10 Round 1 (Division I Level One)

Problem Statement

    You are given a graph to be drawn on the plane. All edges of the graph are drawn as straight lines. Your task is to arrange the vertices of the graph so that the number of intersecting pairs of edges is minimized.

Implementation Details

Your code should implement one method untangle(int V, int[] edges). The parameters of this method describe the graph in the following way: V is the number of vertices in the graph, and (edges[2*j], edges[2*j+1]) are the indices of vertices which form j-th edge. You have to return a int[] which contains the coordinates of the vertices. Elements 2*i and (2*i+1) of your return should contain the x- and y-coordinates of i-th vertex, respectively.

Test Case Generation

The number of vertices V is chosen between 10 and 100, inclusive. V vertices are placed at distinct random integral points within 700x700 square. A hidden parameter alpha is chosen as a double between 1 and 3. After this the number of edges E is chosen between 2*V and 5*V-1, inclusive. The edges themselves are chosen one by one: each next edge is chosen randomly from the list of unconnected pairs of vertices. Each pair can be chosen with the probability proportional to DIST-alpha, where DIST is the distance between vertices of the pair.


Your score for a test case will be the number of pairs of intersecting edges, increased by 1. Two edges intersect each other if they have at least one common point, unless this point is an endpoint of both edges. Your overall score will be calculated in the following way: for each test case 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) 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).


A visualization tool is provided for offline testing. It also allows manual play.


Parameters:int, int[]
Method signature:int[] untangle(int V, int[] edges)
(be sure your method is public)


-The memory limit is 1024 MB and the time limit is 10 seconds per test case (which includes only time spent in your code). There is no explicit code size limit.
-There are 10 example test cases and 100 full submission test cases.
-Invalid return of any kind (wrong number of elements, invalid coordinates or coinciding vertices) results in zero score for that test case, and doesn't contribute to the overall score.
-See visualizer source for the exact details of generation process and checking whether two edges intersect.
-When V = 10, the number of edges E is reduced to 45 whenever E exceeds 45.


-Your return must contain exactly 2*V elements.
-Each element of your return must be between 0 and 699, inclusive.
-All vertices locations in your return must be distinct.


Returns: "seed = 1
V = 10
E = 42
alpha = 2.7431439830828896
Returns: "seed = 2
V = 23
E = 61
alpha = 1.3799845315969623
Returns: "seed = 3
V = 99
E = 413
alpha = 1.1150135028877757
Returns: "seed = 4
V = 52
E = 207
alpha = 2.1909318594639484
Returns: "seed = 5
V = 83
E = 308
alpha = 2.825971462902503
Returns: "seed = 6
V = 34
E = 89
alpha = 1.0386470180784189
Returns: "seed = 7
V = 98
E = 431
alpha = 1.6724759405620613
Returns: "seed = 8
V = 49
E = 208
alpha = 2.626817509760431
Returns: "seed = 9
V = 55
E = 161
alpha = 1.8448823389444475
Returns: "seed = 10
V = 84
E = 405
alpha = 1.9578917178952873

Problem url:

Problem stats url:




Problem categories: