Discussion @ 1325. Dirt @ Timus Online Judge

Pages: 1 2 Next

The problem was impossible to accept!!!

Posted by 黄源河 22 Apr 2004 21:14

It is possible!

Posted by Vladimir Yakovlev (USU) 22 Apr 2004 22:14

see this:
http://acm.timus.ru/status.aspx?space=1&pos=574747

Re: It is possible!

Posted by 黄源河 23 Apr 2004 11:27

How can you do it, I'am puzzled. Can you solve it today???

Edited by author 23.04.2004 11:29

I used Dijkstra algorithm with Heap.

Posted by Vladimir Yakovlev (USU) 23 Apr 2004 11:58

I have solved it with 2 BFS

Posted by Oberon (Yura Znovyak) 27 Apr 2004 06:12

Re: I have solved it with 2 BFS

Posted by Failed Peter 28 Apr 2004 13:35

how?

1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Oberon (Yura Znovyak) 28 Apr 2004 17:47

First. You can contract all regions in one vertex.
Second. You can find shortest distance by regions.
Third. Remove useless regions. BFS what was left.

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Zieve Cheng 28 Apr 2004 21:47

I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail.

Oberon (Yura Znovyak) wrote 28 April 2004 17:47

First. You can contract all regions in one vertex.
Second. You can find shortest distance by regions.
Third. Remove useless regions. BFS what was left.

It's right solution. It has implementation in O(N*M).

Posted by Vladimir Yakovlev (USU) 28 Apr 2004 22:59

Re: It's right solution. It has implementation in O(N*M).

Posted by Zieve Cheng 29 Apr 2004 12:10

Now I know that's used colouration.

Edited by author 29.04.2004 16:37

Of course, Dijkstra + Heap should get AC (-)

Posted by Dmitry 'Diman_YES' Kovalioff 29 Apr 2004 16:54

I got TL on test 16 :( (-)

Posted by Oberon (Yura Znovyak) 29 Apr 2004 16:58

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Oberon (Yura Znovyak) 29 Apr 2004 17:04

Zieve Cheng wrote 28 April 2004 21:47

I don't agree your opinion.The method can't work out in time.This method I had used to solve,but fail.
Why?
I have impelemnted in O(N*M) --> AC in 0.359 s

Re: Of course, Dijkstra + Heap should get AC (-)

Posted by Zieve Cheng 29 Apr 2004 17:29

But it wastes much time,such as me,used 0.906s to accept.And I used many optimize skill to make it run fast and get accept so hard.
http://acm.timus.ru/status.aspx?space=1&pos=582582

Dmitry 'Diman_YES' Kovalioff wrote 29 April 2004 16:54

Now I used colouration and got accepted in short time,only 0.234s.And the method carry out easily.
http://acm.timus.ru/status.aspx?space=1&pos=583722

Edited by author 30.04.2004 17:44

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Failed Peter 7 May 2004 18:38

but i think it's possible that such condition appears:

in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes.
but these ways are different in shortest way of Walking.
So?

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Oberon (Yura Znovyak) 7 May 2004 23:04

I do not understand :(

Failed Peter wrote 7 May 2004 18:38

in the first BFS to find shortest distance by Changing Boots,there may be many ways to get the shortest Changes

First BFS is for

Failed Peter wrote 7 May 2004 18:38

shortest distance by Changing Boots

Then we throw away all useless regions and use SECOND BFS for

Failed Peter wrote 7 May 2004 18:38

shortest way of Walking

Of course for each region we store min boot change to get to it. While finding shortest walking distance we almost ignore regions. Why almost: we make jumps only on regions with higher boot changes. So we can avoid saw-like regions.

Re: Of course, Dijkstra + Heap should get AC (-)

Posted by hello 17 May 2004 17:40

So fast !!!!!!
I got TLE on test 16 all the time ........
I don't know what does "colouration" mean .
Could you explain ?
Could you say your way ?

Re: Of course, Dijkstra + Heap should get AC (-)

Posted by Zieve Cheng 20 May 2004 18:47

Oberon (Yura Znovyak) had told the method very clarity.

hello wrote 17 May 2004 17:40

So fast !!!!!!
I got TLE on test 16 all the time ........
I don't know what does "colouration" mean .
Could you explain ?
Could you say your way ?

Re: Of course, Dijkstra + Heap should get AC (-)

Posted by hello 26 Jun 2004 11:32

Thanks .
I just uesd 0.187s to get AC !

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path.

Posted by Korduban [Kiev] 6 Aug 2004 15:28

It's very nice method! I have got AC in 0.203s

Pages: 1 2 Next

Discussion of Problem 1325. Dirt