DisjointSemicircles | Topcoder Archive

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.

Definition

Class:: DisjointSemicircles
Method:: getPossibility
Parameters:: int[]
Returns:: String
Method signature:: String getPossibility(int[] labels)
(be sure your method is public)

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

```
{ -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, 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, -1, -1, 0, -1, -1, 2, 0 }
```
```
Returns: "POSSIBLE"
```
The picture shows one of the possible ways of labelling and connecting.

{ -1, 1, 3, -1, 1, 3, -1, -1 }

Returns: "IMPOSSIBLE"

{ -1, 5, -1, -1, 3, 6, 8, -1, 10, 7, -1, 7, 8, 0, 11, -1, -1, 11, 0, 10, 4, -1, 6, 5, -1, -1, 9, 9, 4, 3 }

Returns: "POSSIBLE"

{ 4, -1, 2, 4, -1, 3, 3, 12, 2, 5, -1, 0, 9, 9, 8, -1, 12, 8, -1, 6, 0, -1, -1, -1, 5, 6, 10, -1, -1, 10 }

Returns: "IMPOSSIBLE"

{ -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 }

Returns: "POSSIBLE"

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)2024, Topcoder, Inc. All rights reserved.