11749  Poor Trade Advisor
Moderator: Board moderators

 New poster
 Posts: 4
 Joined: Sat Nov 20, 2010 10:27 pm
11749  Poor Trade Advisor
Can anybody explain this problem? I didn't understand at all what it wanted.
Programming is a challenge........so as life.
Re: 11749 : Didn't understand
it's a simple DFS problem....
but you have to suffer if u don't initialize the graph by a big negative number.
coz PPA may be negative.
but you have to suffer if u don't initialize the graph by a big negative number.
coz PPA may be negative.

 Experienced poster
 Posts: 147
 Joined: Mon Jun 07, 2010 11:43 am
 Location: University Of Dhaka,Bangladesh
 Contact:
Re: 11749 : Didn't understand
The description is not good though its a nice problem. You need to find the largest connected component with highest average PPA in this problem. And you will get the highest average only if you take the max weight edges .
UVa stats: http://felixhalim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 11749 : Didn't understand
I believe there is a case like this in the input. With a repeat road, be sure to store the maximum.
AC Output:
3
Code: Select all
3 3
2 1 0
2 1 1
1 3 0
0 0
3
Check input and AC output for thousands of problems on uDebug!
Re: 11749 : Didn't understand
A very disgusting problem with this one is... we have to initialize the adjacency matrix with Minimal number (better 2147483647) at first I initialized with 999999999 got WA... changed total code still WA and then just changed the limit and got AC and in exchange of 8 WA I got 2nd rank!!!
Re: 11749 : Didn't understand
can't find why getting WA. please someone help me find the case where the code fails
Code: Select all
AC
Last edited by Scarecrow on Tue Apr 09, 2013 10:45 pm, edited 1 time in total.
Do or do not. There is no try.
Re: 11749 : Didn't understand
You don't need to initialise the PPA value with an arbitrary negative value because the problem states clearly that M > 0 so there will always be an initial edge to initialise from.
It is a nice problem but the description is not the easiest to follow and bit confusing. The term "average" is very misleading. Ignore all roads which do not have maximal PPA.
Bear in mind also that there can be more than 1 connected component containing the same number of cities with maximal PPA. The second example input case shows this i.e. more than 1 province but all with equal cardinality. Draw it out to see (I did and it was helpful).
It is possible also to solve this with disjoint sets union/find.
I think the judge input tests the full range of M i.e. up to 1M edges which is quite a large input.
I can post some test input cases if anyone is still stuck or otherwise it is available on UVA Toolkit for you to check arbitrary test cases.
As Brian says, there are definitely cases of repeated roads. You can infer this from the problem description because M <= 1M but N is only <= 500 and a complete graph with 500 nodes only has 125250 edges (I think!) which is << 1M, so there must be repeated roads.
Be sure to test edge cases like maximal PPA is negative and complete/disconnected PPA graphs etc.
For added realism, you can also run your laptop on battery just like the problem says and see if you can complete it in time!
It is a nice problem but the description is not the easiest to follow and bit confusing. The term "average" is very misleading. Ignore all roads which do not have maximal PPA.
Bear in mind also that there can be more than 1 connected component containing the same number of cities with maximal PPA. The second example input case shows this i.e. more than 1 province but all with equal cardinality. Draw it out to see (I did and it was helpful).
It is possible also to solve this with disjoint sets union/find.
I think the judge input tests the full range of M i.e. up to 1M edges which is quite a large input.
I can post some test input cases if anyone is still stuck or otherwise it is available on UVA Toolkit for you to check arbitrary test cases.
As Brian says, there are definitely cases of repeated roads. You can infer this from the problem description because M <= 1M but N is only <= 500 and a complete graph with 500 nodes only has 125250 edges (I think!) which is << 1M, so there must be repeated roads.
Be sure to test edge cases like maximal PPA is negative and complete/disconnected PPA graphs etc.
For added realism, you can also run your laptop on battery just like the problem says and see if you can complete it in time!
Re: 11749 : Didn't understand
Thanks remerson! Got AC using UnionFind Disjoint Sets And the fault in the DFS solution was initializing ppamax by 2147483647.
Do or do not. There is no try.
uva 11749 why wa????
Code: Select all
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int ar[1000005],br[1000005],cr[1000005],graph[505][505];
int visited[505],n,m,temp;
void dfs(int i){
for(int j=1;j<=n;j++){
if(graph[i][j]&&!visited[j]){
visited[j]=1;
temp++;
dfs(j);
}
}
}
int main(){
int i,j,max_ppa,cities;
while(scanf("%d %d",&n,&m)!=EOF){
if(n==0&&m==0)break;
max_ppa=1;
for( i=1;i<=m;i++){
scanf("%d %d %d",&ar[i],&br[i],&cr[i]);
max_ppa=max(max_ppa,cr[i]);
}
memset(graph,0,sizeof(graph));
memset(visited,0,sizeof(visited));
for( i=1;i<=m;i++){
if(max_ppa==cr[i]){
graph[ar[i]][br[i]]=graph[br[i]][ar[i]]=1;
}
}
cities=1;
for( i=1;i<=n;i++){
if(!visited[i]){
temp=1;
visited[i]=1;
dfs(i);
cities=max(cities,temp);
}
}
printf("%d\n",cities);
}
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: uva 11749 why wa????
Change line 22 to:
max_ppa = 2147483648;
max_ppa = 2147483648;
Check input and AC output for thousands of problems on uDebug!