Hi all,
Problem Link: http://www.usaco.org/index.php?page=viewproblem2&cpid=416
I am trying to conceptually understand what is going on in the internal solution:
So, I understand that rotating the square looks something like this:
The blue squares are the non-lattice squares as per the solution.
Bessie cannot be on those squares, so we need to avoid those when counting.
How does the solution do this?
It seems we go through every row, top to bottom. For each row we do the following:
- Workout the starting column, which is determined by
int start_c = n % 2 == 0 ? 1 : 0;(line 29 of the internal solution)
However, why does this work? I don’t get how that keeps Bessie off the wrong squares as we iterate over the column?