|
|
back to boardWhat's wrong with my algo? Finally ACed by changing to a direct approch. But I still don't understand what's wrong with my previous algo(which results to WA5) It's something like this: For example, for such a input: 4 6 1 1 2 3 3 7 4 5 2 6 6 7 4 5 8 9 12 11 10 10 8 9 12 11 1.Construct a n*m graph G, every vertices connected with all it's neighbors(up, down, left, right) (for layout reasons here I use hex to number the vertices) (the graph left is only a illustration to explain the things happening to the former graph. the graph right shows the result we get in every stage.) 1-1-2-3-3-7 o-o-o-o-o-o | | | | | | | | | | | | 4-5-2-6-6-7 o-o-o-o-o-o | | | | | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | | | | | | | | | A-A-8-9-C-B o-o-o-o-o-o 2.Remove an edge whose endpoints have the same number. Repeat this operation until no such pairs connected. finally we get something like this 1 1-2-3 3-7 o o-o-o o-o | | | | | | | | 4-5-2-6 6-7 o-o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o 3.Pick a vertex v, which has a minimum degree(non-zero), and w, an arbitrary neighbor of v. Assign a incremental number to both v and w, and remove all the edges who cover v or w. Repeat this operation until Δ(G) == 0. For the input the process will be: (STEP1) 1 1-2-3 3-7 1 o-o-o o-o | | | | | | | 4-5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o (STEP2) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4-5-8-9-C-B o-o-o-o-o-o | | | | A A-8-9-C-B o o-o-o-o-o (STEP3) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A-8-9-C-B 3 o-o-o-o-o (STEP4) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A-8-9 C B 3 o-o-o 4 4 (STEP5) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5-8-9-C-B 3 o-o-o-o-o | | A A 8 9 C B 3 o 5 5 4 4 (STEP6) 1 1-2-3 3 7 1 o-o-o 2 2 | | | | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP7) 1 1 2 3 3 7 1 7 7 o 2 2 | | 4 5-2-6 6-7 1 o-o-o o-o | | | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP8) 1 1 2 3 3 7 1 7 7 o 2 2 | | 4 5 2 6 6-7 1 8 8 o o-o | | | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP9) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6-7 1 8 8 9 o-o | | | | 4 5 8-9-C-B 3 6 o-o-o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP10) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6-7 1 8 8 9 o-o | | | | 4 5 8 9 C-B 3 6 A A o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP11) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6 7 1 8 8 9 B B
4 5 8 9 C-B 3 6 A A o-o
A A 8 9 C B 3 6 5 5 4 4 (STEP12) 1 1 2 3 3 7 1 7 7 9 2 2
4 5 2 6 6 7 1 8 8 9 B B
4 5 8 9 C B 3 6 A A C C
A A 8 9 C B 3 6 5 5 4 4 4.Finally we got a valid output: 1 7 7 9 2 2 1 8 8 9 B B 3 6 A A C C 3 6 5 5 4 4 I know I must mistaked something, but I can't find the mistake. Please tell me where is wrong, or give me some tests to beat this algo. Thanks in advance. Edited by author 31.05.2009 00:28 Sorry I'm sorry the layout turned out to be totally unreadable. Please copy the text to the notepad for viewing the graph edges. Re: What's wrong with my algo? It was a very good question. What's wrong with the algo? "3. Pick a vertex v, which has a minimum degree (non-zero)..." If there are several (not one) such vertices, we must do a choice. Let choose the vertix (with a minimum degree) that is placed in the least row. If the row has several vertices with a minimum degree, let choose the vertix that is placed in the least column. The next choice is the choice of w (see the algo). Let choose right neighbor of v if v is connected with it. Otherwise let choose bottom neighbor of v as w. So we have input data that breaks the algo: 6 6 1 1 2 2 3 4 5 5 6 7 3 4 8 9 6 7 10 11 8 9 12 12 10 11 13 14 15 15 16 17 13 14 18 18 16 17 STEP 12 1 9 9 3 2 2 1 10 10 3 11 11 4 4 o - o 12 12 | | o - o - o o - o - o | | | | o - o 6 8 o - o 5 5 6 8 7 7 STEP 13 (it is not good) 1 9 9 3 2 2 1 10 10 3 11 11 4 4 13 13 12 12
o - o - o o - o - o | | | | o - o 6 8 o - o 5 5 6 8 7 7 I'm sure we can build input data that makes the algo invalid if we would choose the v and w in other way. Edited by author 23.10.2017 22:15 |
|
|