ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1623. Fractal Labyrinth

Why so few ACs???
Don't understand - the algorithm is just Floyd, and so few people solved this problem...
Re: Why so few ACs???
Posted by Al.Cash 24 Aug 2008 22:07
Do you think I understand why I have WA#6?
Re: Why so few ACs???
Posted by Denis Koshman 26 Aug 2008 09:55
I had WA6 when I spread minimum over inner houses to all others (including outer). This is wrong, you should consider only outer house as a new inner one. But now I have WA16 :)

Edited by author 27.08.2008 11:19
Re: Why so few ACs???
Posted by Denis Koshman 27 Aug 2008 11:27
WA16 was that I added roads leading from some house to itself as such road for every house. This is also wrong.
Re: Why so few ACs???
Posted by svr 28 Nov 2008 08:54

I start my solving with two hypotheses:
1. It is enough to use only one inner room.
2. Using this room it is enough edges between two rooms inner and outer consider as edges on boundary of outer room.
It typical for contest. You achievements determined by your
first quick considerations.

WA6. Not so simple. More rightly to consider functional
equation for dist[i,j].This equation solved by method of
relaxation as a Laplas equation.

AC at last. The problem indeed very simple and very based
on the Floyd. But a man must have big contest experience
to catch all logical moments.

Edited by author 28.11.2008 20:58