Editorial for TLE '17 Contest 6 P1 - Molecules


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

For 50\% of the points, the cases satisfied N \le 10, so it sufficed to brute force every permutation of molecules and check if adjacent molecules could be reacted.

Time Complexity: \mathcal{O}(N!)

Note that for any number of molecules, if the molecule with highest occurrence appears as more than half of the molecules, then it is impossible to react every molecule, as there are not enough different molecules to react with the highest occurrence ones.

Otherwise, we can do the following greedy solution: Find the molecule with the highest occurrence and react it with any other molecule.

If there are 2 molecules each with frequency \frac N 2, then we can obviously react all the molecules.

Otherwise, there can be at most 1 molecule with frequency \frac N 2. While N \ge 2, there must be another molecule to react with. If we react this with any other molecule, the fact remains true as \frac N 2 and the frequency of the most common molecule both decrease by 1.

By repeating this, we can react all the molecules.

Thus, we can simply check if the highest occurrence of a molecule is at most half of the molecules.

However, we must remember that it will never be possible to react all molecules if the initial number of them is odd. Forgetting this case would result in receiving 25\% of the points.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.