| ENG RUS | Timus Online Judge |
Discussion of Problem 1416. ConfidentialKollekcioner[Vologda, VML1] Some test [7] // Problem 1416. Confidential 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 Denis Koshman Re: Some test [3] // Problem 1416. Confidential 3 Aug 2008 19:27 AC answer: Cost: 24 Cost: 25 Sunzuhan Re: Some test // Problem 1416. Confidential 4 Apr 2011 20:37 What? The right answer should be Cost: 24 Cost: -1 Reply to the upper Edited by author 04.04.2011 20:38 Giorgi Shavgulidze [Tbilisi SU] Re: Some test [1] // Problem 1416. Confidential 9 Apr 2011 02:44 I think answer should be 24 24, as my program does. We can replace 3->8 with 3->6 and it changes nothing. index Re: Some test // Problem 1416. Confidential 8 May 2011 12:48 In fact,it changes; What my program shows is 24 25 wzkDTerH Re: Some test [2] // Problem 1416. Confidential 2 Jul 2011 08:42 Thanks answer is 24，25. wzkDTerH Re: Some test // Problem 1416. Confidential 2 Jul 2011 08:46 Thank you very much!! Ritesh Rastogi Re: Some test // Problem 1416. Confidential 25 Apr 2020 06:26 Thanks a ton ! Dima_Philippov O(N^2) solution... [1] // Problem 1416. Confidential 2 Dec 2011 02:23 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... die_young Re: O(N^2) solution... // Problem 1416. Confidential 20 Jul 2018 21:41 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). letranloc WA #11 Help me! [2] // Problem 1416. Confidential 26 Oct 2013 19:31 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??? 1212509 Re: WA #11 Help me! [1] // Problem 1416. Confidential 27 Oct 2013 22:36 Dude, the same to me :(( joaopfg Re: WA #11 Help me! // Problem 1416. Confidential 13 Jul 2018 21:52 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 So Sui Ming WA on test 11 // Problem 1416. Confidential 18 Dec 2017 11:00 My codes passed all testcases mentioned in the forum using stable sort or sort in c++ but still got WA on test 11. Any idea? Edited by author 18.12.2017 11:01 Edited by author 18.12.2017 11:01 jaxi test 11st [4] // Problem 1416. Confidential 26 Feb 2011 11:03 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 pbj Re: test 11st [1] // Problem 1416. Confidential 27 Feb 2011 14:39 I've got a wa ,too. I need test data to find question. Sunzuhan Re: test 11st // Problem 1416. Confidential 4 Apr 2011 20:33 I got wa at 10th test. Who can tell me the data? Thank you ! sunzuhan@163.com index Re: test 11st [1] // Problem 1416. Confidential 8 May 2011 12:53 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 llaa Re: test 11st // Problem 1416. Confidential 6 Aug 2015 18:38 However, my programme shows the answer 2 4, but i failed at #11. Who can tell me why? twocoldz Prim got AC,Kruskal TLE #6 // Problem 1416. Confidential 13 Nov 2013 23:01 RT. I want to know what data is on test #6 1212187 Test #11 Data [2] // Problem 1416. Confidential 30 Oct 2013 23:08 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.... 1212264 Re: Test #11 Data [1] // Problem 1416. Confidential 31 Oct 2013 11:56 4 6 1 2 1 1 3 5 3 4 1 4 2 3 4 1 8 2 3 0 is this test #11? 1212187 Re: Test #11 Data // Problem 1416. Confidential 4 Nov 2013 16:10 Thanks RybKMU Statement bug? // Problem 1416. Confidential 5 Dec 2012 10:23 "highly protable"? May be "highly profitable"? And "in those aairs"? May be "in those affairs"? Edited by author 05.12.2012 10:26 lkjslkjdlk wa38 // Problem 1416. Confidential 11 Aug 2012 18:25 use sort, wa. use stable_sort, ac Smilodon_am [Obninsk INPE] Useful hints about ranges of M (amount of edges) // Problem 1416. Confidential 11 Mar 2012 15:36 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 Eazy jobb I get WA11 before . Now I AC . Here is some hint // Problem 1416. Confidential 8 Dec 2011 11:48 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 N.M.Hieu ( DHSP ) Is O(N^2) the fastest solution ? [5] // Problem 1416. Confidential 14 May 2006 20:21 I think O(N^2) ( Prim + DFS )is the fastest way to solve this problem , is it right ? Alexey Re: Is O(N^2) the fastest solution ? [4] // Problem 1416. Confidential 14 May 2006 20:30 Tell me, Why Kruscal+DFS doesn't work? I have TLE#12. Should I write Prim? N.M.Hieu ( DHSP ) Re: Is O(N^2) the fastest solution ? [3] // Problem 1416. Confidential 14 May 2006 22:20 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. Alexey Re: Is O(N^2) the fastest solution ? [2] // Problem 1416. Confidential 15 May 2006 18:14 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? Ludovic Re: Is O(N^2) the fastest solution ? [1] // Problem 1416. Confidential 9 Sep 2006 07:51 You may try adding each non-MST edge to the MST and delete the longest MST edge in the cycle. -XraY- Re: Is O(N^2) the fastest solution ? // Problem 1416. Confidential 25 Oct 2011 16:23 I don't know how, but my O(n^2) solution works 0.312 sec) Zayakin Andrey[PermSU] Weak tests [1] // Problem 1416. Confidential 7 Aug 2010 21:59 My O(M*M*log(N)) solution passed. Sandro (USU) Re: Weak tests // Problem 1416. Confidential 10 Jan 2011 13:28 New tests were added. 40 authors lost AC. Baurzhan wa #11 [4] // Problem 1416. Confidential 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 Baurzhan Re: wa #11 [3] // Problem 1416. Confidential 16 Jun 2010 20:46 up Baurzhan Re: wa #11 [2] // Problem 1416. Confidential 1 Jul 2010 22:41 up Baurzhan Re: wa #11 [1] // Problem 1416. Confidential 31 Jul 2010 19:18 up. KALO Re: wa #11 // Problem 1416. Confidential 8 Aug 2010 09:10 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. Alexey TLE#12. Algo Kruscal doesn't work! Help :( [1] // Problem 1416. Confidential 13 May 2006 17:29 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 Oleg Strekalovsky [Vologda SPU] Re: TLE#12. Algo Kruscal doesn't work! Help :( // Problem 1416. Confidential 31 Jul 2010 19:29 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 tedomir Is something wrong with sample #1? Need answer ASAP. [1] // Problem 1416. Confidential 26 May 2010 22:17 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? Sandro (USU) Re: Is something wrong with sample #1? Need answer ASAP. // Problem 1416. Confidential 27 May 2010 00:10 "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. Khlyzov Andrew I've got WA on test 11. What's wrong? [10] // Problem 1416. Confidential 30 Oct 2005 19:40 Do we have to find two smallest mst that differ from each other by one edge? Lan Jun Re: I've got WA on test 11. What's wrong? // Problem 1416. Confidential 2 Nov 2005 18:39 i got WA as well.can anyone tell me?i don't know the mistake boaz Re: I've got WA on test 11. What's wrong? // Problem 1416. Confidential 24 Mar 2006 11:02 the same mistake.. lamot Re: I've got WA on test 11. What's wrong? [2] // Problem 1416. Confidential 13 May 2006 14:03 the same :( N.M.Hieu ( DHSP ) Re: I've got WA on test 11. What's wrong? [1] // Problem 1416. Confidential 14 May 2006 14:04 The same :(( Please help me :( marius dumitran Re: I've got WA on test 11. What's wrong? // Problem 1416. Confidential 7 Aug 2006 04:29 i have WA on test 12:) it's not the same:)) LittlePig Re: I've got WA on test 11. What's wrong? // Problem 1416. Confidential 25 Sep 2007 12:52 The same.. WA11 bonism Re: I've got WA on test 11. What's wrong? [3] // Problem 1416. Confidential 7 Feb 2009 17:23 Maybe there is something wrong on your UFS(Union Find Set)... AlMag(VNTU) Re: I've got WA on test 11. What's wrong? [2] // Problem 1416. Confidential 27 Mar 2009 02:40 i need a hint, wa#11 :( AlMag(VNTU) Re: I've got WA on test 11. What's wrong? [1] // Problem 1416. Confidential 27 Mar 2009 17:43 bug has been founded, thanks for replying :) RASTA Re: I've got WA on test 11. What's wrong? // Problem 1416. Confidential 21 Apr 2009 21:42 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 DK [Samara SAU 1: X2008] How to solve this problem in 0.045s? // Problem 1416. Confidential 4 Jun 2008 02:42 I've solved it only in 0.14s :( AlexF [USTU Frogs] WA#12 Hint // Problem 1416. Confidential 26 Aug 2007 19:19 I had WA#12 when I've forgotten that the wights can be 0)) Yitao At last AC...Who got WA#12 can test this data: [1] // Problem 1416. Confidential 22 Jun 2007 15:23 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 Lomir Re: At last AC...Who got WA#12 can test this data: // Problem 1416. Confidential 30 Jun 2007 18:39 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
|