10459  The Tree Root
Moderator: Board moderators
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
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.
Success is also easy to handle: You've solved the wrong problem. Work hard to improve.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
Can anyone help me.
I got WA many time.
Here is my code:
Please help...help....
Thanks,
RS
I got WA many time.
Here is my code:
Code: Select all
Thanks,
RS
Last edited by Red Scorpion on Thu Mar 27, 2003 6:50 am, edited 1 time in total.
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 middlepoint (or 2 points) of the path N1>N2 and add it to the list of the best roots.
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 middlepoint (or 2 points) of the path N1>N2 and add it to the list of the best roots.
@+!
DitriX
DitriX

 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 :
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
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.
If someone have time please give me the tricky input.
Best Thanks,
Red Scorpion
Code: Select all
1
/ \
2 3
/ \ / \
4 5 6 7
/ \
8 9
best: 1 2
worst: 6 7 8 9
And your algo should add 5 as worst root.
@+!
DitriX
DitriX

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

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
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:
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
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
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

 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.
But still I got WA.
Is this method can work ?
Code :
Thanks.
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.
Is this method can work ?
Code :
Code: Select all
my code is wrong so I cut it...
Last edited by Red Scorpion on Wed Apr 09, 2003 11:29 am, edited 1 time in total.

 Experienced poster
 Posts: 192
 Joined: Sat Nov 30, 2002 5:14 am
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.
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
(
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 ...
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(a1);
}
}
//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;)
Beliefs are not facts, believe what you need to believe;)

 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.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10459  The Tree Root
Input:Output should be:
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
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!

 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.
I never noticed that multiple datasets were possible.
However, I'm currently getting time limit. I think I can do the left myself.