| Show all threads Hide all threads Show all messages Hide all messages |
| Some test | Kollekcioner[Vologda, VML1] | 1416. Confidential | 25 Apr 2020 06:26 | 8 |
Some test Kollekcioner[Vologda, VML1] 15 Aug 2007 00:23 If you have WA25 and low try this test:
8 9
1 2 1
2 3 5
3 4 3
4 5 4
3 6 1
3 7 2
3 8 9
6 8 9
7 8 8 AC answer:
Cost: 24
Cost: 25 What?
The right answer should be
Cost: 24
Cost: -1
Reply to the upper
Edited by author 04.04.2011 20:38 I think answer should be 24 24, as my program does. We can replace 3->8 with 3->6 and it changes nothing. In fact,it changes;
What my program shows is 24 25 |
| O(N^2) solution... | Dima_Philippov | 1416. Confidential | 20 Jul 2018 21:41 | 2 |
What is the O(N^2) solution of this problem?
I wrote simply Kraskal & DFS with assimptoty O(E * Log(E) + V * E) and got Accepted in 1.156... I want to know O(N^2) solution of this problem... My 0.093 N square solution:
1) Compute MST with Kruskal in E logE.
2) For each pair of vertices in MST compute dp[u][v] the cost of largest edge on path from u to v. This can be done by calling N depth first searches. DFS runs in O(E) and there is N - 1 edge in a MST. So this step takes (N^2) time.
3) For each edge (u, v) that isn't in a MST try to relax answer with { MST_COST - dp[u][v] + weight(u, v) }. This step is done in O(E).
So, the running time of this solution is O(ElogE + E + N^2) = O(N^2). |
| WA #11 Help me! | letranloc | 1416. Confidential | 13 Jul 2018 21:52 | 3 |
I got WA at #11. I had tested all tests on discussion and It's print right answer! Can anyone tell me some tricks? i don't know the mistake!!! What's #11??? The same to me :(
Can the author of the problem show the test case or someone give more tests, please?
Edited by author 13.07.2018 21:54 |
| WA on test 11 | So Sui Ming | 1416. Confidential | 18 Dec 2017 11:00 | 1 |
wrong post, sorry folk!
Edited by author 16.09.2024 11:07 |
| test 11st | jaxi | 1416. Confidential | 6 Aug 2015 18:38 | 5 |
i've got a wa on test 11st,could someone give me the test data?
Edited by author 26.02.2011 11:03
Edited by author 26.02.2011 11:03 I've got a wa ,too.
I need test data to find question. I got wa at 10th test.
Who can tell me the data?
Thank you !
sunzuhan@163.com 4 6
1 2 1
1 3 5
3 4 1
4 2 3
4 1 8
2 3 0
Have a try!
The right answer is 2 4
At first I forgot something and failed at #11 However, my programme shows the answer 2 4, but i failed at #11.
Who can tell me why? |
| Prim got AC,Kruskal TLE #6 | twocoldz | 1416. Confidential | 13 Nov 2013 23:01 | 1 |
RT.
I want to know what data is on test #6 |
| Test #11 Data | 1212187 | 1416. Confidential | 4 Nov 2013 16:10 | 3 |
Can someone give me data of test #11? I have test all data in discussion section and got right answer but my program just stuck in test #11.... 4 6
1 2 1
1 3 5
3 4 1
4 2 3
4 1 8
2 3 0
is this test #11? |
| Statement bug? | RybKMU | 1416. Confidential | 5 Dec 2012 10:23 | 1 |
"highly protable"? May be "highly profitable"?
And "in those aairs"? May be "in those affairs"?
Edited by author 05.12.2012 10:26 |
| wa38 | lkjslkjdlk | 1416. Confidential | 11 Aug 2012 18:25 | 1 |
wa38 lkjslkjdlk 11 Aug 2012 18:25 use sort, wa. use stable_sort, ac |
| Useful hints about ranges of M (amount of edges) | Smilodon_am [Obninsk INPE] | 1416. Confidential | 11 Mar 2012 15:36 | 1 |
Note that M (amount of edges) could be as more as N^2. Tests #12 and #15 contain perhaps M equal about 250000.
Edited by author 11.03.2012 16:06 |
| I get WA11 before . Now I AC . Here is some hint | Eazy jobb | 1416. Confidential | 8 Dec 2011 11:48 | 1 |
Helpful test data:
6 6
1 2 8
2 3 3
3 5 2
2 4 7
4 6 2
2 5 6
Ans:
Cost: 22
Cost: 25
Edited by moderator 12.11.2023 21:26 |
| Is O(N^2) the fastest solution ? | N.M.Hieu ( DHSP ) | 1416. Confidential | 25 Oct 2011 16:23 | 6 |
I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ?
Tell me, Why Kruscal+DFS doesn't work? I have TLE#12.
Should I write Prim? I think Kruskal + DFS is enough.
Maybe you need to optimize your code.
Nguyen Dinh Tu ( DHSP ), my fiend , has got AC with the complexity O(N^3)( 0.89s ) . He used Prim , too. OK, then tell me, please, how to find the second answer?
I use DFS... May be I should delete the largest vertic and
run Kruscal again? You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle. I don't know how, but my O(n^2) solution works 0.312 sec) |
| Weak tests | Zayakin Andrey[PermSU] | 1416. Confidential | 10 Jan 2011 13:28 | 2 |
Weak tests Zayakin Andrey[PermSU] 7 Aug 2010 21:59 My O(M*M*log(N)) solution passed. New tests were added. 40 authors lost AC. |
| wa #11 | Baurzhan | 1416. Confidential | 8 Aug 2010 09:10 | 5 |
wa #11 Baurzhan 12 Jun 2010 21:19 My programm passes all tests from the forum and sample tests. Please, give me some tricky tests. One more question: is there test with N=1? (it's impossible according to the statement but somebody adviced to check this case. Is it nesessary?)
Edited by author 12.06.2010 21:20 1. check your sorting algo (I used bucket sort at last)
2. don't stop at the first MST-free edge, try some more edges
This helped me. |
| TLE#12. Algo Kruscal doesn't work! Help :( | Alexey | 1416. Confidential | 31 Jul 2010 19:29 | 2 |
Please, tell me what kind of mistake can I have?
I see that there are a lot of persons
who has problems with Test#12. Is there smth speciale?
Thanks.
Edited by author 14.05.2006 15:27 I also have TLE 12 and write Kruskal and his advanced version with DSU. It doesn't meter.
But when at finding secondcost i stoped finding, if secondcost became equal to firstcost i got AC at Java with 0.2 sec with complexity o(n^3) at worst case :-)
Edited by author 31.07.2010 19:32 |
| Is something wrong with sample #1? Need answer ASAP. | tedomir | 1416. Confidential | 27 May 2010 00:10 | 2 |
4 6
1 2 2
2 3 2
3 4 2
4 1 2
1 3 1
2 4 1
Cost: 4
Cost: 4
1:
why not 1>4(cost 2, minimum. Description says if transition between A > B is possible then B > A is possible too)
That gives answer: 2
2:1>3(cost 1) then 3>4(cost 2), 1+2=3
That gives answer: 3
Anyone mind explaining why its 4 and 4 in sample? "choose the minimal possible set of trans-planet passages so that he could pass from any planet to any other one via those passages"
If you choose 1-3 and 3-4, you can't reach planet 2 from the other planets. |
| I've got WA on test 11. What's wrong? | Khlyzov Andrew | 1416. Confidential | 21 Apr 2009 21:42 | 11 |
Do we have to find two smallest mst that differ from each other by one edge? i got WA as well.can anyone tell me?i don't know the mistake The same :((
Please help me :( i have WA on test 12:) it's not the same:)) Maybe there is something wrong on your UFS(Union Find Set)... bug has been founded, thanks for replying :) may be this test will hel you
4 4
1 2 2
2 3 1
2 4 3
3 4 1
answer
Cost: 4
Cost: 6
but my WA11 program return
Cost: 4
Cost: 5
and this test
5 6
1 2 2
1 5 1
2 3 1
2 4 1
1 3 4
4 5 3
answer
Cost: 5
Cost: 6
Edited by author 21.04.2009 22:22 |
| How to solve this problem in 0.045s? | DK [Samara SAU 1: X2008] | 1416. Confidential | 4 Jun 2008 02:42 | 1 |
I've solved it only in 0.14s :( |
| WA#12 Hint | AlexF [USTU Frogs] | 1416. Confidential | 26 Aug 2007 19:19 | 1 |
I had WA#12 when I've forgotten that the wights can be 0)) |
| At last AC...Who got WA#12 can test this data: | Yitao | 1416. Confidential | 30 Jun 2007 18:39 | 2 |
6 6
1 2 8
2 3 3
3 5 2
2 4 7
4 6 2
2 5 6
The correct answer is:
Cost: 22
Cost: 25
But the program made by me which WA 12 prints:
Cost: 22
Cost: 20 I also got WA 12, but pass this test correctly...
Ops, I forget that weight of an edge can be equal to 0.
Edited by author 30.06.2007 20:00 |
