Editorial for Back To School '19: 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: wleung_bvg

Subtask 1

For the first subtask, we can encode each beaker with a unique binary number from $0$ $0$ to $N - 1$ $N - 1$ . For the $i^{th}$ $i^{t h}$ bit, we can easily determine if the encoding of the hydrogen cyanide beaker is a $0$ $0$ or a $1$ $1$ by pouring all of the beakers that have a $1$ $1$ in the $i^{th}$ $i^{t h}$ bit into the cup. If the substance changes colours, then we know that the $i^{th}$ $i^{t h}$ bit of the hydrogen cyanide beaker is also a $1$ $1$ . Otherwise, it is a $0$ $0$ . If we repeat this for each bit, then we can determine the full binary encoding of the hydrogen cyanide beaker. Determining the formula for the number of bits for $N$ $N$ beakers is an exercise for the reader.

Time Complexity: $\mathcal{O}(1)$ $O (1)$

Subtask 2

For the second subtask, we can use the same process as subtask 1, except we have $M$ $M$ minutes. We want to divide each of the required measurements into $M$ $M$ minutes while minimizing the maximum number of cups used in any minute. It can be shown that if $Q$ $Q$ is the number of cups required for $N$ $N$ beakers in $1$ $1$ minute, then the number of cups required for $M$ $M$ minutes is $\lceil \frac{Q}{M} \rceil$ $⌈ \frac{Q}{M} ⌉$ .

Time Complexity: $\mathcal{O}(1)$ $O (1)$

Be careful with precision if you decide to use floating point calculations.

Comments

There are no comments at the moment.