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

Post by RuiFerreira » Sun Aug 22, 2004 12:27 am

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

Post by RuiFerreira » Tue Aug 24, 2004 4:41 pm

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

Post by serur » Tue Apr 25, 2006 11:27 am

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

Post by serur » Wed Apr 26, 2006 11:16 am

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

Post by rmotome » Wed Sep 27, 2006 12:11 am

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
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm
Location: Kitchener, Ontario, Canada

Post by rmotome » Wed Sep 27, 2006 5:57 am

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

Post by rmotome » Wed Sep 27, 2006 7:20 am

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
New poster
Posts: 4
Joined: Mon Dec 04, 2006 5:39 am
Contact:

540 RTE~ help

Post by scan33scan33 » Tue Jan 02, 2007 10:47 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jan 04, 2007 1:59 pm

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

Post by ayon » Mon Apr 30, 2007 2:41 pm

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

Post by helloneo » Mon Apr 30, 2007 3:11 pm

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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Fri Jul 27, 2007 8:42 pm

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
Bangladesh

wasi
New poster
Posts: 2
Joined: Mon Jul 30, 2007 12:10 am
Location: Dhaka, Bangladesh

Post by wasi » Mon Jul 30, 2007 12:23 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


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

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Mon Jul 30, 2007 6:38 pm

thanks wasi , i misunderstood the problem statement :oops:
Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

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

Re: 540- Team Queue, RTE

Post by shakil » Fri May 23, 2008 5:59 pm

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

Post Reply

Return to “Volume 5 (500-599)”