Show all threads Hide all threads Show all messages Hide all messages |
Page 2 |
WA on test 11 | So Sui Ming | 1416. Confidential | 18 Dec 2017 11:00 | 1 |
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 |
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? |
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 |
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 |
Page 1 |
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 |
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). |
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? |
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. |
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. |
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)) |
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 |
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 |
For Admins | PSV | 1416. Confidential | 4 Apr 2007 01:44 | 3 |
Firstly I've got WA13 but when I check test [ 1 0 ] - it got AC. But description says that N >= 2 - I am not misstaken? |
WA #11 | Stashuk Alex | 1416. Confidential | 31 Jan 2007 09:18 | 2 |
WA #11 Stashuk Alex 31 Jan 2007 01:59 I got WA #11. Is there any special trick for this test? Or maybe my algo is incorrect. The second minimal tree is diferrent from the first one by one edge. That's the main idea. When you solve an optimization problem first of all you must guarantee not missing any candidates to solution but don’t depend on good luck. So I think and have Ac 1416 that you must sequentially one by one cut each edge of the first tree and find first tree in residue graph. Best such tree- is answer. |
The test data #1 contains unconnected graph. | lcftc | 1416. Confidential | 16 Oct 2006 15:11 | 2 |
The test data #1 contains unconnected graph. I have tested it with my code, but in description it says that "One can reach any planet from any other planet via some chain of these passages",it means that test data can confirm it must be a connected graph. |