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???

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???

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*