TC VegetableGarden
From Algorithmist
[edit] Summary
This problem seems to be pretty tricky (only 4 people got it right) but the solution is fairly short. It takes place on a rectangular grid. You have to walk around inspecting certain plots of land but not inspecting others.
From TopCoder Single Round Match 340.
[edit] Hints
- The constraint "Your path must not intersect itself" can be ignored.
- Given any square S, let R be any infinite ray leaving that square. Then after you return to the origin, S is inside your path if and only if your path intersects R an odd number of times.
