PROBLEM LINK:Author: Michael Nematollahi PREREQUISITES:None PROBLEM:There's an $N \times N$ chessboard given. There are already K rooks placed on it in a way that no two of them attack each other. Find out what is the maximum number of rooks you can add to the board without having any two rooks attacking each other. Print a configuration that lexicographically minimizes the output sequence. QUICK EXPLANATION:The answer is $NK$. Match the smallest unused row with the smallest unused column, the second smallest unused row with the second smallest unused column and so on to achieve the lexicographically minimum configuration. EXPLANATION:First, let's prove that the maximum number of rooks that can be added is $NK$. All that's left is to find the lexicographically minimum answer. This answer can be achieved by pairing the smallest unused row with the smallest unused column, the second smallest unused row with the second smallest unused column and so on. This solution's complexity is $O(N)$. To see the implementation, refer to the setter's solution. AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 24 Jan, 00:26

An easy implementation would be to maintain two sets of row and column and assign them with values (1 to N).... Now k lines would contain two inputs, let them be a and b so we know that the rooks can't be placed in rowa and columnb... so we keep deleting the values a from row and b from column. That's it now we have to print nk and remaining elements of set. link to the solution : https://github.com/executable16/CodeChef/blob/master/ROOKS.cpp New ideas are welcome! answered 31 Jan, 02:37
