Editorial for WC '16 Contest 1 S1 - Hide and Seek
Submitting an official solution before solving the problem yourself is a bannable offence.
This problem can be approached greedily. If we consider the leftmost room , Michael's leftmost chosen room
might as well be the rightmost possible room such that
and
are within
units of each other, since that'll cover not only room
, but as many more rooms to the right of
as possible. In particular, if room
is the rightmost room which is within
units of room
, then room
will cover all rooms between
and
(inclusive).
Therefore, if we can determine the locations of these rooms
,
, and
, then we can add room
to Michael's list of chosen rooms, and henceforth ignore room
and all rooms left of it, thereby reducing the problem to only the section of the hallway to the right of room
. At that point, we can repeat this process until there are no more rooms remaining to the right of room
.
The first step is to find room . Let's define
to be the leftmost character of room
, and
to be its rightmost character (and similarly for rooms
and
).
is simply the first
.
in the floor plan. is then the character before the first
#
after .
The second step is to find room . The furthest character in range of room
is
. If that character is a
.
, then it's inside room , and so
is the character before the first
#
after . Otherwise, room
must be to the left, so
is the last
.
before . We don't need to find
.
The final step is to find room . The furthest character in range of room
is
. We can repeat exactly the same process as above to find
. Once again, at that point, we can add
to the answer (since Michael will need to visit room
), and repeat the process with the remainder of the string to the right of
.
Comments