Connection Status:
Competition Arena > DisjointSemicircles

DisjointSemicircles

SRM 568 · 2012-12-13 · by lyrically

SRM 568 · 2012-12-13 · by lyrically · Brute Force, Graph Theory
Class Name: DisjointSemicircles
Return Type: String
Method Name: getPossibility
Arg Types: (vector<int>)
Problem Statement

Problem Statement

Consider 2N points in a plane: (0, 0), (1, 0), ..., (2N - 1, 0). You want to label these points with integers, such that each integer in { 0, 1, ..., N - 1 } is used twice, and you can draw N disjoint semicircles in the plane, as follows: For each j, one of the semicircles has to connect the two points labelled j (See the image in Example 0).

Some points are already labelled. You are given a int[] labels consisting of 2N elements. If labels[i] is -1, it means that the point (i, 0) is not labelled yet, otherwise the point (i, 0) is labelled with the integer labels[i]. Each integer in { 0, 1, ..., N - 1 } will appear in labels either zero or two times.

Return the String "POSSIBLE" if the labelling is possible, "IMPOSSIBLE" otherwise.

Constraints

  • labels will contain between 2 and 50 elements, inclusive.
  • labels will contain an even number of elements.
  • Each element in labels will be between -1 and N - 1, inclusive, where 2N is the number of elements in labels.
  • Each integer between 0 and N - 1 will appear in labels either zero or two times.
Examples
0)
{ -1, 0, -1, -1, 0, -1 }
Returns: "POSSIBLE"

If you label the points as { 1, 0, 1, 2, 0, 2 }, you can draw 3 disjoint semicircles as in the picture.

1)
{ 1, -1, 2, 1, -1, 2 }
Returns: "IMPOSSIBLE"

The labelling must be { 1, 0, 2, 1, 0, 2 }, but then you cannot draw 3 disjoint semicircles.

2)
{ 2, -1, -1, 0, -1, -1, 2, 0 }
Returns: "POSSIBLE"

The picture shows one of the possible ways of labelling and connecting.

3)
{ -1, 1, 3, -1, 1, 3, -1, -1 }
Returns: "IMPOSSIBLE"
4)
{ 1, -1, 1, -1, 2, 0, 2, -1, 3, -1, 3, 4, 0, 4 }
Returns: "POSSIBLE"
5)
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
Returns: "POSSIBLE"

16 9

6)
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
Returns: "POSSIBLE"

17 8

7)
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
Returns: "POSSIBLE"

18 7

8)
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
Returns: "POSSIBLE"

19 6

9)
{ 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }
Returns: "POSSIBLE"

20 5

10)
{ -1, 7, -1, 11, 15, 10, 4, 9, 2, 5, -1, 11, 12, -1, 2, 13, 15, 9, 14, 8, 10, -1, 0, -1, -1, -1, -1, 1, 12, 14, 7, 13, -1, 6, 3, -1, -1, -1, -1, -1, 1, 6, 0, 8, 3, 4, -1, 5, -1, -1 }
Returns: "IMPOSSIBLE"

16 9

11)
{ 5, -1, 1, -1, -1, 9, -1, 13, 4, -1, -1, 9, 6, 13, 6, 11, 0, 3, 8, 7, 7, -1, 14, 8, -1, -1, -1, 1, -1, 15, 2, 3, -1, 10, 2, 16, -1, 12, -1, -1, 12, 11, 15, 4, -1, 10, 5, 0, 14, 16 }
Returns: "IMPOSSIBLE"

17 8

12)
{ 11, 2, -1, -1, -1, 16, 14, 7, 4, -1, -1, 14, 6, 5, -1, 4, 17, -1, 7, 12, 13, 16, 6, -1, 8, 10, 5, 8, 15, 13, -1, 9, -1, -1, 17, 3, 10, -1, 3, 0, 15, 1, 2, 1, 0, 9, 11, -1, -1, 12 }
Returns: "IMPOSSIBLE"

18 7

13)
{ 12, 0, -1, 12, 8, 8, 0, -1, 5, 15, -1, 18, -1, 1, 14, 13, 2, 11, 4, 3, 13, -1, 17, -1, 1, -1, 9, 14, -1, -1, 5, -1, 2, 10, 10, 11, 6, 16, 6, -1, 18, -1, 9, 16, 4, 17, 7, 7, 15, 3 }
Returns: "IMPOSSIBLE"

19 6

14)
{ 8, 1, 3, 7, 4, 11, 6, 17, 10, 7, 13, 0, 19, 5, 12, -1, 10, -1, 8, 9, -1, -1, 15, 19, 12, -1, 16, 16, 1, 2, 11, 13, -1, -1, 17, -1, 4, 9, -1, 3, 6, 2, 18, 5, 0, 14, 15, 18, -1, 14 }
Returns: "IMPOSSIBLE"

20 5

16)
{14,9,-1,2,-1,-1,12,-1,9,14,0,5,8,-1,-1,1,5,-1,1,10,10,12,-1,-1,8,-1,-1,0,2,-1,15,16,17,18,19,20,21,22,23,24,23,24,21,22,19,20,17,18,15,16}
Returns: "POSSIBLE"

6 edges to draw. Relatively few solutions.

17)
{5,10,-1,2,-1,-1,5,-1,7,2,10,-1,3,11,13,-1,11,4,-1,-1,-1,-1,3,4,-1,13,-1,7,14,15,16,17,18,19,20,21,22,23,24,23,24,21,22,19,20,17,18,15,16,14}
Returns: "POSSIBLE"

6 edges to draw. Relatively few solutions.

18)
{-1,-1,17,-1,20,-1,-1,20,-1,5,18,-1,10,18,-1,19,14,-1,8,10,-1,5,-1,-1,21,3,0,8,0,-1,-1,-1,3,-1,21,14,-1,-1,-1,13,-1,-1,19,16,-1,17,16,13}
Returns: "POSSIBLE"

Just 2 solutions, but only 12 edges.

19)
{-1,11,-1,-1,13,0,-1,9,-1,-1,1,9,0,-1,12,-1,15,7,16,12,-1,3,13,14,-1,14,3,16,11,7,-1,15,-1,1,17,18,19,20,21,22,23,24,23,24,21,22,19,20,17,18}
Returns: "POSSIBLE"

6 edges to draw. Relatively few solutions.

20)
{11,11,10,18,-1,3,9,-1,14,-1,5,-1,-1,13,3,-1,-1,13,5,18,-1,-1,-1,14,2,17,17,2,8,-1,9,-1,12,1,12,8,1,10,19,20,21,22,23,24,23,24,21,22,19,20}
Returns: "POSSIBLE"

6 edges to draw. Relatively few solutions.

21)
{4,-1,2,-1,-1,-1,5,-1,6,15,-1,6,11,17,-1,15,4,-1,-1,-1,10,17,3,8,11,8,3,12,-1,5,-1,-1,12,2,10,-1,18,19,20,21,22,23,24,23,24,21,22,19,20,18}
Returns: "POSSIBLE"

7 edges to add, relatively few solutions.

22)
{-1,-1,15,3,-1,7,3,-1,16,-1,-1,11,1,6,-1,-1,-1,1,-1,-1,14,2,14,-1,7,2,-1,6,15,0,11,0,-1,16,17,18,19,20,21,22,23,24,23,24,21,22,19,20,17,18}
Returns: "POSSIBLE"

7 edges to add, relatively few solutions.

23)
{3,13,-1,-1,0,-1,-1,-1,-1,6,6,8,1,-1,0,9,3,-1,5,-1,9,-1,1,-1,-1,-1,8,5,13,-1,15,16,17,18,19,20,21,22,23,24,23,24,21,22,19,20,17,18,15,16}
Returns: "POSSIBLE"

7 edges to add, relatively few solutions.

Submissions are judged against all 988 archived test cases, of which 23 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class DisjointSemicircles with a public method string getPossibility(vector<int> labels) · 988 test cases · 2 s / 256 MB per case

Submitting as anonymous