← All solutions

Shortest judge solution: 568 bytes. Shortest team solution (during contest): 1432 bytes.

Effectively, every knock on the pipe answers the question “did the Flubber already get to this point”, which tells us “is the velocity of the Flubber greater or equal to the minimum speed needed to get to this point.” So, the problem would be very easy if the pipe had infinite length.

For an infinitely long pipe, we would simply run a binary search on the velocity, and return the answer in ⌈log₂((v₂−v₁)/t)⌉ knocks. However, due to the finite length of the pipe, some velocity queries are impossible to make after some points in time. This may cause the whole binary search to be impossible to perform (as in sample input 3), or it may cause us to have to adapt the search, possibly using more queries (as in sample input 2).

Notice that the effect of the flubber moving out of the pipe is that some queries about the last parts of the velocity interval become illegal. This means that if the velocity is in some final part of the possible interval, and we have not determined what it is yet, we will not be able to determine it in the future. So, our knocking plan must be able to tell these velocities apart before the flubber flows out.

Let us describe how we will construct a good strategy of knocking at the pipe. We will always knock as soon as we can (that is, at s, 2s, 3s, etc. seconds) After k knocks, our strategy will have already adapted to determine the velocity (within a t error range) in some final range of the velocity interval, and we are still searching in the range [v₁, v(k)]. If not for the need to determine some answers fast, we would have, at this point, divided the range of velocities into 2^k intervals, and the strategy would tell us in which of these intervals the real answer is. However, some of these potential intervals might have been used up – so, the range of [v₁, v(k)] is only divided into some smaller number n(k) ≤ 2^k intervals, and our strategy will tell us in which of these intervals the answer is. If t · n(k) ≥ v(k) − v₁, we can just let these intervals be an equidivision of the velocity range, and k is going to be the number of knocks our strategy uses.

The initial values are easy: v(0) = v₂ and n(0) = 1 – before knocking, we are searching the [v₁, v₂] range, and the range is “divided” into a single interval. Let’s see what happens when we add another knock. Before we do this, we need to determine what range of velocities becomes impossible to query (if any) — the higest velocity that’s possible to query at time k is simply v_f(k) = l/(s(k+1)). We need to determine the velocity of the Flubber for velicities above v_f(k) + t in the first k steps. In other words, if v(k) > v_f(k) + t, then we need to “use up” n_f(k) = ⌈(v(k)−v_f(k)−t)/t⌉ intervals out of our n(k) intervals to make sure we cover the high velocities with sufficient accuracy before it is too late. For the remaining n(k) − n_f(k) intervals, we do not decide yet what are they going to be, but whatever they are, we ask a new query to split them in two. Thus, n(k + 1) = 2(n(k) − n_f(k)), and v(k + 1) = v(k) − n_f(k) · t.

This analysis allows us to solve the problem. We will iterate over k, keeping track of v(k) and n(k). Once t · n(k) ≥ v(k) − v₁, we can answer k. If n(k) drops to zero or below at any point, we answer “impossible”. becomes how big k can become? It’s pretty difficult to get an accurate estimate, but after getting some intuition for the problem, it is relatively easy to believe that it’s not going to be very high. The worst test case we found (subject to the input bounds in the problem) had an answer of 74. If you can beat this, please let us know!