10608 - Friends

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

Moderator: Board moderators

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

10608 : why this code gives T.L.E

Post by harry » Fri Sep 17, 2004 8:36 pm

Using this algo i got A.C for 459 , 793 ,10227 . But why TLE for 10608
Can anyone help?
thanks in advance.
Last edited by harry on Fri Sep 17, 2004 9:45 pm, edited 1 time in total.

udvat
New poster
Posts: 29
Joined: Thu Aug 07, 2003 9:56 pm

10608

Post by udvat » Fri Sep 17, 2004 9:32 pm

dont use

while(scanf("%d",&test)==1)
{
while(test)
{
test--;
}
}

instead use

scanf("%d",&test);

while(test)
{
test--;
}

but thus u can escape from tle,but still your code holds a bug and getting WA.check it out.

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

10608 W.A. [Why?] HELP!!!

Post by Ali Arman Tamal » Sat Jan 15, 2005 5:16 pm

I'm getting W.A. :( Don't Know why .

I tested the program with a lot of inputs, and the answers were correct.

I will really appreciate some test cases... :roll:

I'm also posting my code:


// CUT



THANK YOU VERY MUCH !!! :-?
Last edited by Ali Arman Tamal on Mon Jan 31, 2005 3:34 pm, edited 2 times in total.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

there is a easier way..

Post by sohel » Mon Jan 17, 2005 4:24 pm

It seems that you are using sets to divide the members into groups..
And the implementation of that is a little complicated and thus error prone.

.. but you can easily solve this problem using bfs/dfs. :)
Last edited by sohel on Wed Jan 19, 2005 3:01 pm, edited 1 time in total.

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

10608

Post by Ali Arman Tamal » Mon Jan 17, 2005 7:29 pm

Thanks for your help Sohel. :)

But the problem is how should I represent the graph while using BFS of DFS.

Both the adjacency matrix and adjacency list representation may lead to a 30000*30000 :o memory requirements as there are 30000 vertexes (30000 people);

Thats why I used this method.

Give me a hint :(

PS: If anybody has solved this code, Please give me some TEST CASES.

THANK YOU VERY MUCH !!!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Tue Jan 18, 2005 8:33 am

tomal wrote: Both the adjacency matrix and adjacency list representation may lead to a 30000*30000 memory requirements as there are 30000 vertexes (30000 people);
Using Adjacency matrix will certainly get MLE/TLE, but the usage of adjacency list will suffice. There might be 30000 different vertices but there wont be cases where you have to handle 30000*30000 memory.

Remember there can be at most 500000 different pairs and that is not a lot.

You can use STL Vector to represent the matrix.. ( if you don't already know it) and then run a dfs.

Hope this will help you in some way. :)

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Tue Jan 18, 2005 9:56 pm

Code: Select all

for(k=1;k<=n;k++)if(a[k]==a[j])a[k]=a[i];
this line is wrong. you should use a temporary variable for the value of a[j], since with this loop you are changing a[j] to a, so if there are values a[k] == a[j] with k>j, you will forget to set them to the new value a.
Btw, why didn't you use the union find data structure? It is much faster.

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

Got AC

Post by Ali Arman Tamal » Thu Jan 20, 2005 6:09 am

:D I got Acc.

Thank you Adrian Kuegel, I was so blind :oops: !!!

liang1425
New poster
Posts: 5
Joined: Thu May 26, 2005 8:20 am

10608WA

Post by liang1425 » Thu May 26, 2005 8:29 am

I've tried many datas,and it's correct......But I got W.A. >"<
Please help me!!Thanks a lot!!

Code: Select all

/*Q10608: Friends*/
/*2005.5.25   W.A.*/
#include<stdio.h>

int main()
{
    int i,j,n,a,b,c[30001],x,y,num,t[30001],max;
    
    scanf("%d",&n);
    while(n--){
        for(i=0;i<30001;i++){ c[i]=0; t[i]=0; }
        scanf("%d %d",&a,&b);
        num=0;
        while(b--){
           scanf("%d %d",&x,&y);
           if(c[x]){ 
               if(!c[y]){c[y]=c[x]; t[c[x]]++;}
               else if(c[x]!=c[y]){
                   t[c[x]]+=t[c[y]];
                   for(j=1;j<=a;j++)
                     if(c[j]==c[y]) c[j]=c[x];
               }
           }
           else{
              if(c[y]){ 
                  if(!c[x]){c[x]=c[y]; t[c[y]]++;}
                  else if(c[x]!=c[y]){
                      t[c[y]]+=t[c[x]]; 
                      for(j=1;j<=a;j++)
                          if(c[j]==c[x]) c[j]=c[y];
                  }
              }
              else{
                 num++;
                 c[x]=c[y]=num; t[num]=2;
              }
           }
        }
        max=0;
        for(i=1;i<=num;i++)
            if(t[i]>max) max=t[i];
        printf("%d\n",max);
    }

    return 0;
}

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Wed Jun 01, 2005 3:36 pm

Hi, liang1425 !

I've sent you a private message with your fixed code.

It will get ACC :) if you submit it.

Regards !

liang1425
New poster
Posts: 5
Joined: Thu May 26, 2005 8:20 am

Post by liang1425 » Sat Jun 04, 2005 7:14 pm

Dear Sedefcho~
Thank you very much:)
I've known where my code was wrong.
Thank you.

salamander
New poster
Posts: 9
Joined: Fri Jan 21, 2005 6:46 pm

10608 WA Why???

Post by salamander » Thu Jun 16, 2005 10:20 am

I'm getting W.A. Don't Know why .

I post the code

Code: Select all

#include <cstdio>
#include <cstdlib>

int parent[30001];
int count[30001];

int main() {
    int t, m, n, a, b, Max;

    scanf("%d\n", &t);

    for (int i=0;i<t;i++) {
        scanf("%d %d\n", &m, &n);

        for (int j=1;j<=m;j++) {
            parent[j] = j;
            count[j] = 0;
        }

        for (int j=0;j<n;j++) {
            scanf("%d %d\n", &a, &b);

            while (parent[a] != a) {
                a = parent[a];
            }
            
            while (parent[b] != b) {
                b = parent[b];
            }

            if (a<b) {
                parent[b] = a;
            }
            else {
                parent[a] = b;
            }
        }

        for (int j=1;j<=m;j++) {
            count[parent[j]]++;
        }
        
        /*for (int j=1;j<=m;j++) {
			printf("%d ", count[j]);
		}
        putchar('\n');*/
        
        Max = 0;
       
        for (int j=1;j<=m;j++) {
            if (count[j] > Max) {
                Max = count[j];
            }
	    }

        printf("%d\n", Max);
    }
}

salamander
New poster
Posts: 9
Joined: Fri Jan 21, 2005 6:46 pm

Post by salamander » Sat Jun 18, 2005 5:31 am

nobody know ? :o

salamander
New poster
Posts: 9
Joined: Fri Jan 21, 2005 6:46 pm

Post by salamander » Tue Jun 28, 2005 12:44 am

Anyone know what wrong in my code???

jdmetz
New poster
Posts: 25
Joined: Fri May 27, 2005 5:23 pm
Location: Ann Arbor, MI USA

what is wrong with your code

Post by jdmetz » Tue Jul 19, 2005 7:52 pm

You need to move all of b's friends to a's group or the other way, not just b or a:

Input:

Code: Select all

1
10 5
1 2
2 3
4 5
5 7
3 4
Output:

Code: Select all

6

Post Reply

Return to “Volume 106 (10600-10699)”