Problem Statement
Given an n × m chessboard, try and place as many rooks as possible on the board in such a way that the number of rooks on each row is equal to the number of rooks on each column (it is allowed for two rooks to attack each other). You are prohibited from placing the rook at some given locations on the board.
Source
This problem was an exercise left to the reader on a Topcoder tutorial click.
After many attempts, I am unable to formalise a solution. To be more specific neither was I able to formulate this problem as an instance of max-flow, nor was I able to model it as an instance of min-cut.
My observations
- The total number of rows that contain a rook must be equal to the total number of columns that contain a rook
- Could we possibly binary search for the solution and construct a bipartite graph for each candidate solution in the binary search?
it seems that I misunderstood the problem, because this is the solution:
if n != m answer is 0
if n == m answer is n * m
Yes, you should binary search the answer and construct a bipartite graph. One side of the graph should be vertices representing rows, the other should be vertices representing columns. For each allowed cell connect its row with its column with an edge of capacity 1. Now connecting row-vertices with the source allows you to limit the number of rooks in each row. The same for columns. Do you see the solution now?
If max flow is less than nk then reduce the value of k, else try to increase it?
Yes.
And the answer is simply 0 if n ≠ m if I understood the problem correctly.