| Show all threads Hide all threads Show all messages Hide all messages |
| What is the proper solution? (Got AC with a hack, my solution inside) | araifr | 1569. Networking the “Iset” | 15 Aug 2022 06:52 | 3 |
Could anyone who solved it share the idea?
My solution was: iterate over all vertices i. Fix each i start bfs, so you get a tree (rooted in i). Find it's diameter (from the farthest node v from root i start another BFS and find the farthest node u from v. The distance from u to v would be the diameter).
Across all the diameters find the minimum, that would be the answer.
This solution got WA 8. After random_shuffle() on adjacency lists I've got WA 17.
Now repeat this solution 100 times and you get AC.
So my question is, what is the solution? 1. Find shortest paths from all vertices with Floyd-Warshall or BFSes
2. Brute force all possible tree centers. Note, that a diameter center can be either a vertex or an edge.
Basically, my solution is exactly yours while I believe you've forgotten to check edges that can form a center.
My solution is completely deterministic.
Edited by author 07.11.2018 17:03
Edited by author 07.11.2018 17:03 I just tried all vertices and all edges (meaning pushing both neighbors in priority before BFS starts), then checked tree diameter across all vertices, not just to these roots (there is O(N) algo for that). I used no Floyd-Warshall for candidates, just tried all pairs v1 <= v2, besides I am not sure Floyd will help here because original graph diameter can be shorter than that of resulting tree (e.g. see WA17 topic). |
| What is test 17? | Felix_Mate | 1569. Networking the “Iset” | 15 Aug 2022 06:47 | 3 |
Use this test
6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5 Thanks, helped me to get AC, but first line in your test should be 6 8. Correct answer is diameter 3. |
| Is the edge direct or undirect? | RoBa | 1569. Networking the “Iset” | 15 Aug 2022 06:36 | 2 |
Graph is not oriented. Word "direct connection" in the statement means connection w/o intermediate nodes. |
| Tests (to admins) | Razdolbay from SIS | 1569. Networking the “Iset” | 21 Apr 2014 21:58 | 2 |
Am I right that some AC solutions will be failed on these tests? )
5 10
2 1
3 1
4 2
5 2
3 5
4 5
2 4
5 5
2 2
5 1
10 19
2 1
3 2
4 2
5 1
6 3
7 4
8 6
9 8
10 4
5 2
10 5
8 10
2 7
10 1
7 9
3 6
10 10
10 3
5 3
16 20
2 1
3 1
4 3
5 3
6 2
7 2
8 7
9 8
10 8
11 10
12 8
13 11
14 10
15 12
16 3
9 1
15 2
2 13
2 1
7 15 This network layout is guaranteed to be connected, and there are no links connecting a node with itself. |
| wa #4 | Samsonov Ivan (Rybinsk SAAT) | 1569. Networking the “Iset” | 13 Jul 2010 02:11 | 12 |
wa #4 Samsonov Ivan (Rybinsk SAAT) 7 Oct 2007 19:00 Why BFS doesn't work ? Can you give some tests ? 6 9
5 6
3 4
2 4
1 5
3 6
1 2
1 6
4 5
3 3 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. Re: wa #4 Loky_Yuri [USTU Frogs] 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? 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? 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! 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
What is the complexity of Hakimi algo? I repeat! You don't need Hakimi algo!
Apply your shortests path algo also to the middles of the edges as sink of searching. My program gave the following output:
1 5
3 6
1 2
1 6
4 5
Is that correct? |
| Please add full graph 100x100 | Denis Koshman | 1569. Networking the “Iset” | 14 Aug 2008 14:09 | 1 |
Well, may it's there... but I managed to get 0.14 sec AC with O(N^2*M/2). |
| TO ADMINS | LX&R Bacherikov [KNU] | 1569. Networking the “Iset” | 29 Nov 2007 18:25 | 1 |
TO ADMINS LX&R Bacherikov [KNU] 29 Nov 2007 18:25 The tests are weak!
I submitted simple BFS using adjacency matrix and got WA#8.
But my friend used adjacency list and got AC with the same algorithm.
So, the result depends on the order of edges in the input.
Admins, please, add some tests to fix this problem.
P.S. There is O(nm) correct solution. |
