Editorial for TLE '17 Contest 1 P3 - Screensaver 2
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
For
Time Complexity:
For o-|
, where o
is the ball. When the ball goes through the horizontal mirror, it becomes vertical. When the ball hits the second mirror, it bounces back and that mirror becomes horizontal. The ball heads back for the first mirror, which is now vertical. It will bounce off the first mirror and head for the second mirror, which is now passable.
We can then deduce that for every mirror other than the first, if it is vertical, it adds 2 seconds to the ball's travel time. If the first mirror is vertical, it will bounce leftward and the ball will only travel for
To efficiently count the number of vertical mirrors, we can keep track of the state of each mirror and have a count of the initial number of vertical mirrors. When a mirror is updated from vertical to horizontal, subtract one mirror from the count. Otherwise, add one mirror to the count.
Time Complexity:
As an aside, we note that the image of the problem describes an impossible state.
Comments