10615 - Rooks

[Miguel Angel]

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

[Adrian Kuegel]

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]

Yep, correct

[Miguel Angel]

Yeap, correct mine gives 81..some suggestion?

[Nikolay Archak]

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.

[Adrian Kuegel]

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]

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]

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]

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.

[..]

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

[windows2k]

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

[..]

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.

[Minilek]

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]