ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1229. Strong Brickwork

What's wrong with my algo?
Posted by Akaishuichi 31 May 2009 00:24
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
Posted by Akaishuichi 31 May 2009 00:32
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?
Posted by Dmitri Belous 23 Oct 2017 22:08
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