Editorial for WC '16 Contest 2 S3 - Turbolift Testing
Submitting an official solution before solving the problem yourself is a bannable offence.
Solving this problem efficiently requires precomputing various useful values, and then using them to answer the questions.
Let's consider each of the button sequences. Assuming that sequence
is executed with the turbolift starting at floor
, let
be the length of the sequence,
be the turbolift's final floor,
be the highest floor reached at any point during the first
button presses of the sequence,
be the lowest floor reached during the first
button presses,
be the highest floor reached at any point during the whole sequence (equal to
), and
be the lowest floor reached (equal to
). These values can all be easily computed by simulating the sequence's button presses in
time, which is sufficient as the sum of the sequences' lengths is at most
.
Next, let's repeat a similar process over the entire sequence of button sequences. Let
be the total length of the first
executed sequences,
be the turbolift's final floor after the first
sequences,
be the highest floor reached at any point during the first
sequences, and
be the lowest floor reached during the first
sequences. These values can similarly be easily computed in
time, with the help of the precomputed
,
,
, and
values. Note that
.
Finally, we're set up to answer the questions efficiently. Let's say we're interested in the first button presses. The
-th button press must occur during some sequence
– in particular, during the first sequence
such that
. Since the values
are increasing, we can use binary search to determine the value of
in
time. Now, since the first
button sequences have been completed before the
-th button press, the highest floor reached during the first
button presses is at least
. However, the first
button presses of button sequence
were additionally executed after that, which is where more of our precomputed values come into play – the answer must be
. Similarly, the minimum floor reached is
.
The time complexity of this algorithm is .
Comments