×

# RKS - Editorial

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi

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.

This question is marked "community wiki".

7★watcher
37
accept rate: 0%

19.8k350498541

 0 Video Editorial : https://youtu.be/ti0JMOsDorQ answered 29 Jan, 21:41 3★ivabby 1●1 accept rate: 0%
 0 It can be done using only 2 bool[n] variables. answered 30 Jan, 16:50 1 accept rate: 0%
 0 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 row-a and column-b... so we keep deleting the values a from row and b from column. That's it now we have to print n-k 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 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×968
×39