JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 61
Problem: Planarity

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.

Scoring

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

Tools

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

Definition

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

Notes

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

Constraints

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

Examples

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

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)2010, TopCoder, Inc. All rights reserved.