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

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

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

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

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

}

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

long i,t,ans,x,y;
char name1,name2;

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

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)
{
}

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

Re: 11503-Virtual Friends

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

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

Re: 11503-Virtual Friends

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

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

I found my silly mistake   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

Hi... I Am New At Acm.. I Did Try Virtual Friends Using Map In Java.. But I Get WA 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
{
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

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

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
{

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;
s = new int; //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

Re: 11503 - Virtual Friends

Hi every one i went for a funny method & don't know if it works or not. 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.

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

Re: 11503 - Virtual Friends

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

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

Re: 11503 - Virtual Friends

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