TC VegetableGarden

From Algorithmist
Jump to navigation Jump to search

Summary[edit]

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.

Hints[edit]

  • 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.