11503 - Virtual Friends
Moderator: Board moderators
11503 - Virtual Friends
i use union find algo and get tle.give any idea how to optimize time.
An offer u can not refuse.
-
- 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 ?
Re: 11503-Virtual Friends
i also use c++.
here is my code
i use len[] to get total connected components of the parents every vertex.
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;
}
An offer u can not refuse.
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)
{
link(find_set(x), find_set(y));
}
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));
}
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.....
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.....
Re: 11503-Virtual Friends
ACC now!! I used map and got accepted. Thank you!!
-
- Learning poster
- Posts: 58
- Joined: Wed Dec 31, 2003 8:43 am
- Location: Dhaka, Bangladesh
- Contact:
Re: 11503-Virtual Friends
visit http://www.youngprogrammer.com compare your solution and fix bugs.sabir wrote:i use union find algo and get tle.give any idea how to optimize time.
http://www.the-sports.co
Sports Stories
Sports Stories
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:
![:(](./images/smilies/icon_frown.gif)
Code: Select all
AC. . .
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![:-?](./images/smilies/icon_confused.gif)
![:D](./images/smilies/icon_biggrin.gif)
![:oops:](./images/smilies/icon_redface.gif)
![:lol:](./images/smilies/icon_lol.gif)
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
![:-?](./images/smilies/icon_confused.gif)
-
- 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
{
//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;
}
}
![:oops:](./images/smilies/icon_redface.gif)
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.......
Re: 11503-Virtual Friends
Try
Code: Select all
1
5
A B
B C
D E
A D
A C
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?
I'm having the same problem with Problem 11504...
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;
}
}
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?
![:oops:](./images/smilies/icon_redface.gif)
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.
This may be the address of success.
-
- 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
output
but ur code gives
hope it will help out.
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
Code: Select all
2
3
2
5
5
Code: Select all
2
3
5
5
5
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
It is more tough to become a good person.
I am trying both...............................
-
- 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
thanks in adnance
I use union-find and map
thanks in adnance
Impossible says I`m possible