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 »

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 »

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 »

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.

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

there is a easier way..

Post by sohel »

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 »

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

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

Post by sohel »

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 »

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 »

: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 »

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

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

Post by Sedefcho »

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 »

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 »

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 »

nobody know ? :o

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

Post by salamander »

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 »

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)”