Editorial for TLE '16 Contest 1 P3 - Joey and Chemistry


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

First, note that the order of carbons, hydrogens, and oxygens in R do not matter. Only the amount of each element is important. We can get the count of each element using string manipulation.

We can simplify the entire complete combustion chemical equation into a system of 3 equations with 4 unknowns. The first equation will represent carbons, the second equation will represent hydrogens, and the third equation will represent oxygens.

\displaystyle \begin{align*}
a \cdot R_C &= c \\
a \cdot R_H &= 2 \cdot d \\
a \cdot R_O + 2 \cdot b &= 2 \cdot c + d
\end{align*}

Note that there can be an infinite number of solutions, but we want a solution where a, b, c, and d are all positive integers and are in lowest terms with each other. We can first assume that a is equal to 1, meaning that c is equal to R_C. Next, we need to make sure that R_H is divisible by 2 (so d can have an integer solution). If R_H is divisible by 2, d is equal to R_H/2. If R_H is not divisible by 2, multiply a and c by 2 and set d equal to R_H. Finally, we can solve for b using the same principles that we used to solve for d. Namely, if b cannot initially be an integer, multiply the other variables by 2 so that b can be an integer. If a, b, c, or d are not positive integers, then it is impossible to balance the equation.

Time Complexity: \mathcal O(|R|)


Comments

There are no comments at the moment.