Internet Problem Solving Contest

IPSC 2009

Solution to Problem B – Bouncing balls

Simulation of bouncing balls might be slightly problematic, in both implementation and computational aspects. Fortunately, there are several interesting restrictions given in the input specification, especially the fact that all balls have the same speed and they move only diagonally.

In fact, thanks to this setting we can simply ignore collisions of the balls with each other. Visually, we would get exactly the same view if we allowed the balls to pass through each other.

Hence we only have to handle the collisions between each ball and the walls. To do this, it is enough to note that the x coordinate of each ball is periodic with a period 2X, and the y coordinate is periodic with a period 2Y .

Thus we can simply process the balls one by one, for each of them we compute its final position in O(1), and then we just sort and output these.