← All solutions

Shortest judge solution: 1945 bytes. Shortest team solution (during contest): 2738 bytes.

This was one of the last problems solved, and the judges were a bit surprised by how few teams solved it. While the problem requires a bit of work, the hard part of that work is pen and paper calculations without the computer, which is a nice type of work for a three person team with one computer.

The problem has two parts – figuring out which jumps are possible, and then computing the shortest jump sequence from the starting position. The second part is easily solved with a breadth first search so let us focus on the first part. Given a horizontal jump distance d, and a height difference ∆h between the takeoff and landing positions, we need to figure out how to split the total speed v into horizontal speed v_d and vertical speed v_h such that when making a jump with these initial horizontal and vertical speeds, we end up at a height difference of exactly ∆h after having travelled d meters horizontally. From the equations in the problem statement we see that the time t it takes us to travel d meters horizontally is d/v_d, and that after this time our vertical position (relative to where we started) will be v_ht − gt²/2 (follows by integrating the identity for the velocity from 0 to t). Plugging in t = d/v_d and v_h = √(v² − v_d²), we thus need to solve the equation

∆h = (d/v_d) · √(v² − v_d²) − g·d²/(2v_d²) for v_d.

This may look like pretty nasty, but it can easily be transformed into a quadratic equation in v_d²: move the g·d²/(2v_d²) term to the left side, multiply both sides by v_d², and then square both sides (this may potentially introduce spurious solutions since it throws away sign differences).

The expression for the solution gets a bit messy (a tip to make things a bit cleaner is to parameterize v_d² = xv² and v_h² = (1 − x)v² for an unknown 0 ≤ x ≤ 1 and then solve for x instead) but can be found using only pen, paper, and patience; we do not want to spoil the joy of doing the math so leave the details of this to you. Solving this gives (up to) two solutions, one or both of which may be spurious due to the squaring trick above. We observe that if there are two real solutions, it is always better to take the one with higher value of v_h, because that corresponds to making a higher jump. It also turns out that the solution with higher value of v_h is never spurious so we can in fact take it without even checking if it is spurious.

With the calculus out of the way: suppose we now want to check whether we can make a jump from the building at position (x₁, y₁), with height h₁ to the one at position (x₂, y₂), with height h₂. This corresponds to making a jump with height difference ∆h = h₂ − h₁ and horizontal length d = √((x₂ − x₁)² + (y₂ − y₁)²), so we use what we figured out above to determine the jump parameters v_d and v_h (or we figure out that such a jump is impossible). Now that we have the jump parameters we know the exact parabola of the jump trajectory, we also need to check all buildings that lie between (x₁, y₁) and (x₂, y₂) to make sure that the jump trajectory goes above the building. To do this, it is sufficient to check the first and last times where we are over the building in question (because the parabola is concave). Finding the buildings to check can be done in O(d_x + d_y) time but it was OK (at least if the checks were done reasonably efficiently) to do it in O(d_x · d_y) time by simply iterating over all buildings and checking which ones the trajectory passes by. Overall, this leads to an O(d_x²d_y²(d_x + d_y)) or O(d_x³d_y³) running time for building the graph (because we have to do this for all O(d_x²d_y²) pairs of buildings).