| Show all threads Hide all threads Show all messages Hide all messages |
| Universal test for any WA, including WA6 | D4nick | 1709. Penguin-Avia | 12 May 2023 13:54 | 2 |
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 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 |
| Possible mistakes causing WA6 and others | D4nick | 1709. Penguin-Avia | 12 May 2023 13:53 | 1 |
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. |
| If you have WA5 (C++) | 👾_challenger128_[PermSU] | 1709. Penguin-Avia | 22 Feb 2021 01:27 | 1 |
write line "#define int long long" and change "int main" to "signed main" |
| Подсказка | Nurs | 1709. Penguin-Avia | 19 Jan 2021 14:54 | 1 |
Подумайте о типе графа, дерево |
| WA 5 | Ildar Valiev | 1709. Penguin-Avia | 19 Mar 2018 04:11 | 16 |
WA 5 Ildar Valiev 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. Ohhh! So stupid mistake)) Ohhh! So stupid mistake)) what? I use dfs and add edge between two pieces.
I should use int64.......
Edited by author 05.04.2009 07:22 When do you add edge between two pieces? 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? FT~~~~
I didn't know that long long is not supported. 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? Oh,I See.So we can only use "%I64d" to input/output?for I got WA while using "%lld" but AC with "%I64d" I know abbreviations AC, WA, TLE, DFS, BFS, DP... But what does FT stand for??? Re: WA 5 Валентин Дядька 19 Mar 2018 04:11 |
| WA6 | xurshid_n | 1709. Penguin-Avia | 2 Oct 2016 11:07 | 9 |
WA6 xurshid_n 4 Apr 2009 16:30 Please, give me some hint! Standard Prim's(Greedy) algo works if we assign -d to edges
in graph. 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 Re: WA6 FatalityNT 23 Oct 2013 13:55 Thanks you. This test helped me to find the reason of WA6. Re: WA6 Jane Soboleva (SumNU) 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. Re: WA6 Mescheryakov_Kirill [SESC17] 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? 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. Re: WA6 Samsonov Alex [USU] 6 Jul 2009 20:38 Try to estimate the maximal possible answer to this problem. |
| Hint | Frankey | 1709. Penguin-Avia | 28 Jul 2015 17:56 | 4 |
Hint Frankey 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.
spanning tree can be built during BFS. It's correct because graph is unweighted. Re: Hint Artem Khizha [DNU] 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. Re: Hint Sehriyar Novruzov 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 |
| WA4 | Husan | 1709. Penguin-Avia | 4 Jun 2015 11:31 | 4 |
WA4 Husan 5 Oct 2009 04:55 Please give me some tests Re: WA4 Oleg Strekalovsky aka OSt [Vologda SPU] 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 Is this one of the solutions to the above given test?
2000000
00a0a0
000000
a00000
000000
a00000
000000 Re: WA4 amomorning 4 Jun 2015 11:31 |
| LONG LONG!!!!!!!!!!!!!!!! | kostya1996 | 1709. Penguin-Avia | 15 Oct 2014 11:07 | 1 |
|
| wa #1 | hyesun | 1709. Penguin-Avia | 22 Apr 2014 16:25 | 2 |
wa #1 hyesun 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 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. |
| How to make graph connected fast? | Andrew Sboev | 1709. Penguin-Avia | 27 Dec 2013 10:51 | 2 |
My method of making graph connected works nearly by O(N^2). Are there any classic algorithmes for such problem? You should use the system of disjoint sets. |
| Why it's wrong or how to solve this problem??? | yutr777 | 1709. Penguin-Avia | 27 Dec 2013 10:50 | 1 |
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??? |
| what is the test 13 | hell_boy7725 | 1709. Penguin-Avia | 15 Apr 2013 23:22 | 1 |
wrong answer in test 13, help me!
Edited by author 15.04.2013 23:26 |
| [AC] | Karpov Alexandr | 1709. Penguin-Avia | 13 Apr 2013 08:46 | 2 |
[AC] Karpov Alexandr 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 |
| What is Test #2 ?? | Nguyen Doan Quoc Phong | 1709. Penguin-Avia | 11 Apr 2013 23:01 | 2 |
Pls, anyone give me some hint about test #2 ! Thanks |
| What is the test 5?? | [TH2011/1]1112396 | 1709. Penguin-Avia | 29 Mar 2013 19:34 | 5 |
I have a problem with test5!.Wrong anwser!!!
Can anyone help me?. What is the test 5? I have solved this problem!!!. I am stupid!. 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:38The project is not very difficult. The test is so easy. ^^ Thanks for the help...i spent a day debug my code :) |
| useful for wa#6 | Barsuk Alexey [Pskov] | 1709. Penguin-Avia | 9 Feb 2013 18:53 | 2 |
If you use dfs, try this test
5
1 3
01000
10111
01000
01000
01000
Answer is:
0
00000
00000
00000
00000
00000 It is rather useful. Thanks. |
| So stupid error。。。。 | ZLqiang | 1709. Penguin-Avia | 23 Jul 2011 07:50 | 1 |
The program should use long long or __int64 type。。。。 |
| 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++). | Hrayr | 1709. Penguin-Avia | 8 Jul 2011 23:17 | 2 |
|
| Hint | Frankey | 1709. Penguin-Avia | 26 Jul 2009 21:26 | 1 |
Hint Frankey 26 Jul 2009 21:26 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.
|
