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

×

ADAROKS - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Alei Reyes
Tester- Pranjal Jain
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium-Hard

PRE-REQUISITES:

Bitmasking, Data Structures

PROBLEM:

Given a chessboard with kings placed on it, you need to find minimum number of rooks to place such that kings cannot reach each other. Rooks cannot be attacked by the kings for simplicity.

QUICK-EXPLANATION:

Key to AC- Realize that since $N*M \leq 1024$, at least one of the dimensions must be less than $32$. Now if we remove rows where kings are, and merge groups of empty rows into a single row, there can be at most $16$ rows where we can put rooks. Bitmasking + Clever Brute Force is the way to go.

Without loss of generality, assume $N \leq M$, otherwise we can simply transpose the matrix and obtain the same result. This caps $N$ to $N \leq 32$. Now, we need to see how many rows we can put rooks on. Out of these $32$ rows, remove rows where kings are placed as rook cannot be placed there without attacking the king. Once its done, see that you might get some consecutive rows which don't have king on them. Placing a rook on any of the row gives same effect, as long as we place it in the same column. Hence, merge them all into single row. We see that this limits maximum number of rows we can place rooks on to $N \leq 16$.

Try all possible subsets of rows on which we can place rooks. With rows decided, we now only need to see which columns we have to place rook. This problem can be shown equivalent to finding minimum number of lines to cut given set of intervals (where every interval must be cut by a line). The solution to this is, sort the intervals and greedily pick an interval to cut. All intervals intersecting with this interval are also cut by line and hence are removed. Repeat until no interval is left.

EXPLANATION:

The editorial will be modularized into parts. You can feel free to jump at and start from the part unclear to you, provided you are clear with the parts before it :)

1. How to arrive at $N \leq 16$ result-

First convince yourself that the board's area is $\leq 1024$. Now, this means, that at least one dimension must be $\leq \sqrt{1024}$, i.e. $\leq 32$. Without loss of generality, assume that $N \leq M$, as if thats not the case, we can rotate the matrix by $90^\circ$ and get same result.

Now, put kings alternatively on these $32$ rows. That is, keep one king at row $1$, next at row $3$...and so on. We see that we have exactly $16$ rows with kings, and $16$ free rows.

We are to see that we can, at no instance, have more than $16$ free rows. Now, addition of any more kings cannot increase number of free rows, as a rook cannot be placed in same row as of king. Also, if we remove any of the king, then the group of free rows will merge, again decreasing number of free rows. Also, we can see that the configuration we chose is a maximal one, no other configuration exists which has more free rows than this.

Hence, number of rows where rooks can be put (or free rows as I called earlier) are $\leq 16$

2. Getting bit-masking (without dp :p) into the picture-

The above observation of $N \leq16$ makes life veryy convenient. The reason being, now we have $2^16$ possible choices of keeping rooks on the rows. This is, $=65536$ combinations to try, at max. Hence, we can simply try all the combinations!

Once we are decided on which rows we have to put the rooks, I think you all can agree that the problem becomes somewhat simpler, and something which can be done with much less effort than what we imagined on reading the statement.

Next part deals with how to calculate the final answer. In case you wish to do an independent try without any more spoilers from editorial, this is your checkpoint :p

Calculating the final answer-

We store the column and row numbers of positions where kings are placed, so as to not to place rooks on them. Now, lets say we are placing rooks at row $i$ and row $j$, as per our current combination. Obviously, there should not be two kings on same column, else they can reach each other (recall that rooks are being placed ONLY at rows specified by our mask). Let me call the part of board bounded by row $i$ and row $j$ as $region$.

Now, you can model the problem as, "Given possible intervals of free columns, where we have to place rooks (recall we need to place rooks between $2$ kings in same region!), what are minimum number of rooks to place such that each interval has at least $1$ rook assigned to it."

The solution for this is to, sort all such intervals and greedily place rooks at larger interval, and eliminate intervals where rooks are already set.

"I cannot understand how to make these intervals."

In case those are your words, then read on :p

Now, for all columns from $[1,M]$, start from row $i+1$ and iterate up to row $j-1$. Make a vector $v$ to store column numbers of any kings up see. This ensures columns are put in sorted order in $v$.

Now, lets say we are looking at king present on index $idx$ on $v$. Our interval would be, all free columns after column of king at $v[idx-1]$ and all columns before those of king at $v[idx]$. A rough implementation is below-

View Content

SOLUTION

Setter

View Content

Tester

View Content

$Time$ $Complexity=O(2^{min(N,M)}*M*N)$
$Space$ $Complexity=O(N*M)$

CHEF VIJJU'S CORNER :D

1. Given $N*M$ dimensional chess board, how many knights can you put at it such that no knight attacks each other? Solution

2. Given a $N*N$ dimensional chess board, what if we ask to place bishops instead of knights in above problem. Can you draw a recurrence for it? Solution

3. Setter's Solution-

View Content

4. Tester's Solution-

View Content

5. Related Problems-

This question is marked "community wiki".

asked 19 Jan, 22:30

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 21 Jan, 01:17

admin's gravatar image

0★admin ♦♦
19.8k350498541

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:

×1,406
×160
×145
×18

question asked: 19 Jan, 22:30

question was seen: 235 times

last updated: 21 Jan, 01:17