Raging Rooks

Computer Science Level 5

King Jack wants to prevent enemy pieces from landing on his land. To accomplish this, he will place pieces on as few squares as possible such that every square is attacked, and so any invader will be taken. His piece of choice is the Rook. He already placed a few rooks, but now attacks are becoming more frequent, and he must place more.

His land consists of a $1,000,000\times 1,000,000$ grid of squares, and he currently has $10,000$ rooks already deployed in $10,000$ positions (not necessarily distinct) onto the board. The positions are pairs of integers, $(x_i,y_i)$ with $1\le x_i,y_i\le 1,000,000$ . Your task is to find the last three digits of the minimum number of additional rooks Jack needs such that every square on his land is attacked by at least one rook.

Sample input (on a $4\times 4$ grid with 4 rooks already placed)

1 3

2 2

2 4

4 3

Input explanation

The rooks are placed on squares $(1,3)$ , $(2,2)$ , $(2,4)$ , and $(4,3)$ .

Answer and explanation

Only $1$ rook is needed, which will be placed at $(3,1)$ .

Note that the actual input has 10000 positions.

Details and assumptions

You may find the list of positions here . Each of the 10000 lines contains a space-separated pair of integers $(x_i,y_i)$ that corresponds to the position of a single rook.

A rook attacks every square in the same row as it and/or the same column as it, and so a square with a rook is considered to be attacked.

The answer is 37.

4 solutions

Lokesh Sharma
Dec 27, 2013

Python Solution:

positions = open('raging_rooks.txt', 'r')
positions = [position.rstrip().split() for position in positions]
x, y = [], []
for i in positions:
    x.append(i[0])
    y.append(i[1])
print max(1000000 - len(set(x)), 1000000 - len(set(y)))

print min(1000000 - len(set(x)), 1000000 - len(set(y)))

Thaddeus Abiy - 7 years, 5 months ago

Here is the proof of why this solution works...

Suppose that the board is protected. This means, obviously, that every row and column is protected.

Pick an arbitrary protected column. If it has at least one rook on it, then it is trivially protected by that rook.

Suppose that chosen column doesn't have a rook and it is protected. But, since it is protected, it means that there must be a rook on every row that protects every square of that column.

Therefore, for any protected board, either every row has a rook or every column has a rook.

Now look that if every column(row) has a rook, then the whole board is protected.

Therefore a board is protected if and only if it has a rook in every colum or in every row.

This helps to compute the minimal amount of rooks, since we need either all the columns or all the rooks to have a rook, we have to compute how many rooks do we need to fill the columns and how many rooks do we need to fill the rows. The minimal will be the lowest of those two numbers.

Isaí Vázquez - 7 years, 4 months ago

Note: For a list 'x', set(x) gives all the distinct elements in 'x'.

For example, if x = ['1', '2', '2', '3'], set(x) = ['1', '2', '3']

Lokesh Sharma - 7 years, 5 months ago

Nice short solution. How long did it take to run?

Daniel Chiu - 7 years, 5 months ago

It took 0.12 seconds but when I ran it second time it took 0.17 seconds and some other time in the next run. Is it normal?

Lokesh Sharma - 7 years, 5 months ago

That isn't too surprising.

Daniel Chiu - 7 years, 5 months ago

Isaí Vázquez
Oct 13, 2015

Here is the proof of why this solution works...

Suppose that the board is protected. This means, obviously, that every row and column is protected.

Pick an arbitrary protected column. If it has at least one rook on it, then it is trivially protected by that rook.

Suppose that chosen column doesn't have a rook and it is protected. But, since it is protected, it means that there must be a rook on every row that protects every square of that column.

Therefore, for any protected board, either every row has a rook or every column has a rook.

Now look that if every column(row) has a rook, then the whole board is protected.

Therefore a board is protected if and only if it has a rook in every colum or in every row.

Thaddeus Abiy
Jan 10, 2014

I just place a piece in either an unoccupied row or an unoccupied column and count it. I used the following algorithm:

Go through each column x
If any cell in column x is not occupied, Add one to the variable Rx ;
Go through each row x
If any cell row x is not occupied,Add one to the variable Ry
Compare Rx and Ry ,the smaller one is our answer

A technical problem I faced was that checking if a specific value exists in a list object using in in python is very very slow. It took several minutes for the code to run. But surprisingly putting the values in a set object really sped things up.It cut the run-time dramatically to 1.81 seconds.The code below directly reads from the input file raging_rooks.txt ,splits the file,stores the values into tuples,executes the algo above,prints out the answer( 990037 ) and the time taken for the code to run.

from time import *     #Imported for timing the program
start =time() 
with open('raging_rooks.txt','r') as D:      
        All = [tuple(map(int,(i.split()[0],i.split()[1]))) for i in D.read().split('\n')  ]       
        Lim = 10**6
        Allx = set([i[0] for i in All])        
        Ally = set([i[1] for i in All])
        Rx , Ry = 0 , 0
        for x in range( 1 , Lim + 1 ):
            if not x in Allx:Rx+=1
            if not x in Ally:Ry+=1
        if Rx > Ry:print Ry
        else:print Rx
        print 'Time take is ',time()-start

Tarun Chabarwal
Jan 9, 2014

Minimum is the number of rows or columns left

Make two arrays representing 10^6 positions, one for row and other one for column. Count left number of columns and rows and return the minimum

include"stdio.h" char row[1000001], col[1000001]; int main() { int i=10000, p, q; while(i--) { scanf("%d %d", &p, &q); row[p] = 1; col[q] = 1; } p = 0;q=0; for(i=1;i<=1000000;i++){ if(!row[i])p++; if(!col[i])q++; } printf("%d", (p<q)?p:q); return 0; }

Tarun Chabarwal - 7 years, 5 months ago

Raging Rooks

The answer is 37.

4 solutions

0 pending reports