As I mentioned in my post introducing Project 462, I have spent some time in the past working on historical CodeForces problems to get some idea of what their programming competitions are like. I thought it would be interesting to go through one of those problems, Hot Bath, from the perspective of a CodeForces beginner. In CodeForces Beta Round #93, Hot Bath was Problem C in the Division 2 contest, and Problem A in the Division 1 contest. In the CodeForces system, that means the problem is targeted at Division 1 (more experienced) contestants who are just getting their fingers warmed up at the beginning of a contest, and at Division 2 (less experienced) contestants who have finished a couple of easier problems, and are ready for something that requires more thinking. Based on the information in the standings report for that round, several top Division 1 contestants submitted an accepted solution in about ten minutes, so we can take that as a reasonable lower bound.
The first challenge in solving a programming problem is understanding the problem statement. For contest beginners, it can sometimes take more than ten minutes just to do that! Part of the difficulty is how the problems are written, which in my opinion is not as clear as it could be. So I find it useful to re-write the important parts of the problem. If I were to rewrite the Hot Bath problem statement to be more understandable, it would sound something like this:
The Problem
You have a bathtub with two taps (cold and hot). Each tap pours out water at a fixed temperature. You can control the flow rate of each tap separately. For each tap, you can set the rate from 0 to the maximum rate for that tap. You are given the cold temperature, the hot temperature, the two maximum rates, and a target temperature. Your job is to fill the bathtub as fast as possible, while keeping the water temperature as close as possible to a target value. However, you must not make the water any colder than the target.
Let these variables represent the givens:
- $t_1$: the cold tap temperature
- $t_2$: the hot tap temperature
- $x_1$: the maximum cold tap rate, in units per second (an integer value)
- $x_2$: the maximum hot tap rate, in units per second (an integer value)
- $t_0$: the target temperature
If you set the cold tap to a rate of $y_1$ units per second and the hot tap to a rate of $y_2$ units per second, then the bath water temperature will be the weighted average of the temperature of the water entering the tub. You can calculate this temperature as follows:
(1) $$ t = \frac{t_1y_1+t_2y_2}{y_1+y_2} $$
The target temperature $t_0$ is guaranteed to be greater than or equal to the cold temperature and less than or equal to the hot temperature, so that the problem is guaranteed to have a solution. You need to find $y_1$ and $y_2$, the rate of each tap that will produce the optimal value for $t$.
That’s the end of the problem statement, except for one important detail that I’ll reveal shortly. If you read through it a few times, the problem itself isn’t too complicated. Or maybe you find it simple after just one reading, in which case you’re ahead of the game.
Solution Ideas
Since the problem statement gives us a formula for the temperature and we know the range of legal values, one obvious solution idea is just to try every value and save the best result:
for each y1 from 0 to x1
for each y2 from 0 to x2
calculate t using y1 and y2
if t >= t0 and is closer to t0 than any previous t,
save the current t, y1, and y2 values as the best
found so far
output the best y1 and y2 values found
It turns out that this solution doesn’t work on CodeForces. To prevent contestants from using it, the puzzle authors cleverly set the range set the range of the $x_1$ and $x_2$ values to $1 \leq x_1,x_2 \leq 10^6$, which eliminates any possibility of this $O(n^2)$ algorithm completing in the allotted time (a few seconds) for all test cases. (That’s the important detail that I left out of the problem statement).
But we don’t have to give up on the solution entirely. It turns out that we can use a slightly more clever brute force solution that relies on eliminating the inner (hot tap) loop. For each cold tap rate, we can calculate a corresponding hot tap rate that allows us to check only a subset of the hot tap values and still find the optimal pair.
Here’s how to do that: rather than looping through all possible hot rates, we can use the supplied formula along with the current cold rate, the cold and hot temperatures, and the target temperature to calculate the optimal corresponding hot rate. To do that, we need to solve the temperature formula for $y_2$ (hot rate), using the following algebra:
$$ t = \frac{t_1y_1+t_2y_2}{y_1+y_2} $$ $$ t(y_1+y_2) = t_1y_1+t_2y_2 $$ $$ ty_1+ty_2 = t_1y_1+t_2y_2 $$ $$ ty_2-t_2y_2 = t_1y_1-ty_1$$ $$ y_2(t-t_2) = y_1(t_1-t) $$ $$ y_2 = \frac{y_1(t_1-t)}{t-t_2} $$
(2) $$ y_2 = \frac{y_1(t-t_1)}{t_2-t} $$
The last step is not strictly necessary, but it ensures that the temperature values are positive when we use this formula in the algorithm, since $t_1 \leq t_0 \leq t_2$. That simplifies the code a bit.
When we’re inside the cold rate loop, the variables in this formula will represent the following values:
- $y_1$: the current cold rate
- $t_1$: the cold temperature
- $t_2$: the hot temperature
- $t$: the target temperature, $t_0$
- $y_2$: the hot rate
The result, $y_2$, is a floating point number representing the hot rate that will produce a water temperature of exactly $t_0$ when the cold rate is $y_1$. But the problem statement says the tap rates are integers, so we won’t be able to the calculated $y_2$ value in most cases. To convert the result to an integer, we can use $\lceil y_2 \rceil$ (the ceiling function). In general, that will give us a temperature value that differs from the target. We’ll need to calculate how much it differs, and then whether we found a temperature that is closer to the target than we have seen so far.
The Algorithm
Now that we have a good idea of how to solve the problem, it’s time to work out the details of the algorithm.
One detail to work out is what to do in a few special cases. First, what happens when the cold or the hot temperature (or both) is equal to the target temperature. If the cold temperature is equal to the target temperature and the hot temperature is some other value, then we can match the target temperature exactly by just using the cold tap and leaving the hot tap off. And since we want to fill the bath as fast as possible, we need to use the maximum rate. There is an analogous case when the hot temperature is equal to the target. If both temperatures are equal to the target, then we can use the maximum rate for both taps.
Is there any other case where we should leave the cold tap off to get the optimal temperature? It turns out that the answer is no. In other words, the special case in which $t_2=t_0$ is the only situation in which $y_1=0$ is the optimal cold rate. To see why this is, consider a case where $t_2 \neq t_0$ (the hot temperature is not equal to the target). Then it must be true that $t_2>t_0$ (the hot temperature must be greater than the target) because we know that the target is between the hot and cold temperatures. So we can always get closer to $t_0$ by applying some cold water — that is, by applying water with temperature $t_1 \leq t_0$. Therefore, when we are looping through cold temperature values to find the optimal one, the values we need to loop through are the integers $1 \leq y_1 \leq x_1$.
Here are the steps for that cold rate loop from $1$ to $x_1$:
- Using the current cold rate (loop variable $y_1$) and the givens, calculate a hot rate $y_2$ using equation (2), and round up to the nearest integer $\lceil y_2 \rceil$.
- If $y_2$ is not in the range $0..x_2$, it’s not a valid rate, so skip the remaining steps and continue with the next iteration.
- Using equation (1), calculate the actual temperature $t$ produced by the current $y_1$ and $y_2$.
- If $t < t_0$, continue loop
- If $t$ is closer to $t_0$ than any $t$ found so far, save $t-t_0$, $y_1$, and $y_2$.
When the loop is complete, the saved $y_1$ and $y_2$ will be the values that produce the optimal temperature and total rate.
Implementation
The algorithm as described above contains enough detail to implement the solution to this problem. The structure of the complete program looks like this:
read givens
if any of the special cases apply, return result
otherwise, implement the cold rate loop as shown
print the best values found in the loop
One decision to make when implementing the algorithm is whether to use any floating point variables, or only integers. The floating point implementation is conceptually simpler, but you need to be careful about rounding issues when comparing values. The standard way to avoid unexpected results when comparing floats is to select a small epsilon value, and verify that numbers are within this value rather than strictly equal. For the integer implementation, the challenge is that you can’t use the formulas as-is, since they produce floating point results. For my implementation, I decided to use floating point values.
Key Concepts
The solution to Hot Bath can be implemented in under 75 lines of code, and the algorithm is mostly brute force. This is why the best competitive programmers can finish it in about 10 minutes. The main insight required to solve the puzzle is realizing that formula (1), the one given in the problem description, must be manipulated into form (2). This provides an efficient way to calculate the optimal $y_2$ for any $y_1$, rather than having to consider every $(y_1,y_2)$ combination, which is impractical given the input ranges.
Despite the apparent simplicity of the solution, there are some tricky details to consider. For someone like me who hasn’t yet solved a lot of these types of puzzles, it’s plenty challenging. First you have to get the insight about how the formula given in the problems statement needs to be transformed. Then you need a “half brute-force” algorithm using the modified formula, Finally, there are the implementation details about how to work with floating point numbers while preserving correctness or, alternatively, how to adjust the formulas so that integer data types can be used. Looking at the steps required to come up with an implementation from scratch, it seems amazing that top contestants could come up with a solution in barely more time than it takes to type the code. But it’s a characteristic of complex skills that what seems impossible from the perspective of a beginner turns out to be a routine performance for people with who have been doing the right kind of practice for long enough.
(Image credit: Leigh Ann)