Baltic OI 2013 - Tracks in the Snow

Link to problem & solution.

In the statement, we are asked to find the “minimal possible number N >= 1 of animals that must have crossed the meadow to leave the given pattern of tracks in the snow”.

The only thing I can’t wrap my head around is how the answer could ever be more than 2. From what I understand, animals have complete freedom of movement, (“they can move back and forth, playing in the snow, even crossing their own tracks”), so it’s always possible for them to walk over previous patterns. From my logic, the answer would be 1 if only one animal pattern is visible on the grid, and 2 if there are 2.

I’ve reread the question multiple times, and sketched out numerous random cases, yet can’t find where I’m going wrong, although I’m sure it’s painfully obvious.

Can someone point to a case where the minimum number of animals could be more than 2 / where my logic is wrong?


You need a lot of animals to create the pattern on the top.
Hint: Simulate the foxes and rabbits by hand, going backwards from the last animal. How would you optimize/simplify this by translating it to a shortest path problem?

1 Like

Just what I needed :+1: