Discussion @ 1569. Networking the “Iset” @ Timus Online Judge

Samsonov Ivan (Rybinsk SAAT) wa #4 [11] // Problem 1569. Networking the “Iset” 7 Oct 2007 19:00

Please give some test

Todor Tsonkov Re: wa #4 [10] // Problem 1569. Networking the “Iset” 7 Oct 2007 22:00

Why BFS doesn't work ? Can you give some tests ?

Victor Barinov (TNU) this test helped me to get AC // Problem 1569. Networking the “Iset” 7 Oct 2007 22:27

6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5
3 3

shilp Re: wa #4 [8] // Problem 1569. Networking the “Iset” 7 Oct 2007 22:42

i make a shortest path tree (i know i do it correctly) from the every vertex of the graph, but even that is giving me a WA on #17... can someone please give me a test case where that would fail?

@Todor
BFS won't work in a case like
6 6
1 2
2 5
1 3
3 5
3 6
3 4

if you make a BFS tree by searching the lower indexed vertices, starting from 1, then 5 would be committed under 2 where as it should be committed under 3,
even if you are constructing a tree from 3 in the above case i am sure a case can be formed that the above anomaly is exploited.

Loky_Yuri [USTU Frogs] Re: wa #4 [7] // Problem 1569. Networking the “Iset” 7 Oct 2007 22:55

I have WA #17 too. But I don't understand why in your test BFS doesn't work?
6 6
1 2
2 5
1 3
3 5
3 6
3 4
My prog gives this answer:
1 2
1 3
3 4
3 5
3 6
It's correct, isn't it?

shilp Re: wa #4 [6] // Problem 1569. Networking the “Iset” 7 Oct 2007 23:31

its correct.. yes..
i am saying that a BFS would construct the shortest paths for sure, but it would do so in a greedy format that will most probably give a graph with a sub-optimal diameter, so perhaps will a shortest path tree.. i even tried constructing the BFS with highest degree first but none of it seems to work..

any idea?

diver_ru (Fishburg SAAT) WA 17? Look here(+) [5] // Problem 1569. Networking the “Iset” 9 Oct 2007 16:32

Look at the test, given by Victor (thanks him):
6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5

Answer will be
1 5
2 4
3 4
5 4
6 5
and maximum distance equal 3 (in edges), not 4!

svr Re: WA 17? Look here(+) [3] // Problem 1569. Networking the “Iset” 16 Oct 2007 00:04

How are you may start BFS programming
without mathematical characterization of
optimal solution. I found with difficulties
in internet that it is tree of shortest pathes
from absolute centre of graph.
Thus you need in two programs
1) Finding absolute centre(Hacimi)
2) Dejkstra for shortest paths.

P.S. Glad to confirm with help of 1569 My Hakimi algorithm realization.
But, of course, we don't need Hakimi algo to solve this problem. When edges have equal wheightes absolute centre
or in vertex or in middle of the edge.

Edited by author 02.06.2008 16:18

Denis Koshman Re: WA 17? Look here(+) // Problem 1569. Networking the “Iset” 14 Aug 2008 13:52

I have found algo here:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.5609

Thanks Victor for his test, I've found a bug (as usual, I used some outer loop variable inside inner loop. ARGHHHHH!)

Edited by author 14.08.2008 14:01

Edited by author 14.08.2008 14:01

Tolstobrov Anatoliy[Ivanovo SPU] Re: WA 17? Look here(+) [1] // Problem 1569. Networking the “Iset” 25 Sep 2008 20:12

What is the complexity of Hakimi algo?

svr Re: WA 17? Look here(+) // Problem 1569. Networking the “Iset” 25 Sep 2008 21:28

I repeat! You don't need Hakimi algo!
Apply your shortests path algo also to the middles of the edges as sink of searching.

Azad Re: WA 17? Look here(+) // Problem 1569. Networking the “Iset” 13 Jul 2010 02:11

My program gave the following output:

1 5
3 6
1 2
1 6
4 5

Is that correct?

Discussion of Problem 1569. Networking the “Iset”