Editorial for TLE '17 Contest 1 P3 - Screensaver 2


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: ZQFMGB12

For 50\% of the points, it suffices to simulate the ball's movement for each query.

Time Complexity: \mathcal{O}(NT)

For 100\% of the points, we need to make an important observation. We consider the case that the ball is about to go through a system of mirrors like so: 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 1 second. If the first mirror is not vertical, we count the number of vertical mirrors and add 2 seconds to the time it would take for the ball to reach the end unobstructed (N seconds) for each mirror.

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: \mathcal{O}(N+T)

As an aside, we note that the image of the problem describes an impossible state.


Comments

There are no comments at the moment.