You are not logged in. Please login at www.codechef.com to post your questions!

×

NEERC 2008 Drive Through Megacity

I found this problem the most interesting out of all the problems. Here is the link to the contest: http://codeforces.com/gym/100286/. It's problem D.

I tried to solve it using djkstra. I was trying to create a DAG, by always going forward ( increasing x ) until I hit a rectangle. After that I had 3 options, go through the rectangle, go up till the top of the rectangle and go down to the bottom. Then, I found a test case for which it didn't work.

Later I figured, in the optimal path, all my horizontal paths will have y coordinates parallel to the rectangles bottom or top and all my vertical paths will have x coordinates parallel to the sides. With 1000 rectangles, I can have 2000 unique y-levels and 2000 unique x-levels. Therefore I can divide the whole grid into a 2000 by 2000 grid. Then run djkstra through it. The difficulty with this idea is to determine if the path is inside a rectangle, outside or on the boundary.

That's all the idea I got. Didn't find anything over the net either.

asked 15 Sep '14, 20:43

forthright's gravatar image

4★forthright
56641217
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×631
×4
×4
×2
×1

question asked: 15 Sep '14, 20:43

question was seen: 6,230 times

last updated: 15 Sep '14, 20:43