Editorial for DMOPC '19 Contest 7 P1 - Hydrocarbons


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: Tzak

The hydrocarbon can be represented as a graph with atoms as vertices and bonds as edges which connect the vertices. Consider the induced subgraph with only carbon atoms and carbon-carbon bonds. As this induced subgraph is acyclic and connected, we know that this induced subgraph forms a tree with a+b+c edges and a+b+c+1 carbon atoms.

First, let's figure out how to connect these carbon atoms using the carbon-carbon bonds, while satisfying the condition that no atom has more than 4 bonds. It is always optimal to arrange the carbons in a line, and this can be proven with an exchange argument. Suppose there is some valid arrangement which is not a line, there is always a way to "transform" it into another valid arrangement which is a line:

In the diagram above, suppose there is a j-degree bond connecting 2 and 4, and a k degree bond connecting 2 and 3. After the rearrangement, there is a j-degree bond connecting 2 and 4, and a k degree bond connecting 4 and 3. This line arrangement must be valid, as the number of bonds going into 3 is now j+k \le 4, which must hold for 2 in the original graph.

If we only had single bonds and double bonds, any possible arrangement would work in this line arrangement, but we must consider triple bonds, which can either be adjacent to nothing or adjacent to a single bond. If we had only a single bonds and c triple bonds, we would need at least c-1 single bonds to produce the following arrangement:

Of course, if we had additional single bonds, we could place them anywhere in this arrangement.

Otherwise, if we had a single bonds, b double bonds, and c triple bonds, we would need at least c single bonds to produce the following arrangement:

Then, we place the remaining single and double bonds on the right-hand side of this arrangement.

Finally, we check if the d carbon-hydrogen bonds can satisfy the remaining carbons which have not yet had their 4-bond quota completely satisfied by the carbon-carbon bonds.

Pseudocode:

read a, b, c, d

carbon_count = a + b + c + 1
hydrogen_count = d

if b == 0 and a < c - 1
    print "invalid"
    terminate
if b != 0 and a < c
    print "invalid"
    terminate

(number of bonds satisfied with only carbon-carbon bonds)
bonds_satisfied = 2 * a + 4 * b + 6 * c

required_hydrogen_bonds = 4 * carbon_count - bonds_satisfied

if required_hydrogen_bonds != d
    print "invalid"
else
    print "C", carbon_count, "H", hydrogen_count

Time complexity: \mathcal{O}(1)


Comments


  • 2
    malcolmpublic  commented on May 7, 2020, 5:00 a.m.

    I think you also need to check there are not too many triple bonds. For example, if a=0, b=0, c=2, d=0 then the 'required_carbon_bonds == given_carbon_bonds' check passes, but no molecule is possible.