10459 - The Tree Root

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

Moderator: Board moderators

zsepi
Learning poster
Posts: 51
Joined: Thu Sep 26, 2002 7:43 pm
Location: Easton, PA, USA

10459 - The Tree Root

Post by zsepi » Wed Feb 26, 2003 12:06 am

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
Dealing with failure is easy: Work hard to improve.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Mon Mar 24, 2003 5:47 am

Can anyone help me.
I got WA many time.

Here is my code: Please help...help.... :cry: :cry: :cry:
Thanks,
RS
Last edited by Red Scorpion on Thu Mar 27, 2003 6:50 am, edited 1 time in total.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Tue Mar 25, 2003 1:35 am

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.
@+!
DitriX

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Tue Mar 25, 2003 3:47 am

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

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Tue Mar 25, 2003 1:44 pm

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.
@+!
DitriX

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Mar 26, 2003 3:52 am

....
Last edited by Red Scorpion on Thu Mar 27, 2003 6:53 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Thu Mar 27, 2003 5:27 am

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.

makbet
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo

Post by makbet » Fri Mar 28, 2003 12:03 pm

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:

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Tue Apr 01, 2003 9:29 am

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:
Last edited by Red Scorpion on Wed Apr 09, 2003 11:29 am, edited 1 time in total.

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 am

Post by Red Scorpion » Wed Apr 09, 2003 11:13 am

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

Fix
New poster
Posts: 2
Joined: Sun Apr 24, 2005 1:20 pm

10459 - It's possible?

Post by Fix » Sun Apr 24, 2005 1:36 pm

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
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10459 - The Tree Root

Post by Angeh » Wed Sep 15, 2010 10:59 am

:((
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;
}
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

theemathas
New poster
Posts: 19
Joined: Mon Jan 07, 2013 9:30 am

10459: WA... corner cases??

Post by theemathas » Wed Sep 04, 2013 12:15 pm

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
Last edited by theemathas on Thu Sep 05, 2013 9:51 am, edited 1 time in total.

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

Re: 10459 - The Tree Root

Post by brianfry713 » Wed Sep 04, 2013 9:46 pm

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
Check input and AC output for thousands of problems on uDebug!

theemathas
New poster
Posts: 19
Joined: Mon Jan 07, 2013 9:30 am

Re: 10459 - The Tree Root

Post by theemathas » Thu Sep 05, 2013 9:52 am

Thanks!
I never noticed that multiple datasets were possible.
However, I'm currently getting time limit. I think I can do the left myself.

Post Reply

Return to “Volume 104 (10400-10499)”