10459 - The Tree Root

[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

[Red Scorpion]

Can anyone help me.
I got WA many time.

Here is my code:

Code: Select all

Please help...help....
Thanks,
RS

[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.

[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,
Red Scorpion

[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.

[Red Scorpion]

....

[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.

Huge Thanks,
RS.

[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

[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.

[Red Scorpion]

Finally I've found my bug,
And got AC.
Thanks everyone for helping me out.
RS

[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.

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

[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

[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

[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.