You are not logged in. Please login at www.codechef.com to post your questions!

×

RKS - Editorial

PROBLEM LINK:

Practice
Contest

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.

This question is marked "community wiki".

asked 24 Jan, 00:26

watcher's gravatar image

7★watcher
37
accept rate: 0%

edited 27 Jan, 20:34

admin's gravatar image

0★admin ♦♦
19.8k350498541


Video Editorial : https://youtu.be/ti0JMOsDorQ

link

answered 29 Jan, 21:41

ivabby's gravatar image

3★ivabby
11
accept rate: 0%

It can be done using only 2 bool[n] variables.

link

answered 30 Jan, 16:50

yashasvigoel's gravatar image

2★yashasvigoel
1
accept rate: 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!

@executable

link

answered 31 Jan, 02:37

executable's gravatar image

3★executable
11
accept rate: 0%

edited 31 Jan, 02:47

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 24 Jan, 00:26

question was seen: 696 times

last updated: 31 Jan, 02:47