Problem Statement |
| | A compound hypergraph consists of a set V of nodes and a set E of hyperedges connecting sets of those nodes. Each node v in V may have a parent node, given by parent(v). Each hyperedge consists of a subset of the nodes in V. Your task in this problem is to create a visually appealing layout of a compound hypergraph.
In this layout, each node will be represented by a rectangle, and each node will have a minimum height and width requirement. Each hyperedge will be represented by a number of horizontal, vertical, or diagonal (at 45 degree angle) line segments. The segments from one hyperedge should create a path from each node in the hyperedge to each other node in the hyperedge. A segment connects to a node if it touches the rectangle defining that node at any point.
The layout must meet all of the following requirements:
- Each set of segments forming a hyperedge must connect all the nodes in that hyperedge.
- Each node must meet or exceed its minimum size requirements.
- Each segment must be horizontal, vertical, or diagonal.
- Each node must be entirely contained within its parent node (the boundaries may not touch).
- No two segments may overlap at more than one point (be on top of each other).
- No segment may overlap any rectangle edge of any node at more than one point (be on top of its edge).
- No segment may touch another segment at its endpoint unless they are part of the same hyperedge.
- A segment in an edge may not cross (or touch) the boundary of a node unless that node is an ancestor of some of the nodes being connected, and not an ancestor of some other nodes being connected, or that node is one of the ones being connected. In other words, it may not cross a node boundary unless doing so is necessary to connect the nodes in the hyperedge.
- No two nodes may overlap, except in the case where one is contained entirely inside one of its ancestors.
- Each coordinate defining a rectangle or segment must be an integer.
For instance, consider the example shown by this image. C is the parent of A and B, while M is the parent of C, D, E, and F. Similarly, N is the parent of G-L. M and N have no parent. The hyperedges consist of the following sets: (A,B), (C,D,E,F), (D,F,G,K,L), (G,H), (G,I), and (G,J,K). Note, for instance, the three segments which connect C, D, E and F. On the other hand, 7 segments are used to connect D, F, G, K, and L.
You will be given the input as a int[] parents where element i of parents is -1 if node i has no parent, and otherwise denotes the parent of node i. You will also be given a String[], hyperedges, where each element is a single-space delimited list of two or more nodes forming a hyperedge. Finally, elements i of width and height will give the minimum width and height requirements for node i.
For each node, you should return the coordinates of the rectangle corresponding to that node, formated as "NODE <node_id> <x1> <y1> <x2> <y2>". For each hyperedge, you should return a list of segments "EDGE <edge_id> <x1> <y1> <x2> <y2> ... <xn> <yn>", where (x2i-1,y2i-1) and (x2i,y2i) specify a segment for each i. The <edge_id> and <node_id> correspond to the indices of the inputs (starting from 0).
Scoring is based on crossings, total length, total size, and number of segments. Each crossing of two segments from different hyperedges will incur a cost of C. Each unit of length in segments will incur a cost of L. Each segment will incur a cost of S. Finally the perimeter of the bounding box around your drawing will incur a cost of P per unit. For each test case, your score will be BEST/YOU, where BEST is the lowest cost incurred on a test case. Invalid returns or program crashes will be treated as a cost of infinity, yielding 0 points for the test case.
Test data will be generated by sampling from a large dataset from a real problem. The sampling process is complicated, and hence a corpus of samples may be downloaded for testing purposes. No more tests will be provided, and the exact process by which the tests are generated will not be further described. All of the minimum width and height requirements will be chosen randomly between 5 and 25, inclusive. Examples may be downloaded at www.topcoder.com/contest/problem/CompoundHypergraphDrawing/examples, while 10,000 other tests may be downloaded from
www.topcoder.com/contest/problem/CompoundHypergraphDrawing/tests.gz. Additionally, a simple tool is provided for visualizing your drawings at www.topcoder.com/contest/problem/CompoundHypergraphDrawing/vis.html. |
| |
Definition |
| | | Class: | CompoundHypergraphDrawing | | Method: | draw | | Parameters: | int[], int[], int[], String[], int, int, int, int | | Returns: | String[] | | Method signature: | String[] draw(int[] parent, int[] width, int[] height, String[] hyperedges, int C, int L, int S, int P) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The memory limit is 1024M and the time limit is 2 minutes. |
| - | If two segments from the same hyperedge cross, they are considered connected, and this does not count as a crossing. |
| - | If more than two segments cross at the same point, each pair will count as a crossing. |
| - | All coordinates must be in [-100000,100000]. |
| - | Lines have no width. |
| - | You may use at most 1000 segments. |
| - | The largest test case in the tests file has 99 nodes. The average is 59 nodes and 8.6 hyperedges. |
| - | Overlapping includes touching. |
| - | No hyperedge will include a node and one of its ancestors. |
| |
Constraints |
| - | All the following ranges are selected uniformly at random and are inclusive. |
| - | C will be between 200 and 400. |
| - | L will be between 1 and 3. |
| - | S will be between 5 and 20. |
| - | P will be between 1 and 5. |
| |
Examples |
| 0) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 -1,N 7 6,N 8 -1,N 9 8,N 10 -1,N 11 10,N 12 -1,N 13 12,N 14 -1,N 15 14,E 1 3,E 13 15," |
| Returns: "16 nodes and 2 hyperedges.
Seed = -1856808928
C = 380
L = 1
S = 13
P = 1" | |
|
| 1) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 -1,N 7 6,N 8 -1,N 9 8,N 10 2,N 9 8,N 11 2,N 12 -1,N 13 12,N 14 -1,N 15 14,N 16 -1,N 17 16,E 1 3,E 5 7,E 9 10,E 9 11,E 13 15," |
| Returns: "18 nodes and 5 hyperedges.
Seed = -1790372174
C = 330
L = 3
S = 14
P = 1" | |
|
| 2) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 -1,N 7 6,N 8 6,N 9 -1,N 10 9,N 11 9,N 12 -1,N 13 12,N 14 12,N 15 -1,N 16 15,N 17 -1,N 18 17,E 1 3,E 7 8,E 10 11,E 13 14,E 16 18," |
| Returns: "19 nodes and 5 hyperedges.
Seed = -255016001
C = 248
L = 1
S = 12
P = 5" | |
|
| 3) | |
| | "N 0 -1,N 1 -1,N 2 1,N 3 -1,N 4 3,N 5 -1,N 6 5,N 7 5,N 8 -1,N 9 8,N 10 -1,N 11 10,N 12 3,N 13 -1,N 14 13,N 15 13,N 16 1,N 17 3,N 18 -1,N 19 18,N 20 8,N 21 10,E 2 4,E 6 7,E 9 11,E 14 15,E 16 17,E 20 21," |
| Returns: "22 nodes and 6 hyperedges.
Seed = -1241721039
C = 388
L = 3
S = 5
P = 2" | |
|
| 4) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 4,N 7 -1,N 8 7,N 9 -1,N 10 9,N 11 -1,N 12 11,N 13 -1,N 14 13,N 15 -1,N 16 15,N 17 -1,N 18 17,N 19 -1,N 20 19,N 21 19,N 1 0,N 22 2,N 23 0,N 24 9,N 25 -1,N 26 25,N 27 9,N 28 -1,N 29 28,N 30 -1,N 31 30,E 1 3,E 5 6,E 8 10,E 12 14,E 16 18,E 20 21,E 1 22,E 23 24,E 26 27,E 29 31," |
| Returns: "32 nodes and 10 hyperedges.
Seed = 1933896167
C = 283
L = 3
S = 20
P = 2" | |
|
| 5) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 -1,N 7 6,N 8 -1,N 9 8,N 10 -1,N 11 10,N 12 -1,N 13 12,N 14 -1,N 15 14,N 16 -1,N 17 16,N 18 -1,N 19 18,N 20 -1,N 21 20,N 22 -1,N 23 22,N 24 25,N 26 -1,N 27 26,N 28 -1,N 29 28,N 30 -1,N 31 30,N 32 -1,N 33 32,N 34 -1,N 35 34,N 36 -1,N 37 36,N 38 -1,N 39 38,N 25 36,N 40 -1,N 41 40,N 27 26,N 42 -1,N 43 42,N 44 32,N 31 30,N 33 32,N 45 -1,N 46 45,N 47 32,E 3 5,E 7 9 11 13 15 17 19 21 23 24 27 29,E 31 33,E 35 37,E 39 25,E 41 27,E 43 44,E 31 33,E 46 47," |
| Returns: "48 nodes and 9 hyperedges.
Seed = 1825782255
C = 200
L = 3
S = 15
P = 3" | |
|
| 6) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 -1,N 7 6,N 8 6,N 9 -1,N 10 9,N 11 -1,N 12 11,N 13 -1,N 14 13,N 15 13,N 16 13,N 17 -1,N 18 17,N 19 -1,N 20 19,N 21 19,N 22 19,N 23 -1,N 24 23,N 25 -1,N 26 25,N 27 25,N 28 -1,N 29 28,N 30 28,N 31 -1,N 32 31,N 33 31,N 34 31,N 35 31,N 36 31,N 37 -1,N 38 37,N 39 -1,N 40 39,N 41 -1,N 42 41,N 43 41,N 44 -1,N 45 44,N 46 -1,N 47 46,N 48 -1,N 49 48,N 50 -1,N 51 50,E 1 3,E 7 8,E 10 12 14 15 16 18 20 21 22 24 26 27 29 30 32 33 34 35 36 38 40 42 43,E 45 47,E 49 51," |
| Returns: "52 nodes and 5 hyperedges.
Seed = 1111485637
C = 314
L = 2
S = 13
P = 3" | |
|
| 7) | |
| | "N 0 -1,N 1 0,N 2 0,N 3 -1,N 4 -1,N 5 4,N 1 0,N 6 0,N 7 -1,N 8 7,N 9 -1,N 10 9,N 11 9,N 12 -1,N 13 12,N 14 -1,N 15 14,N 16 -1,N 17 16,N 18 -1,N 19 18,N 20 18,N 21 -1,N 22 21,N 23 12,N 24 -1,N 25 24,N 26 16,N 27 -1,N 28 27,N 29 4,N 30 -1,N 31 30,N 32 -1,N 33 32,N 34 -1,N 35 34,N 36 16,N 37 16,N 38 -1,N 39 38,N 40 38,N 41 -1,N 42 -1,N 43 42,N 44 -1,N 45 44,N 46 -1,N 47 46,N 48 -1,N 49 48,N 50 -1,N 51 50,E 1 2,E 1 6,E 10 11,E 15 17,E 19 20,E 22 23,E 25 26,E 28 29,E 31 33,E 35 36,E 39 40,E 43 45 47 49," |
| Returns: "52 nodes and 12 hyperedges.
Seed = -55340767
C = 272
L = 1
S = 19
P = 5" | |
|
| 8) | |
| | "N 0 -1,N 1 0,N 2 -1,N 3 2,N 4 -1,N 5 4,N 6 2,N 7 -1,N 8 7,N 6 2,N 9 4,N 10 -1,N 11 10,N 12 10,N 13 -1,N 14 13,N 15 -1,N 16 15,N 17 13,N 18 13,N 19 -1,N 20 19,N 21 -1,N 22 21,N 23 -1,N 24 23,N 25 -1,N 26 25,N 27 25,N 28 25,N 29 -1,N 30 29,N 31 29,N 32 29,N 33 -1,N 34 33,N 35 -1,N 36 35,N 37 35,N 38 -1,N 39 38,N 40 0,N 41 -1,N 42 41,N 43 -1,N 44 43,N 45 -1,N 46 45,N 47 0,N 48 -1,N 49 48,N 50 48,N 51 -1,N 52 51,N 53 -1,N 54 53,E 3 5,E 6 8,E 6 9,E 11 12,E 14 16 17 18 20 22 24 26 27 28 30 31 32 34 36 37 39,E 42 44,E 46 47,E 49 50,E 52 54," |
| Returns: "55 nodes and 9 hyperedges.
Seed = 1142965478
C = 285
L = 3
S = 6
P = 1" | |
|
| 9) | |
| | "N 0 -1,N 1 0,N 2 0,N 3 -1,N 4 3,N 5 -1,N 6 5,N 7 -1,N 8 7,N 9 -1,N 10 9,N 11 -1,N 12 11,N 13 -1,N 14 13,N 15 -1,N 16 15,N 17 -1,N 18 17,N 19 -1,N 20 19,N 21 -1,N 22 21,N 23 -1,N 24 23,N 25 23,N 26 -1,N 27 26,N 28 26,N 29 26,N 30 -1,N 31 30,N 32 -1,N 33 32,N 34 -1,N 35 34,N 36 34,N 37 -1,N 38 37,N 39 -1,N 40 39,N 41 -1,N 42 41,N 43 41,N 44 41,N 45 41,N 46 41,N 47 -1,N 48 47,N 49 47,N 50 -1,N 51 50,N 52 -1,N 53 52,N 54 52,N 55 52,N 56 -1,N 57 56,N 58 56,N 59 56,N 60 -1,N 61 60,N 62 -1,N 63 62,N 64 -1,N 65 64,N 66 64,N 67 -1,N 68 67,N 69 67,N 70 67,N 71 -1,N 72 71,N 73 71,N 74 71,N 75 -1,N 76 75,N 77 75,N 78 -1,N 79 78,N 80 -1,N 81 80,N 82 -1,N 83 82,N 84 -1,N 85 84,N 86 84,N 87 -1,N 88 87,N 89 87,N 90 87,N 91 87,N 92 87,N 93 87,N 94 87,N 95 87,E 1 2,E 4 6,E 8 10,E 12 14 16 18 20 22 24 25 27 28 29 31 33 35 36 38 40 42 43 44 45 46 48 49 51 53 54 55 57 58 59 61 63 65 66 68 69 70 72 73 74 76 77 79 81 83 85 86 88 89 90 91 92 93 94 95," |
| Returns: "96 nodes and 4 hyperedges.
Seed = -405961877
C = 285
L = 2
S = 13
P = 4" | |
|