TEAMFORM - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are n people and 2 \cdot m of them already formed pairs. The task is to answer the question if all the remaining unpaired yet n-2 \cdot m people can be connected into pairs.

EXPLANATION:

In the input, exacts pairings for 2 \cdot m people are also given, but this is completely irrelevant to solving the problem. Since a pair consists of 2 different people and one person wants to be a part of exactly one pair, the all remaining n-2 \cdot m people can be connected into pairs if and only if n-2 \cdot m is even. You can also notice that for integer m, n - 2 \cdot m is even if and only if n is even, so we can as well check the parity of n. It follows that the time complexity for answering a single test case is O(1).

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

2

we solve this problem by only seeing the nature of n.if n is odd then we can not form team by taking all the people but if n is even we can surely form teams by taking all the people.that’s the simple one.there is no need of n and pairing of 2*m.

3

Of course, but this is equivalent: n is even if and only if n - 2 \cdot m is even for any integer m. I added this observation to the editorial. Thanks. Just remember that your observation is correct in the context of this problem. For example, if the problem statement was different and instead of 2 \cdot m people connected in pairs, we have m people unregistered from the contest, then parity of n is not enough to decide if remaining n-m people can be connected into pairs.