11134  Fabled Rooks
Moderator: Board moderators
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??
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 !!!
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 ?
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 ?
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??
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].l1>i  v[i].r1<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 !!!
Nice! Heap will work for N*log(N)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 ?
I think your code fails this:vinay wrote:can anyone give some test cases atleast...
i think its some boundary conditions...
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

 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 !
Plz can u give ny hints for that...
thanx !