| ENG RUS | Timus Online Judge |
Discussion of Problem 1709. Penguin-Aviacoolboy19521 Hint // Problem 1709. Penguin-Avia 7 Aug 2024 15:25 Use long type (anything 64 bit) MST D4nick Universal test for any WA, including WA6 [1] // Problem 1709. Penguin-Avia 12 May 2023 13:49 Input: 9 16372 24788 000010111 001111101 010010001 010011001 111100101 010100100 110011000 100000000 111110000 Possible answer (a's should be the same, d's can differ in you answer): 163720 000000000 000000d0d 0000d000d 0000dd00d 00dd00d0d 000d00d00 0d00dd000 000000000 0dddd0000 Matrix for the graph in the answer: 000010111 001111000 010000000 010000000 110000000 010000000 100000000 100000000 100000000 Edited by author 12.05.2023 13:49 D4nick Re: Universal test for any WA, including WA6 // Problem 1709. Penguin-Avia 12 May 2023 13:54 Use this site to visualise the graph using matrix and firstly change enumeration from 1,2,3... to 0,1,2... : https://graphonline.ru/# Edited by author 12.05.2023 13:55 Edited by author 12.05.2023 13:55 D4nick Possible mistakes causing WA6 and others // Problem 1709. Penguin-Avia 12 May 2023 13:53 If you have a mistake, most likely you delete connections of the input graph in a wrong way. And most likely, because you search the connected components incorrectly. 👾_challenger128_[PermSU] If you have WA5 (C++) // Problem 1709. Penguin-Avia 22 Feb 2021 01:27 write line "#define int long long" and change "int main" to "signed main" Nurs Подсказка // Problem 1709. Penguin-Avia 19 Jan 2021 14:54 Подумайте о типе графа, дерево Ildar Valiev WA 5 [15] // Problem 1709. Penguin-Avia 4 Apr 2009 15:24 Can anybody give some test to judge my prog? I have WA on 5 test and cann't find my mistake. Atik Re: WA 5 [5] // Problem 1709. Penguin-Avia 4 Apr 2009 17:11 Ohhh! So stupid mistake)) simonchen Re: WA 5 [4] // Problem 1709. Penguin-Avia 4 Apr 2009 17:13 Atik wrote 4 April 2009 17:11 Ohhh! So stupid mistake)) what?Kolobov_Oleg Re: WA 5 [3] // Problem 1709. Penguin-Avia 4 Apr 2009 18:51 I also have WA5(( Igor9669 Re: WA 5 [2] // Problem 1709. Penguin-Avia 4 Apr 2009 18:53 What is your algo? simonchen Re: WA 5 [1] // Problem 1709. Penguin-Avia 4 Apr 2009 19:50 I use dfs and add edge between two pieces. I should use int64....... Edited by author 05.04.2009 07:22 Igor9669 Re: WA 5 // Problem 1709. Penguin-Avia 4 Apr 2009 20:14 When do you add edge between two pieces? melkiy hint for WA5 [7] // Problem 1709. Penguin-Avia 4 Apr 2009 21:11 This is a "boundary values" test. Consider a case when you have initially a full graph of ones - you have ~100^2 = 10^4 flights, and d=10^6. How much have you pay then to optimize the flights scheme? Martin_fmi Re: hint for WA5 // Problem 1709. Penguin-Avia 4 Apr 2009 21:38 Thx melkiy. cylixstar Re: hint for WA5 [5] // Problem 1709. Penguin-Avia 4 Apr 2009 21:38 FT~~~~ I didn't know that long long is not supported. clocy Re: hint for WA5 [2] // Problem 1709. Penguin-Avia 5 Apr 2009 08:55 OH!!!!FT.. Realy, It's the problem ~ I didn't know that long long is not supported ,either ~ maybe the judge should update its compiler? Al.Cash Re: hint for WA5 [1] // Problem 1709. Penguin-Avia 5 Apr 2009 14:22 Of course long long is supported!! You should read FAQ before asserting such things! http://acm.timus.ru/help.aspx?topic=cpp&locale=en cylixstar Re: hint for WA5 // Problem 1709. Penguin-Avia 5 Apr 2009 15:00 Oh,I See.So we can only use "%I64d" to input/output?for I got WA while using "%lld" but AC with "%I64d" melkiy Re: hint for WA5 [1] // Problem 1709. Penguin-Avia 5 Apr 2009 23:28 I know abbreviations AC, WA, TLE, DFS, BFS, DP... But what does FT stand for??? Yitao Re: hint for WA5 // Problem 1709. Penguin-Avia 11 Jun 2009 14:04 It means "Faint". Валентин Дядька Re: WA 5 // Problem 1709. Penguin-Avia 19 Mar 2018 04:11 May be use long long xurshid_n WA6 [8] // Problem 1709. Penguin-Avia 4 Apr 2009 16:30 Please, give me some hint! svr Re: WA6 // Problem 1709. Penguin-Avia 21 Apr 2009 11:51 Standard Prim's(Greedy) algo works if we assign -d to edges in graph. ilucian1 Re: WA6 [4] // Problem 1709. Penguin-Avia 30 Jun 2009 14:47 nothing special, just obtain a spanning tree (forest)... I think you made a confusion between verteces and parents, or something like that... try this example: 7 2 10 0000101 0000101 0001010 0010010 1100001 0011000 1100100 One of the correct answers is 16 00a000d 0000000 a0000d0 0000000 000000d 00d0000 d000d00 FatalityNT Re: WA6 [2] // Problem 1709. Penguin-Avia 23 Oct 2013 13:55 Thanks you. This test helped me to find the reason of WA6. Jane Soboleva (SumNU) Re: WA6 [1] // Problem 1709. Penguin-Avia 22 Feb 2016 06:26 Had a very silly WA6, and none of tests from this or neighbouring topics helped, so here's the one that i finally thought of and which helped: 5 1 1 01000 10001 00010 00101 01010 (1-2, 2-5, 5-4, 4-3, result is all zeros.) I've been sleepy and lazy and did a bad job with a tree building algo, which i made like this: --- (mark vertices 1..N as unconnected) for i:=1 to N do for j:=1 to N do if (i, j) is an existing edge and either i or j is yet unconnected to anything, then add (i, j) to a tree and mark both i and j as connected. --- So then it adds 1-2, then 2-5, then 3-4, and then it appears that both 4 and 5 are already connected to something, and 4-5 isn't included to a tree, which is a mistake. LLL Re: WA6 // Problem 1709. Penguin-Avia 2 Oct 2016 11:07 helpful!thx Mescheryakov_Kirill [SESC17] Re: WA6 // Problem 1709. Penguin-Avia 31 Aug 2016 12:56 My programm have wa6? and on your test give: 16 0000000 000000d 000000a 00000d0 000000d 000d000 0da0d00 Is it correct? Muad Dib WA6 too // Problem 1709. Penguin-Avia 6 Jul 2009 13:56 I've WA6 too. But on pervious test I've got AC. I use connected components of graph and Kruskal algo for builting spanning tree. Samsonov Alex [USU] Re: WA6 // Problem 1709. Penguin-Avia 6 Jul 2009 20:38 Try to estimate the maximal possible answer to this problem. Frankey Hint [3] // Problem 1709. Penguin-Avia 26 Jul 2009 21:25 This is very easy problem. You can use: 1) BFS or DFS to find the components of the graph; 2) Prim or Kruskal algo for minimum spanning tree. SkorKNURE Re: Hint // Problem 1709. Penguin-Avia 26 Oct 2010 16:28 spanning tree can be built during BFS. It's correct because graph is unweighted. Artem Khizha [DNU] Re: Hint [1] // Problem 1709. Penguin-Avia 16 Jul 2011 17:22 Well, I see, that this is MST problem, but cannot get how to build a graph for it. Please, explain your step 1 more precisely. Sehriyar Novruzov Re: Hint // Problem 1709. Penguin-Avia 28 Jul 2015 17:56 Sure, it can be solved applying BFS or DFS + Minimum Spanning Tree algorithms (Prim Algorithm). But, BFS or DFS is enough to solve it. BFS or DFS is implemented to identify Connected Component and Non-Connected Component. No need to apply MST to remove redundant edges in each Connected Component. Because, while BFS or DFS you can built identify which edges you need and don't need. Here is one part of my code to do BFS and work like Prim algo [code deleted] Edited by moderator 19.10.2019 20:33 Husan WA4 [3] // Problem 1709. Penguin-Avia 5 Oct 2009 04:55 Please give me some tests Oleg Strekalovsky aka OSt [Vologda SPU] Re: WA4 [2] // Problem 1709. Penguin-Avia 16 Oct 2009 21:26 I don't use any graphs algorithms,but only DFS. If you try to solve this problem like me do: 1) break(remove) all cycles 2)Store elements of graph,witch belong to different component's of graph. 3) Connect one of them with others. (one - to every). Not every to every!!! Test 6 1000000 1000000 010000 100000 000100 001000 000001 000010 Edited by author 16.10.2009 21:29 Hikmat Ahmedov I have WA5 // Problem 1709. Penguin-Avia 31 Jan 2012 21:03 Is this one of the solutions to the above given test? 2000000 00a0a0 000000 a00000 000000 a00000 000000 amomorning Re: WA4 // Problem 1709. Penguin-Avia 4 Jun 2015 11:31 thx kostya1996 LONG LONG!!!!!!!!!!!!!!!! // Problem 1709. Penguin-Avia 15 Oct 2014 11:07 hyesun wa #1 [1] // Problem 1709. Penguin-Avia 22 Apr 2014 13:21 I am wondering why i got wa on test #1. I use dfs to color the edges. when one edge is not colored it means it makes a cycle and thus should be deleted. Next, every time I make dfs with a vertex, I connect it to a vertex processed before, which means the current vertex is connected to a component marked before. Lastly I used long long to store the result. But I just got wa on test #1. Can anybody please tell me sth about test #1 ? Lots of thanks hyesun Re: wa #1 // Problem 1709. Penguin-Avia 22 Apr 2014 16:25 Oh damn it. My first version of code is: int d, a, countd, counta; ...... long long money = d * countd + a * counta; But I didn't realize that d * countd may have already overflowed. So my AC version is: long long d, a, countd, count; ...... long long money = .....; Thus if anyone got WA at test #1 and you are sure you have the right algo, you may have failed due to the same reason as mine. Andrew Sboev How to make graph connected fast? [1] // Problem 1709. Penguin-Avia 3 Jun 2012 21:28 My method of making graph connected works nearly by O(N^2). Are there any classic algorithmes for such problem? yutr777 Re: How to make graph connected fast? // Problem 1709. Penguin-Avia 27 Dec 2013 10:51 You should use the system of disjoint sets. yutr777 Why it's wrong or how to solve this problem??? // Problem 1709. Penguin-Avia 27 Dec 2013 10:50 I have submit my solution, where I have used the system of disjoint sets. But it has WA 1 :)) What is another way to solve this problem??? hell_boy7725 what is the test 13 // Problem 1709. Penguin-Avia 15 Apr 2013 23:22 wrong answer in test 13, help me! Edited by author 15.04.2013 23:26 Karpov Alexandr [AC] [1] // Problem 1709. Penguin-Avia 9 Jan 2013 17:57 I had a stupid bug and found better to post it here rather than trying to look on my code. Looked, found. Edited by author 09.01.2013 18:03 To Anh Tuyen Re: [AC] // Problem 1709. Penguin-Avia 13 Apr 2013 08:46 Nguyen Doan Quoc Phong What is Test #2 ?? [1] // Problem 1709. Penguin-Avia 11 Apr 2013 12:13 Pls, anyone give me some hint about test #2 ! Thanks ThieuQuang Re: What is Test #2 ?? // Problem 1709. Penguin-Avia 11 Apr 2013 23:01 [TH2011/1]1112396 What is the test 5?? [4] // Problem 1709. Penguin-Avia 15 Nov 2012 16:14 I have a problem with test5!.Wrong anwser!!! Can anyone help me?. What is the test 5? [TH2011/1]1112396 Re: What is the test 5?? [3] // Problem 1709. Penguin-Avia 15 Nov 2012 17:12 I have solved this problem!!!. I am stupid!. [TH2011/01]1112384 Re: What is the test 5?? [2] // Problem 1709. Penguin-Avia 16 Nov 2012 12:37 [TH2011/1]1112396 wrote 15 November 2012 17:12 I have solved this problem!!!. I am stupid!. minimal amount of money necessary for the optimization of the existing flight scheme is long long type.Edited by author 16.11.2012 12:38 [TH0111]1112400 Re: What is the test 5?? // Problem 1709. Penguin-Avia 16 Nov 2012 13:15 The project is not very difficult. The test is so easy. ^^ ROHAN GULATI Re: What is the test 5?? // Problem 1709. Penguin-Avia 29 Mar 2013 19:34 Thanks for the help...i spent a day debug my code :) Barsuk Alexey [Pskov] useful for wa#6 [1] // Problem 1709. Penguin-Avia 8 Oct 2010 01:36 If you use dfs, try this test 5 1 3 01000 10111 01000 01000 01000 Answer is: 0 00000 00000 00000 00000 00000 inatial_D Re: useful for wa#6 // Problem 1709. Penguin-Avia 9 Feb 2013 18:53 It is rather useful. Thanks. ZLqiang So stupid error。。。。 // Problem 1709. Penguin-Avia 23 Jul 2011 07:50 The program should use long long or __int64 type。。。。 Hrayr Hi all,I have just accepted this problem ,my time is 1s,i know why,because my Prime(MST) algo is very slow ,who can give me Prime algo (c++). [1] // Problem 1709. Penguin-Avia 7 Jul 2011 20:40 Hrayr Re: Hi all,I have just accepted this problem ,my time is 1s,i know why,because my Prime(MST) algo is very slow ,who can give me Prime algo (c++). // Problem 1709. Penguin-Avia 8 Jul 2011 23:17 Need Prime algo in c++.
|