DarkMatterParticles | Topcoder Archive

Problem Statement

Maya has n volatiel dark matter particles in her research facility (particles are numbered as 0, 1, 2, ..., n-1). They are all kept in one giant jar as some particles, if separated far away, would explode.

Maya recently received a huge research grant, and built a new research facility on another planet. Maya wishes to transport exactly k of the particles to the new facility for further experiments. Maya needs to figure out which k particles she can safely transport to the new facility so that no particle would explode.

Maya has a list of pairs described by x and y such that if the two particles x[i] and y[i] are separated, they would explode (assume x[i] is not equal to y[i] for all i). In particular, if Maya transports only one of x[i] and y[i] to the new facility (thereby the other one remaining in the current facility), they would explode. Therefore Maya needs to keep both particles x[i] and y[i] in her current facility or to transport both particles to the new facility (for every i).

Given this information, please help Maya by determining whether it is possible to transport exactly k particles to the new facility without resulting in any explosion. If it is possible, return "Possible"; otherwise return "Impossible" (all quotes for clarity).

Definition

Class:: DarkMatterParticles
Method:: SplitParticles
Parameters:: int, int, int[], int[]
Returns:: String
Method signature:: String SplitParticles(int n, int k, int[] x, int[] y)
(be sure your method is public)

Constraints

n will be between 2 and 1,000, inclusive.
k will be between 1 and 1,000, inclusive.
x will contain between 1 and 2,500 elements, inclusive.
x and y will contain the same number of elements.
Each element in x will be between 0 and n-1, inclusive.
Each element in y will be between 0 and n-1, inclusive.
For each valid i, x[i] != y[i].

Examples

{0,1,2,3}

{1,2,3,0}

Returns: "Impossible"

```
4
```
```
4
```
```
{0,1,2,3}
```
```
{1,2,3,0}
```
```
Returns: "Possible"
```
```
4
```
```
2
```
```
{0,1,2,3}
```
```
{2,3,0,1}
```
```
Returns: "Possible"
```

{0,1,2,3}

{2,3,0,1}

Returns: "Impossible"

```
3
```
```
3
```
```
{0,1,2}
```
```
{1,2,0}
```
```
Returns: "Possible"
```
```
3
```
```
2
```
```
{0,1,2}
```
```
{1,2,0}
```
```
Returns: "Impossible"
```
```
6
```
```
1
```
```
{0,1,4}
```
```
{1,2,5}
```
```
Returns: "Possible"
```
```
6
```
```
2
```
```
{0,1,4}
```
```
{1,2,5}
```
```
Returns: "Possible"
```
```
6
```
```
3
```
```
{0,1,4}
```
```
{1,2,5}
```
```
Returns: "Possible"
```
```
6
```
```
6
```
```
{0,1,4}
```
```
{1,2,5}
```
```
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.