Editorial for Mock CCC '19 Contest 1 S3 - Pusheen Eats Tuna Sashimi and Tuna Nigiri - Olympiads Online Judge

Editorial for Mock CCC '19 Contest 1 S3 - Pusheen Eats Tuna Sashimi and Tuna Nigiri

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.

This problem is a homage to CCC 2018 S3, which tripped up competitors who struggled with implementation-centric graph theory problems.

This problem is solvable with a BFS. We can track Pusheen's state in terms of four variables - her $x$ ~x~-coordinate, $y$ ~y~-coordinate, velocity in the $x$ ~x~-dimension, and velocity in the $y$ ~y~-dimension. It looks like there are $X^2Y^2$ ~X^2Y^2~ distinct states but the theoretical maximum is actually on the order of $\sqrt{X^3Y^3}$ ~\sqrt{X^3Y^3}~ since velocities which are too large will force Pusheen into illegal territory.

The major implementation detail to be concerned about is flying over illegal lattice points. Checking every point to see if it is on the line segment is too slow, instead we can take a line segment and iterate over the lattice points it covers manually and check if any of those are bad.

The first three subtasks do not require dealing with this implementation detail.

The first subtask removes two of the dimensions completely, and the second subtask is equivalent to maintaining two one-dimensional states.

Comments

There are no comments at the moment.