10615 - Rooks

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

10615 - Rooks

Post by Miguel Angel » Wed Jan 28, 2004 12:51 am

I do the following..
Take the trasversal with max number of * and took it away, until no rooks are found...why is this wrong?
:D Miguel & Marina :D

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jan 28, 2004 1:05 am

I don't understand exactly your algorithm. For me it sounds like some greedy algorithm. But greedy doesn't work for this problem.
For example try this test case:
100
.****.**.**.*****.************.*****.**.*********....***.*****.*********.***.*****.********...******
***.*****.*.*****.*********************.****.*.***.*.*****.*.*******...**.*****.*.***.***..*********
.**.**.******.**.*********************...**..***.*****.********.*...**.********.***************.**.*
**..**.***..**.***********************...***.*******..**..*******.*.*****.**.********.************.*
.***..******.*************..******************.*********.**..*..*.*******.*.*************..******...
*.***********.*.************************.*.*.*.*.*..****.**..*******...*.**..*************.*********
***********.**.*.*********************.****...******.****..*.***.*****..*.***.*********.*..****.****
.*.*****.*.**.**************************.**..***..*.**..***.****...************.**************..****
*.**..***.**********************************..*.*.*.***.*.*****.****.***.*******.*.*****.******.*..*
*.***.*************************..**********.*********...****...**.*..*********.*****..**.********.*.
**.******.***.**************..*****..******************.*..*.**.*..*******...*.*..******************
********.*.****************..*..**.*.********.*****************.***..*.*.******.*.**.*********.**..*
*.**********************************************...*****.*****..**.****.*......*...******.****.*****
*.*.****.**********.****.***...**.**.***********************.***.***.**...*************.*..********.
***..*.*************************************.****.*....*.**.*...*****.*****.*.*.*****.***.**********
****.******..*****************************************.*****...*...*.******.*.*.****.*.*...****.****
*.***************************************..*..*******..**.****.**..***.*.*.**..**.***..************.
**.*************************************.*..*********.***.*.*****.*.*...*..******.*..**.**.****.****
*******************.***.*...***.********..**********.**************..**...*****..***..*.**********.*
*.*********************************************..*.*.**.*.***.*..***...****.*.****..********.**.**.*
********************.*********..***.*.*.*******.*.*...***.*..**.**.**************.****.***.****.****
****************.***************************...****.*.*.*.****..*..*****...**.*.*****.***.***.******
*********.*************************************************.*******.**..**.**...*......***.*..*.*.**
***************************************..*.********.**..*******.**..*.**.**********.**...*.**..*..**
*********************************************.*.*.***..*..*.**.***.*..**.*.*..**********.***.**.*.**
*********.*******************************************.*.*..**.**.**..*..*.*.**..***.**..**.*******.*
***.********.******************************.**********...**.*.********..**.*..***.**.*.***..***..***
*********.***************.***..*..*.***..*.*.****.******.********.*****..*.***.**.*******.**********
********************.***********************..*..**********.****.****.*.*..**...*****.*..***.**..***
*********.**********.**.***.*..*.**.*********.******..***.****.**.********.**.*****..******.****.***
***.******************************************.**.*.**....***...******.*.*****..********.*****..*.*.
*************************.***********************.***..*.****.*......**.***.******.****..****..*.***
*******************************************.****.*****..***.**.**....*.*.*..*.***.**.**.***.**.*****
***.*.************.***************************..**.****.*..*****.****.**..*.*********.**..*.****.**.
****..**************.*************************.**************************..**.*.....*.**.**...**..*.
*******************************************.*****..*...*..***..***.******.***.*.**..*.**.*..********
***..*************.*.*****************.**********************..*.***.*.*..*******.*.*.*..******...**
***..*********************************.*************....**..**.****...**..*****.******..****.*****.*
.**..**.************.***************************************...**...**.****..*****..*.*********..**.
**********.***********.***********.***.***********.*****..*.**.*.***..********.**.****.*.**.*.***.*.
.*********.*******.***.******************..*****.******.**.***..***.******...**********.***.**.*..**
*****.*****.**********.*.*************.******.***.****.*.**..*..**********.*.*****..***..*.*********
*****.***********.**.*.*.*************.*************************.*.****..*.**..*.*..**.*****..*****.
.***.*.**********.**.*****.*********.***********************.***.**.****.**.**..***..**.*.****.****.
***.**.**.**.********.**.*********.********************.*.*****.*.*.*...**.********.*.******.***.***
**.*.*******.******...****.**************************.*.**.*.**************.*.*.*.**.****.*.*.***.**
**.************.****.***.*********************.*.****.*.....******..*******..*.*****.**.*****.******
.*.**..**.***.*.*..*.*.*****.**************************************************...*..******.******..
.******.***.***...*.*.**.***.*********.*******************************************.***....*..*****..
..*****..**.**********..**************.***************************************..**..**.*..**.*.*.*..
******.*.*...**.**.***..**********.*.**********.**************..*.*********..*********.*******.*.***
****....*****.***.****...*********.************.**.**.**************.****..*****.*******.******..***
.***.***.*..**..*.*****..*.***.*******.*******.**********************************..********..*.***.*
********.*.**.*****.*.*.**.***.***.*..***********************************...*.*******.**.***.**.**.*
**...*****...******.***.**.****.**.******************************.***.**.**.**.*..****.******.******
**..***.**.*.******.*.******.*****.***********.***********************.***.*********.*.**.***..*.*..
****..****.*.****.***.*******.****.************.******...*************.*.*****.****..**.**.*.*******
..****.**.*.**..*.****.***.**.**..***********.***************************************..****...**.***
.******..**.**.**********.*.********..***.*****.***************************..****.*.*.****.****...**
.****.*.******.**...*****.*....**..***.***.****.********************************************...*****
.**.**..***.*...************.****.***.**********************.*******************.***.*.**.*.*..*.***
.*.********.*.**.**..*.*******.**.*.*..********.*************.***.*************..************..*****
*.*.***..*..*.*******..*****.*******.*********.***.********************.****.***.**.******.*****..**
**.*.*.*.*****.*.**.**.***.****.****..****.**.************.*********************.*.***.**********.*.
**.***..**.**.**...******...***.*.****.**.****************.**************************.**.**.******.*
*.*...**.*.**..***.*.**...*.**..*********..**.************.*****************************************
*********.*...******.*.*.******.**..*****..****.**********************************.*.*...***..******
*.*************..*.**.*..******.*....***.*********.*****.************************..*********...*****
********.***..*....****.*.*.......*..***.*****.*****************************************************
.*.***.***.***.*.**.*.****.**.*******.***..****.**********.*************************.**.*****.***..*
*.***********.*..************..*.*****.*.*..***.*****************************..****....***.********.
*.*.**..****.***.**.*.*****.***.*****.*.**********.*******.*.****************.******.******.*****.*.
...*..***.**********.***.**..**..***...*.*****.***.******************************************.**.***
*..***..*.*****.******.******.*..*.******...**.*.*********.******************************.*******..*
***************.**...**..****.**.....**...*.**.*.*********.*****************.***********************
**.*...******.*******.****.*.**.*.*****.*.******.************.*************************.**...*.**.**
****.*.*****.***..**..***.***.***.***.****..*.*.********.*.*.********.******.***********************
********.*...*..***.******.**.****..**.**.***..*.*...****************.******************************
*******.****..**.*..*..*....****.*.********.******.*******.*.********.******.***********************
*******.******...**.*...*.*.*.***..*.*****..*.***.***********.*******.******************************
*.***.*.*..*******.******.*..******...*****.****.*..************************.************.*..*******
********.***..*****.*...**.****.***..**.*..*****.**.****.****.*********.***********************.****
.*****.....***..***...***.****.**.*.**..*******.***..***********************************************
**.**.*...***.*******.*..***.*.*.*********.**.***.*..*******..*************************************.
**************.*.*.*.*.**...*.**..***.*..*.**.****.*.***********.******.****************************
*.***.*.***.*..**..****.*..*.***..***.*.***.****.**.***************************************.********
*..****.***..*..********..*.****..*.***...****.*****.***********.***************.*******************
********************.*..*.***.****..**..*.*.*.**...**********.**.***********.***.**************.****
******.**.*****.*..****.*.**.*.*.*.********..******.*.*.**********.*************.*****************..
.**.*************.****.*.******...*******.****.****.*.****.**.**.*..***.******.*******************.*
********.*.***......*****..**.*..**.*.******.****.***********.*********.******.*********************
******************.*****..*.*.*****.*.*..***.*.*...*...****.*******.************.*******************
*..*.***.*.***.*..***.******.***.*..***********.*********.***********...*.********************.*****
******.**.**.*.************.*********....**..***.**.****.**..****.*.**.***********.*****************
**.**.**.*******.*..*.****.*.*.******.***.****.**.**.**.********.****.******.*****.*****************
*******.*.****.*.******..**.****.****.*..***.****....*.****.****.*****************************.*****
************.**.**.**.**.*.***..*.*..***.*.****..*****.***..*********.*******************.**********
*****************************..*.**..***..*...******..*********.**.*.****.****.*.*.*******.*********
***.*.***.**.****.*****.***..**.*****.***.**..***********.**.**..***.***********.********.**********
****************************.*.**.**..*.*..*.**.*.*.**.****.*.*.**.*.**.********.*******************

You should obtain a solution that uses 80 colours.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh » Wed Jan 28, 2004 1:34 am

Yep, correct :-)

Miguel Angel
Learning poster
Posts: 60
Joined: Tue Aug 13, 2002 2:39 am
Location: Mexico

Post by Miguel Angel » Wed Jan 28, 2004 7:22 am

Yeap, correct mine gives 81..some suggestion?
:D Miguel & Marina :D

Nikolay Archak
New poster
Posts: 6
Joined: Tue Dec 02, 2003 6:43 am
Contact:

min edge coloring in bipartite graph

Post by Nikolay Archak » Wed Jan 28, 2004 11:03 am

IMHO, this problem is about graph coloring.
We have a bipartite graph with first set of vertices representing rows & second set of vertices representing columns. Row vertex is connected with appropriate column vertex
if and only if there is a rook in the appropriate cell.
So, we have to find a minimal edge coloring for this graph.
The problem is quite complex for general case, however the graph is bipartite which makes
things simpler. For example, it is known that minimal number of colors for such graph
is just a maximum vertex degree. I was too lazy to study the whole bunch of papers on
the subj. found in the Internet, so I just tried to implement the dummy algorithm,
which works as following:
1. ncolors=0;
2. if g is empty go to step 6.
3. find maximal bipartite matching M
4. ncolors++. All edges from matching M are colored in color ncolor and removed from graph
5. go to step 2
6. output

It worked OK on sample tests, it even passed Adrian's example correctly
(returned 80 colors).
However, its not that fast - approx 3s in the online-judge (note that my IO
is not that quick also)
and it still gets WA.
Perhaps my alg is inherently wrong? I'll be glad for any comments and hints.
:o

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Jan 28, 2004 11:20 am

I think you can not assume that you can incrementally color the edges and never change a color back. It is like you try to find k maximum matchings by removing maximum matchings one by one. But it may happen with this approach that after some steps you can't find maximum matching again, so you will need more than k colors (where k is the maximum vertex degree).
By the way, first I tried to solve this problem with network flow, but didn't found a way. Has anybody who got Accepted solved it with network flow?

gawry
New poster
Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Post by gawry » Sat Jan 31, 2004 6:07 pm

It's possible to solve this problem by finding maximum matchings, you have to add to this graphs edges so that it becomes d-regular (where d is maximum vertex degree). From Hall's theorem such graph has exactly d edge-disjoint perfect matchings, so we can just color each of them with one color and then take only edges that were in the orginal graph.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Feb 02, 2004 12:11 pm

Maybe I misunderstand you, but in general, I think it might not be possible to make the graph d-regular. For instance, consider the case:

Code: Select all

***.
.***
.**.
....
How would you make that one d-regular?

Protik
New poster
Posts: 1
Joined: Wed Apr 02, 2003 7:52 am
Location: Dhaka

Post by Protik » Mon Feb 02, 2004 4:07 pm

Maybe I misunderstand you, but in general, I think it might not be possible to make the graph d-regular
make it a multigraph, allow parallel edges. Then it is possible to make a graph d-regular.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Feb 13, 2004 1:48 pm

Everyone interested in this problem can read a paper
"Algorithms for edge coloring bipartite graphs" by Harold N. Gabow and Oded Kariv.

They talked about there is a algorithm using matching to solve the problem by the fact: "A bipartite graph has a matching that cover all the vertices with maximum degree"

So if we can find such matching in the bipartie graph, we can solve the problem by finding such matchings for each color. I tried to implement it, but I gets WA on the judge. So I used the augmenting path algorithm, get AC in 0.1s
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Fri Feb 13, 2004 7:03 pm

.. wrote:Everyone interested in this problem can read a paper
"Algorithms for edge coloring bipartite graphs" by Harold N. Gabow and Oded Kariv.
Hello, I used google to find the paper.
But it needs a ACM account. I don't have one :(
Would some paper offer the same content or where can find this paper
thx :)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Fri Feb 13, 2004 7:38 pm

Oh~~
I find the paper though the university library, so I have no problem in accessing ACM digital lirbary.

There are many papers talk about edge coloring of bipartite graph.
I recommend this one just because it is easy to read and it lists many algorithms.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Minilek
Learning poster
Posts: 90
Joined: Tue Jul 27, 2004 9:34 am
Location: Cambridge, MA
Contact:

Post by Minilek » Tue Aug 17, 2004 6:38 am

We have a bipartite graph with first set of vertices representing rows & second set of vertices representing columns. Row vertex is connected with appropriate column vertex
if and only if there is a rook in the appropriate cell.
How do we have a bipartite graph? Don't we have a k-partite graph with nodes representing cells and edges between nodes iff they are in the same row or column? Also, isn't this problem exponential time to solve?

[EDIT]
N/m, I see what's going on now.
now time to find out what d-regular means. ^_^ *reads*
[/EDIT]

Post Reply

Return to “Volume 106 (10600-10699)”