Editorial for WC '15 Finals S3 - Driving Range
Submitting an official solution before solving the problem yourself is a bannable offence.
Let's consider a single instance of Tiny completing the course for now. Let's say that there are targets at the ends of rows
, and
targets at the ends of columns
, with both arrays
and
sorted in increasing order. It's easy to imagine that it's never optimal for Tiny to drive North or West – instead, he should only move South and East, hitting targets as he goes, in some order. This implies that he'll hit the
row targets in increasing order and the
column targets also in increasing order, with the only question being how they should be interleaved.
This observation suggests a naive recursive solution which tries all possible interleaved orders of targets. We should keep track of how many row and column targets Tiny has hit, and his current row and column. At each step, Tiny can either hit the next row target, if any (by driving South to its row, driving unit East, and firing a missile), or hit the next column target, if any. This recursive process takes
time, yielding an
solution in total.
The above algorithm can be improved with the use of dynamic programming. The recursion can be directly memoized to improve its running time to , which is the number of possible states (with at most two transitions from each state). This yields an
solution in total, where
is the largest
value of any target.
To achieve a dramatically more efficient solution, a different approach to the problem will be required. Before we proceed any further, we should observe that a target in column is special in that it's the only target that can be hit without needing to rotate to face it first – as such, if there's a target in column
, let's simply remove it from the
array (also decrementing
by
), and add
to the answer (as the first move in this case will clearly consist of firing a missile downwards at it).
Now, let's consider counting how many of each type of move Tiny will need to perform. Clearly, he'll fire exactly missiles in total. Additionally, before firing at each target, he'll need to rotate to face it at some point after entering its row/column – this implies needing to drive East a minimum of
times, and South a minimum of
times. Besides these
required moves, it's a fact that Tiny will need to drive South at least
times in total to reach the last row target's row (or
times if
), and similarly East at least
times in total. However, the answer can be smaller than
, because some of the
moves required for rotation can also count towards the
moves required for reaching the last row/column!
Let's assume that the final target that Tiny will hit will be in a row (we'll also want to consider the case in which he hits a column target last, and take the minimum of the two resulting answers). In this case, each of the times that Tiny moves South to rotate himself to hit a column target will also move him towards row
. Therefore, he'll have to drive South exactly
times. On the other hand, each of the
times that Tiny moves East to rotate himself to hit a row target will also move him towards column
except for the last time (because he will already have hit the final column target by then). Therefore, he'll have to drive East exactly
times.
To summarize the above thoughts, the minimum number of moves required to complete the course is , plus
if there's a target in the
column (which we removed from the
array). As such, as targets are added one at a time, all we need to do is maintain the values
,
,
(simply the max target row so far, initialized at
),
(the max target column so far), and a flag for whether or not a target exists in the
column. The time complexity of this is
.
Comments