11134 - Fabled Rooks

[vinay]

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??

[taha]

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]

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]

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;
}    

[vinay]

no one replying..??

[Kevin]

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]

can anyone help me on my code plz..

its WA..

its given above in this thread...

[vinay]

can anyone give some test cases atleast...
i think its some boundary conditions...

[liulike]

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]

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

The answer is not IMPOSSIBLE
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]

Hello,

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

Cu, Erik

[vijay_comsci]

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

[Erik]

Hi,

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

Cu, Erik