The following is not from a puzzle book but from the competitive programming website
HackerRank. The problem in question was
Strange Counter from the Algorithms section. I felt that the discussion was not adequate for help in solving the problem but I was able to write my own solution and share it with the others. Here is a full explanation. First, let's include a bit of the problem description:
Bob has a strange counter. At the first second $t = 1$, it displays the number $3$. At each subsequent second, the number displayed by the counter decrements by $1$.
The counter counts down in cycles. In the second after the counter counts down $1$, the number becomes $2 \times$ the initial number for that countdown cycle and then continues counting down from the new initial number in a new cycle. The diagram below
shows the counter values for each time $t$ in the first three cycles:
In other words, first there is a countdown from $3 * 2^0$, then a countdown from $3 * 2^1$, then a countdown from $3 * 2^2$, and so it goes. If it looks like the sum of a geometric series is being used here, it absolutely is. Recall that the sum of the first $n$ terms of a geometric series is (justification
here):
$$a \frac{1 - r^n}{1 - r}$$
And in this particular instance, the formula is:
$$3 \frac{1 - 2^n}{1 - 2}$$
This information is very useful for solving the problem without any kind of brute force. Given $t$, it is possible to know directly how many of these countdowns have already passed by completely. The length of these past countdowns can then be subtracted from $t$, and then $t$ can be subtracted from the length of the current countdown to find the value of the counter. Before going any further with the mathematics, consider a number of examples:
- At $t = 1$, no counters have passed by completely. The current counter is therefore the counter that goes from three down to one. Because the counter indexing is one-based (like vectors in R, let's say), the value of the counter is $3 - t + 1$ or very simply three.
- At $t = 2$ and $t = 3$, the same reasoning applies and the values of the counter are, respectively, two and one.
- At $t = 4$, however, a full prior countdown has now passed. The reasoning is different here. The current countdown goes from six to one. Subtracting the length of the previous countdown from $t$ is necessary to find out what $t$ indexes relative to the current countdown. Because the length of the prior countdown was three, then the value of the counter is $6 - (t - 3) + 1$ or very simply six.
- The same reasoning applies for $t \in \{5, 6, ... , 9\}$
- At $t = 10$, two entire counters have passed by entirely. Their lengths, three and six, need to be added together and subtracted from $t$ so that the value of the counter can be found. Then applying the previous reasoning results in the value of 12 for the current value of the counter.
So far it seems like there are two central questions here:
- What counter does $t$ belong to?
- What offset needs to be subtracted from $t$ so that it can be used to index the current counter?
The answer these questions, note that $t$ is greater than or equal to the summed lengths of zero or more countdowns that have fully elapsed. This can be stated accordingly:
$$t \ge 3 \frac{1 - 2^n}{1 - 2}$$
Then:
$$
\begin{align*}
t &\ge 3 \frac{1 - 2^n}{1 - 2} \\
t &\ge \frac{3 - 3 \cdot 2^n}{1 - 2} \\
t &\ge \frac{3 - 3 \cdot 2^n}{-1} \\
t &\ge -3 + 3 \cdot 2^n \\
t + 3 &\ge 3 \cdot 2^n \\
\frac{t + 3}{3} &\ge 2^n \\
\log \left( \frac{t + 3}{3} \right) &\ge \log \left( 2^n \right) \\
\log \left( t + 3 \right) - \log \left( 3 \right) &\ge \log \left( 2^n \right) \\
\log \left( t + 3 \right) - \log \left( 3 \right) &\ge n \cdot \log \left( 2 \right) \\
\frac{\log \left( t + 3 \right) - \log \left( 3 \right)}{\log \left( 2 \right)} &\ge n
\end{align*}
$$
This means, all told, that:
$$n \le \frac{\log \left( t + 3 \right) - \log \left( 3 \right)}{\log \left( 2 \right)}$$
In programming terms, $n$, the number of fully elapsed countdowns that happened before timestep $t$, can be determined by evaluating the right-hand expression and then finding its floor (i.e. the largest integer less than or equal to it).
After doing this, the offset, namely the sum of the first $n$ terms of the geometric series can be evaluated as described above for this value of $n$ and subtracted from $t$. This value can then, in turn, be subtracted from the length of the current counter, which is $3 * 2^n$, to find the current value of the counter, with one exception: when $t$ indicates the final value of the current counter, namely, one. Here the current counter has ended, but the next has not yet begun. This case can be detected by the fact that $t$ minus the offset is equal to zero. The case can then be handled simply by printing one. In all other cases, the process I described above applies. Finally, implementing the algorithm in Scala, we have a very short and efficient program indeed:
import scala.io.StdIn
import scala.math._
object Solution extends App {
val t = StdIn.readLine().toDouble
// for the expression 3 * (1 - 2^n) / (1 - 2) which is the sum of the first n terms of the series
val n = ((log(t + 3) - log(3)) / log(2)).floor
val offset = 3 * (1 - pow(2, n)) / (1 - 2)
if (t - offset == 0) {
println(1)
} else {
println(f"${3 * pow(2, n) - (t - offset) + 1}%.0f")
}
}
Notice that, in the
else clause above, the output is formatted so that the
Double used for calculation will appear to be an integer. This is not a fundamental part of the algorithm but simply a requirement for the code judge to accept the output.
