Обсуждение @ 1325. Грязь @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

The problem was impossible to accept!!! 黄源河 22 апр 2004 21:14

It is possible! Vladimir Yakovlev (USU) 22 апр 2004 22:14

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

Re: It is possible! 黄源河 23 апр 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. Vladimir Yakovlev (USU) 23 апр 2004 11:58

Re: I used Dijkstra algorithm with Heap. SkorKNURE 16 ноя 2008 22:13

Dijkstra via STL priority_queue<> ~0.25 sec
Dijkstra via hand-written heap implemented with change_priority() function ~ 0.125 sec

I have solved it with 2 BFS Oberon (Yura Znovyak) 27 апр 2004 06:12

Re: I have solved it with 2 BFS Failed Peter 28 апр 2004 13:35

how?

1 BFS for finding shortest amount of boot change. Another one for shortest path. Oberon (Yura Znovyak) 28 апр 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. Zieve Cheng 28 апр 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) писал(a) 28 апреля 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. Oberon (Yura Znovyak) 29 апр 2004 17:04

Zieve Cheng писал(a) 28 апреля 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: 1 BFS for finding shortest amount of boot change. Another one for shortest path. Korduban [Kiev] 6 авг 2004 15:28

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

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. Denis Koshman 21 авг 2008 04:00

Try this test:

6 5
1 3
6 3
11111
12222
11112
12222
11112
22222

Correct answer: 7 1

So, after 1st BFS both components stay alive. What would prevent 2nd BFS from going a vertical line and output "6 1" while assumed path yields "6 5"?

Re: 1 BFS for finding shortest amount of boot change. Another one for shortest path. Ta'al 15 май 2014 13:37

I'm sorry, but can anybody describe me 2nd BFS? I spent a lot of time trying, but it give me wrong answer on some tests.

It's right solution. It has implementation in O(N*M). Vladimir Yakovlev (USU) 28 апр 2004 22:59

Re: It's right solution. It has implementation in O(N*M). Zieve Cheng 29 апр 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 (-) Dmitry 'Diman_YES' Kovalioff 29 апр 2004 16:54

I got TL on test 16 :( (-) Oberon (Yura Znovyak) 29 апр 2004 16:58

Re: Of course, Dijkstra + Heap should get AC (-) Zieve Cheng 29 апр 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 писал(a) 29 апреля 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: Of course, Dijkstra + Heap should get AC (-) hello 17 май 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 (-) Zieve Cheng 20 май 2004 18:47

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

hello писал(a) 17 мая 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 (-) hello 26 июн 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. Failed Peter 7 май 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. Oberon (Yura Znovyak) 7 май 2004 23:04

I do not understand :(

Failed Peter писал(a) 7 мая 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 писал(a) 7 мая 2004 18:38

shortest distance by Changing Boots

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

Failed Peter писал(a) 7 мая 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.

Обсуждение задачи 1325. Грязь