11134 - Fabled Rooks

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11134 - Fabled Rooks

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

Post by 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
New poster
Posts: 28
Joined: Fri May 30, 2003 12:47 am

Post by 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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by 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;
}    
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:

Post by vinay »

no one replying..?? :oops:
If I will myself do hashing, then who will do coding !!!

Kevin
New poster
Posts: 7
Joined: Tue Oct 24, 2006 2:14 am

Post by 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
Experienced poster
Posts: 104
Joined: Thu Apr 13, 2006 2:26 pm
Location: India
Contact:

Post by vinay »

can anyone help me on my code plz.. :oops:

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:

Post by vinay »

can anyone give some test cases atleast...
i think its some boundary conditions... :cry:
If I will myself do hashing, then who will do coding !!!

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike »

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) :D

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

vinay wrote:can anyone give some test cases atleast...
i think its some boundary conditions... :cry:
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. 8)

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

Post by Erik »

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)

Post by vijay_comsci »

:o 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:

Post by Erik »

Hi,

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

Cu, Erik :)

Post Reply

Return to “Volume 111 (11100-11199)”