11134 - Fabled Rooks

Moderator: Board moderators

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

11134 - Fabled Rooks

i know that rows n columns can be solved independently..
but how to do that in efficient way...
i tried O(n^2) but its clearly going to time limit .. any better algo??
If I will myself do hashing, then who will do coding !!!

taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt
I used N^2 and it is accepted. (it runs in time), May be your bug is in the stopping condition of the input.

subbu
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am
You can do it in O(NlogN).

You can solve for the columns and rows independently, as you mentioned.
For assigning the rooks to different columns, here is a hint, in the form of questions

You can ignore 1 below, if you know an O(N^2) solution aleady.
1) Let x = how many rooks can be assigned to the first column.
1a) What if x = 0?
1b) What if x = 1 ?
1c) What if x > 1 ? Which rook among those that match, would you choose, so that if there is a solution, there is a solution with this rook chosen.

After answering the above, you will probably have an idea of the solution, and a way to do it in O(N^2).

For getting to O(NlogN),

Choosing the "best rook" for the current column C depends on
1) rooks assigned so far
2) rooks whose range contains the current column.
3) Among the rooks whose range contains C, which one has the "least" range to the right of the current column. Can the right end point of the "range" of these rooks help ?

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
i had that nlogn algo in mind when going for the N^2 one ...

but the N^2 tled..

then i tried nlong n , but it gives WA...

any one can have a look at it??

Code: Select all

``````
#include<vector>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<iostream>
#include<string>
#include<stack>
#include<cstdlib>
#include<queue>
#include<set>

#define ALL(data) data.begin(),data.end()
#define VI vector<int>
#define VVI vector<vector<int> >
#define VS vector<string>
#define VSI vector<vector<string> >
#define PB push_back

using namespace std;

struct node{

int index;
int l;
int r;
}   ;

struct nd{

int index;
int x;
} ;

int n;
bool f;

bool operator<(const node& a ,const node& b){

if(a.r==b.r){

return a.l<b.l;
}

return a.r<b.r;

}

bool operator<(const nd& a ,const nd& b){
return a.index<b.index;
}

vector<nd> fun(vector<node> v){

vector<nd> ret(n);

sort(v.begin(),v.begin()+n);

for(int i=0;i<n;i++){

if(v[i].l-1>i || v[i].r-1<i) {

f =  true;
return ret;
}

ret[i].x = i+1;
ret[i].index = v[i].index;
}

return ret;
}
int main(){

vector<node> x(5001),y(5001);

vector<nd> vX , vY;

scanf("%d",&n);
while(n){

for(int i=0;i<n;i++){

x[i].index = i;
y[i].index = i;
scanf("%d%d%d%d",&x[i].l,&y[i].l,&x[i].r,&y[i].r);
}

f = false;

vX = fun(x);

if(f){

printf("IMPOSSIBLE\n");
}

else{

vY = fun(y);
if(f){

printf("IMPOSSIBLE\n");
}

else{

sort(vX.begin(),vX.begin()+n);
sort(vY.begin(),vY.begin()+n);

for(int i=0;i<n;i++){

printf("%i %i\n",vX[i].x,vY[i].x);
}
}

}

scanf("%d",&n);
}
return 0;
}
``````
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
If I will myself do hashing, then who will do coding !!!

Kevin
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am
First key to this problem is columns and rows are independent.
Second key is within a row or column, the areas a rook can be matched to are contiguous.

Priority Queue + Sweep = O(nlgn)

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
can anyone help me on my code plz..

its WA..

its given above in this thread...
If I will myself do hashing, then who will do coding !!!

vinay
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:
can anyone give some test cases atleast...
i think its some boundary conditions...
If I will myself do hashing, then who will do coding !!!

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
subbu wrote:You can do it in O(NlogN).

You can solve for the columns and rows independently, as you mentioned.
For assigning the rooks to different columns, here is a hint, in the form of questions

You can ignore 1 below, if you know an O(N^2) solution aleady.
1) Let x = how many rooks can be assigned to the first column.
1a) What if x = 0?
1b) What if x = 1 ?
1c) What if x > 1 ? Which rook among those that match, would you choose, so that if there is a solution, there is a solution with this rook chosen.

After answering the above, you will probably have an idea of the solution, and a way to do it in O(N^2).

For getting to O(NlogN),

Choosing the "best rook" for the current column C depends on
1) rooks assigned so far
2) rooks whose range contains the current column.
3) Among the rooks whose range contains C, which one has the "least" range to the right of the current column. Can the right end point of the "range" of these rooks help ?
Nice! Heap will work for N*log(N)

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
vinay wrote:can anyone give some test cases atleast...
i think its some boundary conditions...
I think your code fails this:

Code: Select all

``````3
1 1 3 3
1 1 3 3
2 2 2 2
``````
There are 4 possible solutions, for example

Code: Select all

``````1 1
3 3
2 2
``````
This case doesn't appear in the sample input, so it's easy to miss.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hello,

there is an almost O(n) solution even better than O(n*log(n)).

Cu, Erik

vijay_comsci
New poster
Posts: 2
Joined: Wed May 17, 2006 11:29 pm
Location: INDIA

plz .. O(n)

there is an O(n) solution !!!
Plz can u give ny hints for that...
thanx !

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hi,

there is just one famous algorithm I know that is "almost O(n)".

Cu, Erik