11503 - Virtual Friends

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

Moderator: Board moderators

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

11503 - Virtual Friends

Post by sabir » Tue Oct 07, 2008 8:23 pm

i use union find algo and get tle.give any idea how to optimize time.
An offer u can not refuse.

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

Re: 11503-Virtual Friends

Post by jan_holmes » Tue Oct 07, 2008 8:55 pm

I was using the same algorithm (union-find) in C++ and it was run under 1.6 secs. Anyway, in what language do you write your code ?

sabir
New poster
Posts: 13
Joined: Thu Jun 14, 2007 8:48 am

Re: 11503-Virtual Friends

Post by sabir » Tue Oct 07, 2008 10:25 pm

i also use c++.
here is my code

Code: Select all

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define sz 1000010

long vertex[sz],rank[sz],len[sz];
long edge,top;

typedef struct
{
	char name[25];
}name_info;

name_info data[sz];

long Find_set(long num)
{
	if(num!=vertex[num])
	{
		vertex[num]=Find_set(vertex[num]);
	}

	return vertex[num];
}

long Link(long x,long y,long a,long b)
{
	long t1,t2;

	if(rank[x]>rank[y])
	{
		t1=len[x];
		t2=len[y];

		len[x]=len[y]=t1+t2;

		vertex[x]=vertex[y];
	}
	else
	{
		t1=len[x];
		t2=len[y];

		len[x]=len[y]=t2+t1;	

		vertex[y]=x;

		if(rank[x]==rank[y])
		{
			rank[y]++;
		}
	}

	return t1+t2;
}


long UNION(long x,long y)
{
	return Link(Find_set(x),Find_set(y),x,y);
}

int check(char str[])
{
	long i,y;

	for(i=1;i<=top;i++)
	{
		y=strcmp(data[i].name,str);
		if(y==0)
		{
			return i;
		}
	}

	top++;
	
	len[top]=1;
	rank[top]=0;
	vertex[top]=top;
	
	strcpy(data[top].name,str);

	return top;
}

int main()
{
	//freopen("11503in.txt","r", stdin);
	//freopen("11503out.txt","w", stdout);

	long i,t,ans,x,y;
	char name1[25],name2[25];

	scanf("%ld", &t);

	while(t--)
	{
		scanf("%ld", &edge);
		top=0;
		for(i=1;i<=edge;i++)
		{
			scanf(" %s %s", name1,name2);
			
			x=check(name1);
			y=check(name2);

			if(Find_set(x)!=Find_set(y))
			{
				ans=UNION(x,y);
			}

			printf("%ld\n",ans);
		}
	}

	return 0;
}
i use len[] to get total connected components of the parents every vertex.
An offer u can not refuse.

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Re: 11503-Virtual Friends

Post by el cheeto » Wed Oct 08, 2008 1:05 am

Hi, I am also using Union-Find algorithm, but also getting TLE, any help would be great. Thank you.

My union-find algorithm is the following:

void make_set(int x)
{
p[x] = x;
rank[x] = 0;
}

void link(int x, int y)
{
if (rank[x] > rank[y])
p[y] = x;
else
{
p[x] = y;
if (rank[x] == rank[y])
rank[y] = rank[y] + 1;
}
}

int find_set(int x)
{
if (x != p[x])
p[x] = find_set(p[x]);
return p[x];
}

void union_set(int x, int y)
{
link(find_set(x), find_set(y));
}

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11503-Virtual Friends

Post by mmonish » Wed Oct 08, 2008 3:23 am

>>sabir
my algorithm is same as ur's. I think u should use efficient data structure for ur check() function. in worst case ur complexity is O(n^2) where n = 100000. For this i use stl map. Hope this helps u.....

el cheeto
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Re: 11503-Virtual Friends

Post by el cheeto » Wed Oct 08, 2008 4:09 am

ACC now!! I used map and got accepted. Thank you!!

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Re: 11503-Virtual Friends

Post by L I M O N » Sun Nov 02, 2008 8:12 pm

sabir wrote:i use union find algo and get tle.give any idea how to optimize time.
visit http://www.youngprogrammer.com compare your solution and fix bugs.

azk84
New poster
Posts: 14
Joined: Sat Sep 13, 2008 7:50 pm
Location: Tehran
Contact:

Re: 11503-Virtual Friends

Post by azk84 » Thu Nov 06, 2008 7:52 am

I'm getting TLE and I have no idea how to improve my running time! Plz help me :( . Here is my code:

Code: Select all

AC. . .

azk84
New poster
Posts: 14
Joined: Sat Sep 13, 2008 7:50 pm
Location: Tehran
Contact:

Re: 11503-Virtual Friends

Post by azk84 » Thu Nov 06, 2008 6:46 pm

I found my silly mistake :D :oops: :lol:
I used union-find algo with stl map, and my running time is 5.
How can I improve this running time? In ranking list exist running times under 0.5 seconds :-?

StraightForward
New poster
Posts: 1
Joined: Fri Mar 21, 2008 6:33 pm

Re: 11503-Virtual Friends

Post by StraightForward » Tue Nov 25, 2008 6:04 pm

Hi... I Am New At Acm.. I Did Try Virtual Friends Using Map In Java.. But I Get WA :oops: here is my Code...

Thanks BeforeHand.... Christian Ortiz Venezuela...
import java.io.*;
import java.util.*;
import java.math.*;
public class Main
{
static Hashtable<String,Integer> Map;
public static void main(String[] args) throws Exception
{
//BufferedReader In = new BufferedReader(new InputStreamReader(System.in));
BufferedReader In = new BufferedReader(new FileReader(new File("In.in")));
PrintWriter Out = new PrintWriter(System.out);
Integer MAX = new Integer(In.readLine().trim());
for(Integer I=1;I.compareTo(MAX)<=0;I++)
{
Integer Max = new Integer(In.readLine().trim());
Map = new Hashtable<String,Integer>();
Integer Count = new Integer(0);
for(Integer D=1;D.compareTo(Max)<=0;D++)
{
StringTokenizer x = new StringTokenizer(In.readLine());
String X = new String(x.nextToken());
String Y = new String(x.nextToken());
if (Map.containsKey(X) && !Map.containsKey(Y)) //One Friend... New..
{
++Count;
Map.put(new String(Y),0);
}
if (!Map.containsKey(X) && Map.containsKey(Y)) //Other Friend New...
{
++Count;
Map.put(new String(X),0);
}

if (!Map.containsKey(X) && !Map.containsKey(Y) && D.equals(1)) //Two New Friends...
{
Count+= 2;
Map.put(new String(X),0);
Map.put(new String(Y),0);
}
Out.println(Count);
}
}
Out.flush();
return;
}
}
Rocking In A Free World.......

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 11503-Virtual Friends

Post by roticv » Fri Dec 05, 2008 5:39 am

Try

Code: Select all

1
5
A B
B C
D E
A D
A C

wjomlex
New poster
Posts: 13
Joined: Fri Dec 19, 2008 1:56 am

Re: 11503 - Virtual Friends

Post by wjomlex » Tue Jan 27, 2009 8:49 pm

I'm getting RE, and I don't see why. My arrays are much larger than necessary, and I can't find any infinite loops or anything. Is the input formatting different from what the problem says? Can things be split across lines?

Code: Select all

//UVa Problem 11503 - Virtual Friends
//Wesley May - Jan 27 2009 (RE... Array indexes should be fine... maybe HashMap?)

import java.util.*;
import java.io.*;

public class Main
{
	static int[] p, s;

	public static void main(String args[]) throws IOException
	{
		
		BufferedReader scan = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		int t = Integer.parseInt(scan.readLine());

		for(int ca=0;ca < t;ca++)
		{
			int n = Integer.parseInt(scan.readLine());

			p = new int[1000000];
			s = new int[1000000]; //size of set with leader i

			for(int i=0;i < p.length;i++)
			{
				p[i] = i;
				s[i] = 1;
			}

			HashMap h = new HashMap();
			int count = 0;

			for(int i=0;i < n;i++)
			{
				StringTokenizer st = new StringTokenizer(scan.readLine());

				String a = st.nextToken();
				String b = st.nextToken();
				int ia,ib;

				Object o = h.get(a);
				if(o == null)
				{
					ia = count++;
					h.put(a,ia);
				}
				else
					ia = (Integer)o;

				o = h.get(b);
				if(o == null)
				{
					ib = count++;
					h.put(b,ib);
				}
				else
					ib = (Integer)o;

				if(find(ia) == find(ib))
					sb.append(s[find(ia)]).append("\n");
				else
				{
					s[find(ib)] = s[find(ia)] + s[find(ib)];
					union(ia, ib);
					sb.append(s[find(ia)]).append("\n");
				}
			}
		}

		System.out.print(sb);
	}

	public static int find(int i)
	{
		if(p[i] == p[p[i]])
			return p[i];

		p[i] = find(p[i]);
		return p[i];
	}

	public static void union(int i, int j)
	{
		int ri = find(i);
		int rj = find(j);

		p[ri] = rj;
	}
}
I'm having the same problem with Problem 11504...

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 11503 - Virtual Friends

Post by Obaida » Tue Feb 17, 2009 7:16 am

Hi every one i went for a funny method & don't know if it works or not. :oops:
This time seems not working cause i got WA. But is there any mistake in my algo?

Code: Select all

removed
Last edited by Obaida on Sat Feb 28, 2009 9:20 am, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 11503 - Virtual Friends

Post by kbr_iut » Fri Feb 27, 2009 2:51 am

This problem is solvable with union-find algorithm.
I didnt see ur code.
but ur code fails to give correct answer for the input posted by "roticv "
input

Code: Select all

1

5
A B
B C
D E
A D
A C
output

Code: Select all

2
3
2
5
5
but ur code gives

Code: Select all

2
3
5
5
5
hope it will help out.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

User avatar
vahid sanei
Learning poster
Posts: 84
Joined: Fri Jan 09, 2009 4:37 pm
Location: IRAN

Re: 11503 - Virtual Friends

Post by vahid sanei » Tue Mar 03, 2009 1:51 pm

I got Acc in 2.920 sec , how can i reduce time of my algo ?
I use union-find and map




thanks in adnance
Impossible says I`m possible

Post Reply

Return to “Volume 115 (11500-11599)”