Page 1 of 3

540 - Team Queue

Posted: Sun Aug 22, 2004 12:27 am
by RuiFerreira
hi!

i'm having WA and don't really know why...

does any one have larger or tricky inputs?

Code

Posted: Tue Aug 24, 2004 4:41 pm
by RuiFerreira
As no one answer I'll put my code so you can analyse...

It enqueues and dequeues in constant time as it is suposed...

Thanks

found error!
[cpp][/cpp]

thanks

540- Team Queue, RTE

Posted: Tue Apr 25, 2006 11:27 am
by serur
Hello Problem Hunters!

The stuff below gives me RTE in 0.000 CPU:

Code: Select all

/*"Team Queue"*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
#define N 1000000
#define M 1000

int ind[N];

typedef struct NODE{
	struct NODE *Next;
	int ID;
}NODE;

typedef struct{
	NODE *HeadPtr;
	NODE *TailPtr;
	int NumItems;
}QUEUE;

NODE *TeamTailPtr[M];

Add(NODE **Item,int fellow)
{
	NODE *NewNode=malloc(sizeof *NewNode);
	NewNode->ID=fellow;
	if(NULL==*Item)
	{
		NewNode->Next=NULL;
		*Item=NewNode;
	}
	else
	{
		NewNode->Next=(*Item)->Next;
		(*Item)->Next=NewNode;
	}
}
NODE *DeleteThis(NODE *Item)
{
	NODE *NextNode=malloc(sizeof *NextNode);
	NextNode=Item->Next;
	free(Item);
	return NextNode;
}
enQueue(QUEUE *Q,int fellow)
{
	long t=ind[fellow];
	if(TeamTailPtr[t]==NULL)
	{
		Add(&Q->TailPtr,fellow);
		TeamTailPtr[t]=Q->TailPtr->Next;
		if(!Q->NumItems)
			Q->HeadPtr=Q->TailPtr;
	}
	else
	{
		Add(&TeamTailPtr[t],fellow);
		if(TeamTailPtr[t]!=NULL)
			TeamTailPtr[t]=TeamTailPtr[t]->Next;
	}
	++Q->NumItems;
}
deQueue(QUEUE *Q,int *fellow)
{
	*fellow=Q->HeadPtr->ID;
	Q->HeadPtr=DeleteThis(Q->HeadPtr);
	--Q->NumItems;
	if(!Q->NumItems)
		Q->TailPtr=NULL;
}
QUEUE *create(){
	QUEUE *Q=malloc(sizeof *Q);
	Q->HeadPtr=Q->TailPtr=NULL;
	Q->NumItems=0;
	return Q;
}

int empty(QUEUE *Q){return (!Q->NumItems)?(1):(0);}

int main()
{
	QUEUE *Q;
	long cs=0;
	long fellow,T,n,team;
	char command[100];
#ifndef ONLINE_JUDGE
	freopen("A.in","r",stdin);
#endif
	scanf("%ld",&T);
	while(T)
	{
		Q=create();
		for(team=0;team<T;team++)
		{
			scanf("%ld",&n);
			while(n--)
			{
				scanf("%ld",&fellow);
				ind[fellow]=team;
			}
			TeamTailPtr[team]=malloc(sizeof *TeamTailPtr[team]);
			TeamTailPtr[team]=NULL;
		}
		printf("Scenario #%ld\n",++cs);
		scanf("%s",&command);
		while(command[0]!='S')
		{
			if(command[0]=='E')
			{
				scanf("%d",&fellow);
				enQueue(Q,fellow);
			}
			else
			{
				deQueue(Q,&fellow);
				printf("%ld\n",fellow);
			}
			scanf("%s",&command);
		}
		scanf("%ld",&T);
		printf("\n");
	}		
	return 0;
}

Posted: Wed Apr 26, 2006 11:16 am
by serur
Thanks a lot!
I got ACC.
Very GOOD Problem on simulation and modeling.
Due to this problem I learned a lot about pointers, so can anyone tell me some other similar problems?

540 Attack!!!!!

Posted: Wed Sep 27, 2006 12:11 am
by rmotome
My algorithm times-out during it's run. I am asking for help optimizing my approach. I keep two doubly-linked lists (1) a freelist (2) the team queue. I start by adding every element into the freelist and remove each as they are ENQUEUEd into the team queue. Searching the freelist and adding into to the team queue will take no longer than O(n) since the sum of links in the freelist + team queue addup to n. What is wrong with my code?

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<ctype.h>
typedef struct node *link;
struct node{int n;
int team;
link prev;
link next;
};
link NEW(int n,int team,link prev,link next)
{link x = malloc(sizeof *x);
x->n = n;
x->team = team;
x->prev = prev;
x->next = next;
return x;
}
typedef struct{
link head;
link tail;
}Queue;
void init(Queue* Q)
{
Q->head = malloc(sizeof *Q->head);
Q->tail = malloc(sizeof *Q->tail);
Q->head->next = Q->tail;
Q->head->prev = Q->head;
Q->tail->prev = Q->head;
Q->tail->next = Q->tail;
}
link begin(Queue* Q)
{return Q->head->next;}
link end(Queue* Q)
{return Q->tail;}
void insert(Queue* Q,link t)
{link x;
x=Q->head;
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
}
link delete(Queue* Q,link t)
{t->next->prev = t->prev;
t->prev->next = t->next;
return t;
}
int empty(Queue* Q)
{return begin(Q)==end(Q);}
void tqinsert(Queue* Q,link t)
{link x;
for(x=end(Q)->prev; x!=Q->head; x = x->prev)
if(x->team == t->team)break;
if(x==Q->head)
x = end(Q)->prev;
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
}
main()
{
Queue Q1,Q2;
link x;
int n,p,q,r;
link t;
char s[100];
int C;
C=1;
while(scanf("%d",&n)==1){
if(n==0)break;
init(&Q1);
init(&Q2);
while(n--){
scanf("%d",&p);
while(p--){
scanf("%d",&q);
insert(&Q1,NEW(q,n,NULL,NULL));
}
}
printf("Scenario #%d\n",C);
C++;
scanf("\n");
while(scanf("%s",s)==1){
if(s[0]=='S')break;
else if(s[0]=='E'){
scanf("%d",&r);
for(t=begin(&Q1); t!=end(&Q1); t = t->next)
if(t->n== r)break;
tqinsert(&Q2,delete(&Q1,t));
}else{
if(!empty(&Q2)){
t = begin(&Q2);
printf("%d\n",t->n);
delete(&Q2,t);
free(t);
}
}
}
printf("\n");
}
}

Posted: Wed Sep 27, 2006 5:57 am
by rmotome
ANS: keep an updated link to the last element of each group thus reducing ENQUEUE to O(1)

Posted: Wed Sep 27, 2006 7:20 am
by rmotome
I am getting RTE, help me out by giving me valid input
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
#include<ctype.h>
#define T 1000
#define Z 1000000
typedef struct node *link;
struct node{int n;
int team;
link prev;
link next;
};
link NEW(int n,int team,link prev,link next)
{link x = malloc(sizeof *x);
x->n = n;
x->team = team;
x->prev = prev;
x->next = next;
return x;
}
typedef struct{
link head;
link tail;
int N;
}Queue;
link last[T+1];
int team[Z+1];
void init(Queue* Q)
{
Q->head = malloc(sizeof *Q->head);
Q->tail = malloc(sizeof *Q->tail);
Q->head->next = Q->tail;
Q->head->prev = Q->head;
Q->tail->prev = Q->head;
Q->tail->next = Q->tail;
Q->N=0;
}
link begin(Queue* Q)
{return Q->head->next;}
link end(Queue* Q)
{return Q->tail;}
void insert(Queue* Q,link x,link t)
{
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
Q->N++;
}
link delete(Queue* Q,link t)
{
assert(!empty(Q));
t->next->prev = t->prev;
t->prev->next = t->next;
Q->N--;
return t;
}
int empty(Queue* Q)
{return Q->N==0;}
int size(Queue* Q)
{return Q->N;}
main()
{
Queue Q1,Q2;
link x;
int n,p,q,r;
link t;
char s[100];
int C;
int i,j,k;
C=1;
while(scanf("%d",&n)==1){
if(n==0)break;
for(i=0; i<=T; i++)
last=NULL;
init(&Q2);
while(n--){
scanf("%d",&p);
while(p--){
scanf("%d",&q);
team[q]=n;
}
}
printf("Scenario #%d\n",C);
C++;
scanf("\n");
while(scanf("%s",s)==1){
if(s[0]=='S')break;
else if(s[0]=='E'){
scanf("%d",&r);
x = NEW(r,team[r],NULL,NULL);
if(last[team[r]]==NULL)
insert(&Q2,end(&Q2)->prev,x);
else insert(&Q2,last[team[r]],x);
last[team[r]]=x;
}else{
if(!empty(&Q2)){
t = begin(&Q2);
printf("%d\n",t->n);
delete(&Q2,t);
free(t);
}
}
}
printf("\n");
}
}

540 RTE~ help

Posted: Tue Jan 02, 2007 10:47 am
by scan33scan33
I have got RTE on this problem for long
I tested some cases , and fonud all of them are right.
Can anyone help me with the problem?

Here is my code:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct queue{
int data;
struct queue *next;
};

struct squeue{
int data;
struct queue *next;
struct queue *tail[2000];
};

typedef struct queue Queue;
typedef struct squeue StQueue;

int used[2000],team[2000000],answers[500000];

void init(StQueue **q);
void enqueue(StQueue *q, int data);
int dequeue(StQueue *q);
int empty(StQueue *q);
void printqueue(StQueue *q);


int main()
{
char order[20];
int us_all,team_all,atmp,ntmp,i,j,ti=0,number,pf_all;
StQueue *stq;
while(1)
{
++ti;
scanf("%d",&team_all);
if(team_all==0)
return 0;
for(j=0;j<=team_all;j++)
used[j]=0;
for(j=1;j<=team_all;j++)
{
scanf("%d",&atmp);
for(i=0;i<atmp;i++)
{
scanf("%d",&ntmp);
team[ntmp] = j;
}
}
init(&stq);
pf_all=0;
while(1)
{
scanf("%s",order);
if(strcmp("ENQUEUE",order)==0)
{
scanf("%d",&number);
enqueue(stq,number);
}
else if(strcmp("DEQUEUE",order)==0)
{
answers[pf_all] = dequeue(stq);
pf_all+=1;
}
else if(strcmp("STOP",order)==0)
break;
}
printf("Scenario #%d\n",ti);
for(i=0;i<pf_all;i++)
printf("%d\n",answers);
printf("\n");
}
}

void init(StQueue **q)
{
*q = (StQueue*)malloc(sizeof(StQueue));
(*q)->next = NULL;
}

int empty(StQueue *q)
{
return (q->next==NULL);
}

void enqueue(StQueue *q, int data)
{
Queue *qtmp,*qtmp2;
qtmp = (Queue*)malloc(sizeof(Queue));
qtmp->data = data;
if(empty(q))
{
qtmp->next = q->next;
q->next = qtmp;
q->tail[0] = qtmp;
q->tail[team[data]] = qtmp;
used[team[data]]=1;
}
else if(used[team[data]]==0)
{
qtmp->next = q->tail[0]->next;
q->tail[0]->next = qtmp;
q->tail[0] = qtmp;
q->tail[team[data]] = qtmp;
used[team[data]]=1;
}
else if(used[team[data]]!=0)
{
if(q->tail[team[data]]->next==NULL)
{
qtmp->next = q->tail[team[data]]->next;
q->tail[team[data]]->next = qtmp;
q->tail[team[data]] = qtmp;
q->tail[0] = qtmp;
}
else
{
qtmp->next = q->tail[team[data]]->next;
q->tail[team[data]]->next = qtmp;
q->tail[team[data]] = qtmp;
}
used[team[data]]+=1;
}
}

int dequeue(StQueue *q)
{
int data;
Queue *tmp;
if(!empty(q))
{
tmp = q->next;
data = q->next->data;
if(used[team[data]]==1)
{
if(q->tail[0]->data == q->next->data)
q->tail[0] = q->tail[0]->next;
q->tail[used[team[data]]]=NULL;
q->next = q->next->next;
}
else
{
q->next = q->next->next;
}
free(tmp);
used[team[data]]-=1;
return data;
}
}

Posted: Thu Jan 04, 2007 1:59 pm
by Jan
Search your problem first. Dont open a new thread if there is one already.

Posted: Mon Apr 30, 2007 2:41 pm
by ayon
it seems there are DEQUEUE even when the queue is empty, what should i print then?

Posted: Mon Apr 30, 2007 3:11 pm
by helloneo
ayon wrote:it seems there are DEQUEUE even when the queue is empty, what should i print then?
Hmm.. I don't think so.. My AC program doesn't handle that case..

Posted: Fri Jul 27, 2007 8:42 pm
by Kallol
i am getting WA ...

can anyone give me some critical input against my code ??

Posted: Mon Jul 30, 2007 12:23 am
by wasi
An input which is not giving the correct output is:

Code: Select all

2
2 1 2
2 3 4
ENQUEUE 1
ENQUEUE 2
ENQUEUE 3
ENQUEUE 4
DEQUEUE
DEQUEUE
ENQUEUE 1
ENQUEUE 2
DEQUEUE
DEQUEUE
STOP
0


Your output:

Code: Select all

1
2
1
2

My output:

Code: Select all

Scenario #1
1
2
3
4

The reason is after enqueuing 1 2 3 4 , we deque twice and got 1 2 then we enqueue 1 2. This time the priority of this team (1 2) will be lower that that of (3 4). So at the time of dequeing 3 4 will come first.

Please prepend Scenario #n to the answer.

Posted: Mon Jul 30, 2007 6:38 pm
by Kallol
thanks wasi , i misunderstood the problem statement :oops:

Re: 540- Team Queue, RTE

Posted: Fri May 23, 2008 5:59 pm
by shakil
Why WA. Please help. Give some sample Input & Output.

Code: Select all

#include<stdio.h>
#include<string.h>

long flag[1000009];
long count[1009],dkdk[1009];
long m,t,hi;
long element[300009],value[300009];
long x,p,q,r,root;

long check(long h1,long h2)
{

if(flag[element[h1]]!=0&&flag[element[h2]]!=0)
{

if(dkdk[flag[element[h1]]]<dkdk[flag[element[h2]]])
return 1;
else if(dkdk[flag[element[h1]]]>dkdk[flag[element[h2]]])
return 0;
else
{

if(value[h1]<value[h2])
return 1;
else
return 0;

}
}
else
{

if(value[h1]<value[h2])
return 1;
else
return 0;

}


}




void en()
{
scanf("%ld",&x);
long ttt;     
if(hi==0)
{
element[hi]=x;
value[hi]=t;
if(flag[x]!=0)
{
dkdk[flag[x]]=m;
count[flag[x]]++;
m++;
}
t++;
hi++;         
} 
else
{
element[hi]=x;
value[hi]=t;
hi++;
t++;
if(count[flag[x]]==0 && flag[x]!=0)
{
dkdk[flag[x]]=m;
m++;    
}
if(flag[x]!=0)    
count[flag[x]]++;
p=hi-1;
while(p!=0)
{
q=p/2;           
ttt=check(q,p);
if(ttt==1)
break;
r=element[p];
element[p]=element[q];
element[q]=r;
r=value[p];
value[p]=value[q];
value[q]=r;
}
}    
}







void de()
{
	long t1,t2;
printf("%ld\n",element[0]);
if(flag[element[0]]!=0)     
count[flag[element[0]]]--;

element[0]=element[hi-1];
value[0]=value[hi-1];
hi--;

root=0;
while(1)
{
        if(root*2+1>=hi)
        break;
        else if(root*2+2>=hi)
		{
		
		t1=check(root,root*2+1);
		if(t1==1)
		break;
        r=element[root];
        element[root]=element[2*root+1];
        element[2*root+1]=r;
        r=value[root];
        value[root]=value[2*root+1];
        value[2*root+1]=r;    
        root=2*root+1;
		}
		else
		{
		t1=check(root*2+1,root*2+2);
		if(t1==1)
		{
		t2=check(root,root*2+1);
		if(t2==1)
		break;
        r=element[root];
        element[root]=element[2*root+1];
        element[2*root+1]=r;
        r=value[root];
        value[root]=value[2*root+1];
        value[2*root+1]=r;    
        root=2*root+1;
		}
		else
		{
		t2=check(root,root*2+2);
		if(t2==1)
		break;
		r=element[root];
        element[root]=element[2*root+2];
        element[2*root+2]=r;
        r=value[root];
        value[root]=value[2*root+2];
        value[2*root+2]=r;
        root=2*root+2;
		}
		}
         

		  
}     
}














int main()
{
    long n,i,j,hhhh=0;
    char temp[100];
while(1)    
    {
            
        scanf("%ld",&n);        
            if(n==0)
            break;
            hhhh++;
            printf("Scenario #%ld\n",hhhh);
            memset(flag,0,sizeof(flag));
            ///////memset(count,0,sizeof(count)); 
            for(i=1;i<=n;i++)
            {
            scanf("%ld",&m);
            for(j=0;j<m;j++)
            {
            scanf("%ld",&t);                
            flag[t]=i;                
            }                 
            count[i]=0;
            dkdk[i]=0;                 
            }
            m=1;
            t=1;
            hi=0;
            while(1)
            {
                    scanf("%s",temp);        
                    if(strcmp(temp,"STOP")==0)
                    break;
                    else if(strcmp(temp,"ENQUEUE")==0)
                    en();
                    else
                    de();
                    
            }
            
            printf("\n");
            
            
    }
    
    
    
return 0;    
}