Page 1 of 3

10459 - The Tree Root

Posted: Wed Feb 26, 2003 12:06 am
by zsepi
I believe it's more of a C language problem than algorithm, but if you've done this problem, you might be able to help me.

http://acm.uva.es/board/viewtopic.php?t=2415&highlight=

thanx

Posted: Mon Mar 24, 2003 5:47 am
by Red Scorpion
Can anyone help me.
I got WA many time.

Here is my code: Please help...help.... :cry: :cry: :cry:
Thanks,
RS

Posted: Tue Mar 25, 2003 1:35 am
by ditrix
I have the same problem.
I didn't understand your code clearly, so I explain my algo:

1. Do DFS from vertex 0 and add to the list of worst roots each vertex maximizing a distance from 0
2. With each vertex N from the list of worst roots do DFS from it and add to the list of worst roots each vertex maximizing a distance from N.
3. Take a paire of vertex, one (N1) which was found on the step 2 and other (N2) which was found by DFS from N1 on the step 2. Take a middle-point (or 2 points) of the path N1-->N2 and add it to the list of the best roots.

Posted: Tue Mar 25, 2003 3:47 am
by Red Scorpion
My algo just do this:
1. Delete all the node that have only one parrents and add it to the worst.
2. After that search again the node that only have one parrents, and del it.
3. And so on .. until that remain one / two roots. (Best roots).

Example :

Code: Select all

                 6
               /    \
             5       8
          /   \       \
         4     3      7 

1. del the node 4, 3, 7 and make it the worst roots.(worst roots -> 4,3,7)
2.                6
               /    \
             5       8
    del the node 5, 8.
3.               6
     And 6 is the best roots.
I wonder is my algo correct ? I solve this problem without using DFS.
If someone have time please give me the tricky input.

Best Thanks, :lol: :lol:
Red Scorpion

Posted: Tue Mar 25, 2003 1:44 pm
by ditrix

Code: Select all

                     1
                    / \
                  2     3
                 / \   / \
                4   5 6   7
               / \
             8    9
For this exemple the right answer is:
best: 1 2
worst: 6 7 8 9

And your algo should add 5 as worst root.

Posted: Wed Mar 26, 2003 3:52 am
by Red Scorpion
....

Posted: Thu Mar 27, 2003 5:27 am
by Red Scorpion
heemmm. :-? ,
Yes my algo is wrong for the worst roots, Now I tried to find the worst roots with DFS, but got TLE.

Ditrix, can you tell me how I can get the worst trees(please tell me in simple words).
Thanks Ditrix for pointing out my wrong algo.
:oops:
Huge Thanks,
RS.

Posted: Fri Mar 28, 2003 12:03 pm
by makbet
Here's how I do it:
Run dfs from the best root
toggle all the leaves with maximum distance as worst. Now run dfs from one of those leaves, and again toggle all leaves with maximum distance as worst. I hope you understand. I will demonstrate it:

Code: Select all

  1
 / | \
2 3 4
|    \
5     6
     / \
    8   7
1 is one of the best roots here.
After first dfs, 5 has height 2, 3 has 1, 7 & 8 have 3. So 7 & 8 are worst roots. Now we run dfs from 7.
Now 8 has height 2, 3 has 4 and 5 has 5. So 5 is also a worst root.
Worst roots are now 5, 7 and 8. Notice that 3 is not a worst root, although it is a leaf.
I don't know if this is correct, accepted doesn't always mean correct :wink:

Posted: Tue Apr 01, 2003 9:29 am
by Red Scorpion
Hi!
I have changed my algorithms to this:
1. Find the best roots used the above methods (1/2 best roots).
2. Find The worst roots : -> find the longest path from all of the best roots.

Code: Select all

Example :
                     1
                    / \
                  2     3
                 / \   / \
                4   5 6   7
               / \
             8    9 

Best Roots : 1,2
Worst roots from node 1 : 8, 9
                    2
                 /  |  \
               4    5   1
             /   \       |
            8     9      3
                         /  \
                        6   7
Worst roots from node 2 : 6, 7.
So the worst roots is : 6, 7, 8, 9.
But still I got WA.
Is this method can work ?

Code :

Code: Select all

my code is wrong so I cut it...
Thanks. :cry:

Posted: Wed Apr 09, 2003 11:13 am
by Red Scorpion
Finally I've found my bug, :D
And got AC.
Thanks everyone for helping me out.
RS :lol: :lol:

10459 - It's possible?

Posted: Sun Apr 24, 2005 1:36 pm
by Fix
My question is:

It's possible an input like that one:

3
2 2 3
2 1 2
2 1 3

which is this tree

1
/ \
2 _ 3


or like that one:

7
2 2 3
3 1 4 5
3 1 6 7
1 2
2 2 6
2 3 5
1 3

which is this tree:
1
/ \
2 3
/ \ / \
4 5_ 6 7

I did an algorithm which runs well with normal imputs, but when I submit it, I get Memory Limit Exceded from the Judge, and I think it's possible that my algorithm enters in an infinite loop because of a "closed tree".

Thanks

PD: Has anybody some inputs. Thanks again.

Re: 10459 - The Tree Root

Posted: Wed Sep 15, 2010 10:59 am
by Angeh
:((
whats wrong withm this code ..
the Algorithm is to Find First the Best rrots ...
then Run a BFS with the source of Best roosts and find the nodes with Maximum Depht ...
whats wrong ????
:((
thanks ...

Code: Select all

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
int level[5010];
int mark[5010],MA=1;
int C[5010];
vector<int> Graph[5010];
int main(){
    //freopen("in.txt","r",stdin);
    int n,m,a;
    while(scanf("%d",&n)>0 ){
        FOR(i,n)Graph[i].clear();
        FOR(i,n){
            scanf("%d",&m);
            FOR(j,m){
                scanf("%d",&a);
                Graph[i].push_back(a-1);
            }
        }
        //do BFS to find the best ...
        int maxi=0;
        MA++;
        FOR(i,n) C[i]=Graph[i].size();
        queue<int> Q;
        FOR(i,n) if(Graph[i].size()==1){
            Q.push(i);
            mark[i]=MA;
            level[i]=0;
        }
        while(Q.empty() ==false ){
            int u=Q.front();Q.pop();
            FOR(i,Graph[u].size() ){
                int v=Graph[u][i];
                if(mark[v]==MA)continue;
                C[v]--;
                if(C[v]==1){
                    mark[v]=MA;
                    Q.push(v);
                    level[v]=level[u]+1;
                }
                maxi=max(maxi,level[v] );
            }
        }
        printf("Best Roots  :");
        FOR(i,n)if(level[i]==maxi)printf(" %d",i+1);
        putchar('\n');
        //second BFS
        MA++;
        FOR(i,n)if(level[i]==maxi){
            Q.push(i);
            level[i]=0;
            mark[i]=MA;
        }
        maxi=0;
        while(Q.empty() ==false ){
            int u=Q.front();Q.pop();
            FOR(i,Graph[u].size() ){
                int v=Graph[u][i];
                if(mark[v]==MA)continue;
                mark[v]=MA;
                level[v]=level[u]+1;
                Q.push(v);
            }
            maxi=max(maxi,level[u]);
        }
        printf("Worst Roots :");
        FOR(i,n) if(level[i]==maxi )printf(" %d",i+1);
        putchar('\n');
    }
    return 0;
}

10459: WA... corner cases??

Posted: Wed Sep 04, 2013 12:15 pm
by theemathas
I wrote this code, tested it with the sample data and some corner cases, and got correct answers. But for some reason, I got WA after submitting. Can anyone provide me a test case that my code has a bug?

Code: Select all

currently got time limit (at least better than WA)
problem was multiple cases

Re: 10459 - The Tree Root

Posted: Wed Sep 04, 2013 9:46 pm
by brianfry713
Input:

Code: Select all

7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
Output should be:

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7
Best Roots  : 1
Worst Roots : 4 5 6 7

Re: 10459 - The Tree Root

Posted: Thu Sep 05, 2013 9:52 am
by theemathas
Thanks!
I never noticed that multiple datasets were possible.
However, I'm currently getting time limit. I think I can do the left myself.