540 - Team Queue

[RuiFerreira]

hi!

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

does any one have larger or tricky inputs?

[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

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

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

[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");
}
}

[rmotome]

ANS: keep an updated link to the last element of each group thus reducing ENQUEUE to O(1)

[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");
}
}

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

[Jan]

Search your problem first. Dont open a new thread if there is one already.

[ayon]

it seems there are DEQUEUE even when the queue is empty, what should i print then?

[helloneo]

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

[Kallol]

i am getting WA ...

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

[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.

[Kallol]

thanks wasi , i misunderstood the problem statement

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