PROBLEM LINK:
Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: 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 N-K. 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 N-K.
Two rooks attack each other if they’re on the same row or on the same column. Since no two of the given rooks attack each other, all of the rows given in the input are unique. Similarly, all of the columns given in the input are unique. So, we’re left with N-K unused rows and N-K unused columns to put the new rooks on. To put N-K new rooks on the board, we can pair each of these rows with a distinct column and for each pair, put a rook on the intersection of the row and the column in that pair.
To conclude the proof, note that if we place more than N rooks on an N \times N chessboard, two rooks will definitely share a row and hence, attack each other. So the answer cannot be larger than N-K.
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.
Tester’s solution can be found here.