11749 - Poor Trade Advisor

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

Moderator: Board moderators

Post Reply
jakir.duet
New poster
Posts: 4
Joined: Sat Nov 20, 2010 10:27 pm

11749 - Poor Trade Advisor

Post by jakir.duet »

Can anybody explain this problem? I didn't understand at all what it wanted.
Programming is a challenge........so as life.

t2faz
New poster
Posts: 2
Joined: Sun Dec 19, 2010 2:19 pm

Re: 11749 : Didn't understand

Post by t2faz »

it's a simple DFS problem.... :D
but you have to suffer if u don't initialize the graph by a big negative number.
coz PPA may be negative. :wink:

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 11749 : Didn't understand

Post by Shafaet_du »

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11749 : Didn't understand

Post by brianfry713 »

I believe there is a case like this in the input. With a repeat road, be sure to store the maximum.

Code: Select all

3 3
2 1 0
2 1 -1
1 3 0
0 0
AC Output:
3
Check input and AC output for thousands of problems on uDebug!

magurmach
New poster
Posts: 26
Joined: Mon May 14, 2012 8:19 pm

Re: 11749 : Didn't understand

Post by magurmach »

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

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11749 : Didn't understand

Post by Scarecrow »

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.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11749 : Didn't understand

Post by Scarecrow »

can't anyone help? :(
Do or do not. There is no try.

remerson
New poster
Posts: 4
Joined: Sun Jun 05, 2011 6:32 pm

Re: 11749 : Didn't understand

Post by remerson »

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! :D

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11749 : Didn't understand

Post by Scarecrow »

Thanks remerson! Got AC using Union-Find Disjoint Sets :) And the fault in the DFS solution was initializing ppamax by -2147483647.
Do or do not. There is no try.

dipdeb
New poster
Posts: 1
Joined: Thu Jun 05, 2014 8:23 am

uva 11749 why wa????

Post by dipdeb »

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

}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: uva 11749 why wa????

Post by brianfry713 »

Change line 22 to:
max_ppa = -2147483648;
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”