Editorial for VPEX P3 - Coding Club


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.

Subtask 1

The values are so small, it is enough to simply simulate the rectangle, changing its direction every time it bounces off a wall.

When the box has the same position and is travelling in the same direction as it started in, the animation will begin to loop.

Time Complexity: about \mathcal O(AB), depending on implementation

Subtask 2

Instead of an A \times B logo bouncing around a W \times H screen, you can focus on the bottom left point bouncing around a (W-A) \times (H-B) box. This can then be imagined as a point travelling in a line through an infinite grid of (W-A) \times (H-B) cells.

When the point travels through an even number of cells vertically, it will have bounced an even number of times vertically. Same thing for the horizontal direction. When this has happened, the box will be travelling in its starting direction.

The box also needs to have travelled to its original position, so the vertical and horizontal displacement must be divisible by the cell height and width.

If a is the horizontal displacement, and b is the vertical displacement, you have a \bmod W = 0 and b \bmod H = 0. Write this as a = mW and b = nH.

From the slope, also \frac b a = \frac y x.

Then \frac{nH}{mW} = \frac y x and yWm = xHn = \operatorname{lcm}(yW, xH) because it's the first time this happens. So:

\displaystyle \begin{align*}
a &= \frac{\operatorname{lcm}(yW, xH)}{y} \\
b &= \frac{\operatorname{lcm}(yW, xH)}{x}
\end{align*}

The distance is \sqrt{a^2+b^2}, and travelling at one unit/second, it's also the time taken.

You can also see that the output will never be -1.

Remember the special cases where x = 0 or y = 0, where the point only travels in one direction.

Also, remember to store your output as a double to avoid integer overflow.

Time Complexity: \mathcal O(1)


Comments

There are no comments at the moment.