Editorial for Mock CCC '19 Contest 1 S3 - Pusheen Eats Tuna Sashimi and Tuna Nigiri
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 -coordinate,
-coordinate, velocity in the
-dimension, and velocity in the
-dimension. It looks like there are
distinct states but the theoretical maximum is actually
on the order of
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