10147 - Highways

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

Moderator: Board moderators

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Sun Mar 12, 2006 1:18 am

Salamo Aleko
I got accepted in both problems with exactly the same code
May be some think wrong logically in your code.Check it or upload it
and i may help....But put in mind.10379 is more easier in the input
so you can get ac easily but 10147 has large inputs and hard to get within time.
I have implemented Kruskal's algorithm using union set (including union by rank and path compression!).

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

10147 Highways - MLE

Post by taskin » Tue Oct 17, 2006 9:21 am

this is saying MLE, which should not be. can anyone help me? here fx & fy r local & other 2 r global.

#define SIZE 751

struct Edge {
int u, v;
double w;
bool is_MST;
};

struct Node {
int size;
int father;
};

Node forest[SIZE];
Edge A[SIZE * SIZE];
double fx[SIZE],fy[SIZE];

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

TLE

Post by soddy » Sat Jun 30, 2007 9:24 pm

i m getting TLE for this problem...can nebody tell me how can i improve the efficiency
here is the code

Code: Select all

#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
using namespace std;
struct edges{
	int v1,v2;
	int w;
};	
struct point{
	int x,y;
};	
bool compare(const edges& e1,const edges& e2)
{
	return e1.w<e2.w;
}	
int find_set(int v,vector< set<int> >vset)
{
	for(int i=0;i<vset.size();i++)
	{
		set<int>::iterator p;
		p = vset[i].find(v);
		if(p != vset[i].end())
			return i;
	}
	return -1;
}	
int dist(int x1,int y1,int x2,int y2)
{
	int d,dx,dy;
	dx=x1-x2; dy=y1-y2;
	d=(dx*dx)+(dy*dy);
	return d;
}	
int main()
{
	int kases;
	cin>>kases;
	bool first=true;
	while(kases--)
	{
		if(!first)
			cout<<endl;
		first=false;	
		int n;
		cin>>n;
		vector< set<int> > vset(n);
		for(int i=0;i<n;i++)
		{
			set<int> s;
			s.insert(i);
			vset[i]=s;
		}	
		vector<edges> E;
		vector<point> P;
		edges e;
		point p;
		for(int i=0;i<n;i++)
		{
			cin>>p.x>>p.y;
			for(int j=0;j<P.size();j++)
			{
				int w=dist(P[j].x,P[j].y,p.x,p.y);
				e.v1=j; e.v2=i; e.w=w;
				E.push_back(e);
			}
			P.push_back(p);
		}
		sort(E.begin(),E.end(),&compare);
		//Already built highways
		int m,hw=0;
		cin>>m;
		for(int i=0;i<m;i++)
		{
			int x,y;
			cin>>x>>y;
			x--; y--;
			if(x!=y)
			{
				int mn=min(x,y),mx=max(x,y);
				vset[mn].insert(vset[mx].begin(),vset[mx].end());
				vset[mx].clear();
				hw++;
			}	
		}
		//New highways to be built
		bool newh=false;
		for(int i=0;i<E.size();i++)
		{
			int x=find_set(E[i].v1,vset);
			int y=find_set(E[i].v2,vset);
			if(x!=y)
			{
				newh=true;
				cout<<E[i].v1+1<<" "<<E[i].v2+1<<endl;
				int mn=min(x,y),mx=max(x,y);
				vset[mn].insert(vset[mx].begin(),vset[mx].end());
				vset[mx].clear();
				hw++;
			}	
			if(hw==n-1)
				break;
		}
		if(!newh)
			cout<<"No new highways need"<<endl;
	}
	return 0;
}	

before using sets, i tried vectors n still got TLE

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Sun Jul 01, 2007 1:49 pm

I'm not good at C++, so I can't understand your code well.
Could you give a brief explanation of your algorithm ?

Anyway, heres a test case which your code doesn't work.

Code: Select all

1

4
0 0
0 1
1 1
1 0
4
1 2
1 3
2 4
3 4
----
Rio

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Post by soddy » Sun Jul 01, 2007 9:52 pm

i can take care of ur case....actually i needed to chk dis at the beginning of the loop but i chked at the end

Code: Select all

if(hw>=n-1)
        break; 
I m implementing Kruskal algorithm....i implemented Kruskal in the same way for 908 and 10034 and got AC in 0.00 and 0.123 repectively.......maybe this code demands a lot more efficiency so i m getting TLE

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

m

Post by rio » Mon Jul 02, 2007 4:44 am

I don't feel Kruskal feasible for this problem, as you must to generate all n*(n+1)/2 edges.

In problem 908, edges in all given, so Kruskal is feasible for this (I also used Kruskal for this problem).
Though Problem 10034 is metric MST as this problem is , its upper limit is 100.

----
Rio

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Mon Jul 02, 2007 5:09 am

I got AC with Kruskal..
But it's so slow..
9.937 sec with qsort() library in C
and 3.064 sec with my own quick sort..

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Post by soddy » Tue Jul 03, 2007 9:08 am

i m using stl sort...still getting tle....is thr any other algorithm more efficient than kruskal for this problem???

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Jul 03, 2007 9:21 am

Prim. If you implement it carefully, time complexity will be O(n^2) using O(n) memory

----
Rio

SARKAR
New poster
Posts: 21
Joined: Tue May 22, 2007 4:18 pm

Post by SARKAR » Wed Jul 04, 2007 7:51 pm

i used kruskal.
finding all edges and sorting them is o(n^2log(n^2)) task



i used stl library for sorting
can this be done more effeciantely.

soddy
New poster
Posts: 23
Joined: Tue May 29, 2007 1:39 am

Post by soddy » Wed Jul 04, 2007 8:14 pm

helloneo wrote:I got AC with Kruskal..
But it's so slow..
9.937 sec with qsort() library in C
and 3.064 sec with my own quick sort..
i always thought stl is very efficient....can we code our own function three times efficient than stl ones???

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jul 05, 2007 4:55 am

soddy wrote: i always thought stl is very efficient....can we code our own function three times efficient than stl ones???
STL is slow even though it guarantees the time complexity..
If we make our code with the same time complexity, it will be much faster..

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Thu Jul 05, 2007 4:57 am

SARKAR wrote:i used kruskal.
finding all edges and sorting them is o(n^2log(n^2)) task



i used stl library for sorting
can this be done more effeciantely.
Try not to use STL.. like vector, set, sort
If you still get TLE, try Prim's algorithm like rio said.. :-)

ishtiaq ahmed
Learning poster
Posts: 53
Joined: Sat Jul 29, 2006 7:33 am
Location: (CSE,DU), Dhaka,Bangladesh

Re: 10147 unclear output format

Post by ishtiaq ahmed » Thu May 01, 2008 7:27 pm

I have a problem with the output format. According to the sample inputs the outputs are given such like this
output

Code: Select all

1 6
3 7
4 9
5 7
8 3
Now my question is it correct format just bellow i am indicating?
output

Code: Select all

1 6
3 7
4 9
5 7
3 8
Yes i am trying to say that is it acceptable if the pair format swap just like 3 8 instead of 8 3?
No venture no gain

with best regards
------------------------
ishtiaq ahmed

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

Re: 10147 unclear output format

Post by sohel » Fri May 02, 2008 9:27 am

This problem has a special judge - that means there are multiple outputs and any correct one will be accepted.
The output format isn't mentioned in the problem statement and thus you are free to choose your own way.
{8 3} and {3 8} are equivalent.

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: Bing [Bot] and 1 guest