10459 - The Tree Root

Moderator: Board moderators

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

10459 - The Tree Root

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
Can anyone help me.
I got WA many time.

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
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
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
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

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

@+!
DitriX

Red Scorpion
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 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
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
New poster
Posts: 44
Joined: Tue Nov 26, 2002 11:01 pm
Location: Wejherowo
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
Experienced poster
Posts: 192
Joined: Sat Nov 30, 2002 5:14 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.
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
Finally I've found my bug,
And got AC.
Thanks everyone for helping me out.
RS

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

10459 - It's possible?

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

(
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??

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

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

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