DarkMatterParticles
2016 TCO Beijing Regional · 2016-03-24 · by ltdtl
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).
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].
4
2
{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"
4
3
{0,1,2,3}
{2,3,0,1}
Returns: "Impossible"
3
3
{0,1,2}
{1,2,0}
Returns: "Possible"
Submissions are judged against all 104 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class DarkMatterParticles with a public method string SplitParticles(int n, int k, vector<int> x, vector<int> y) · 104 test cases · 2 s / 256 MB per case