## 540 - Team Queue

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

Moderator: Board moderators

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### 540 - Team Queue

hi!

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

does any one have larger or tricky inputs?
Please visit my webpage!! I've got a lot of UVA statistics scripts
http://www.fe.up.pt/~ei01081/scripts/

RuiFerreira
New poster
Posts: 23
Joined: Mon Dec 16, 2002 8:01 pm
Location: Portugal
Contact:

### Code

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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### 540- Team Queue, RTE

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 *TailPtr;
int NumItems;
}QUEUE;

NODE *TeamTailPtr[M];

{
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)
{
TeamTailPtr[t]=Q->TailPtr->Next;
if(!Q->NumItems)
}
else
{
if(TeamTailPtr[t]!=NULL)
TeamTailPtr[t]=TeamTailPtr[t]->Next;
}
++Q->NumItems;
}
deQueue(QUEUE *Q,int *fellow)
{
--Q->NumItems;
if(!Q->NumItems)
Q->TailPtr=NULL;
}
QUEUE *create(){
QUEUE *Q=malloc(sizeof *Q);
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
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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?
Last edited by serur on Sat Apr 14, 2012 3:33 pm, edited 1 time in total.

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

### 540 Attack!!!!!

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 x = malloc(sizeof *x);
x->n = n;
x->team = team;
x->prev = prev;
x->next = next;
return x;
}
typedef struct{
}Queue;
void init(Queue* Q)
{
Q->tail = malloc(sizeof *Q->tail);
Q->tail->next = Q->tail;
}
{return Q->tail;}
void insert(Queue* Q,link t)
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
}
{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)
for(x=end(Q)->prev; x!=Q->head; x = x->prev)
if(x->team == t->team)break;
x = end(Q)->prev;
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
}
main()
{
Queue Q1,Q2;
int n,p,q,r;
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
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada
ANS: keep an updated link to the last element of each group thus reducing ENQUEUE to O(1)

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada
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 x = malloc(sizeof *x);
x->n = n;
x->team = team;
x->prev = prev;
x->next = next;
return x;
}
typedef struct{
int N;
}Queue;
int team[Z+1];
void init(Queue* Q)
{
Q->tail = malloc(sizeof *Q->tail);
Q->tail->next = Q->tail;
Q->N=0;
}
{return Q->tail;}
{
t->next = x->next;
x->next->prev = t;
x->next = t;
t->prev = x;
Q->N++;
}
{
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;
int n,p,q,r;
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
New poster
Posts: 4
Joined: Mon Dec 04, 2006 5:39 am
Contact:

### 540 RTE~ help

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;

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)
{
pf_all+=1;
}
else if(strcmp("STOP",order)==0)
break;
}
printf("Scenario #%d\n",ti);
for(i=0;i<pf_all;i++)
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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Search your problem first. Dont open a new thread if there is one already.
Ami ekhono shopno dekhi...
HomePage

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh
it seems there are DEQUEUE even when the queue is empty, what should i print then?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea
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..

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
i am getting WA ...

can anyone give me some critical input against my code ??
Last edited by Kallol on Mon Jul 30, 2007 6:39 pm, edited 1 time in total.
Syed Ishtiaque Ahmed Kallol
CSE,BUET

wasi
New poster
Posts: 2
Joined: Mon Jul 30, 2007 12:10 am
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
``````

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.
Mir Wasi Ahmed

Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am
thanks wasi , i misunderstood the problem statement
Syed Ishtiaque Ahmed Kallol
CSE,BUET

shakil
Learning poster
Posts: 74
Joined: Sat Jul 15, 2006 6:28 am
Location: CUET , bangladesh
Contact:

### Re: 540- Team Queue, RTE

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

``````
SHAKIL