Editorial for DMOPC '19 Contest 7 P1 - Hydrocarbons
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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 edges and 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 -degree bond connecting and , and a degree bond connecting and . After the rearrangement, there is a -degree bond connecting and , and a degree bond connecting and . This line arrangement must be valid, as the number of bonds going into is now , which must hold for 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 single bonds and triple bonds, we would need at least 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 single bonds, double bonds, and triple bonds, we would need at least 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 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:
Comments
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.