Page 2 of 3

Re: 10459 - The Tree Root

Posted: Wed May 21, 2014 10:22 am
by prashantharshi
i m getting WA contnuously even my code print correct answers
need help
#include<iostream>
#define max 5100
#define size 5100
int pred[max];
int status[max];
int height[max];
int state[max];
using namespace std;
struct node
{
int data;
node* link;
node(int d)
{
data=d;
link=NULL;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

struct tnode
{
int data;
int no;
int flag;
tnode** childlist;
tnode(int d)
{
data=d;
no=0;
flag=0;
}
};
struct stack
{
tnode* arr[size];
int top;
void push(tnode*);
tnode* pop();
stack()
{
top=-1;
}
}st;
void stack::push(tnode* ptr)
{
arr[++top]=ptr;
}
tnode* stack::pop()
{
tnode* p1=arr[top];
top--;
return p1;
}
struct queue
{
int front;
int rear;
tnode* arr[size];
void insert(tnode*);
tnode* del();
queue();
}q;
queue::queue()
{
front=-1;
rear=-1;
}
tnode* queue::del()
{

if(front!=-1)
{
tnode* f=arr[front];
if(front==rear)
{
front=-1;
rear=-1;
}
else
{
front=(front+1)%size;
}
return f;
}

}
void queue::insert(tnode* f)
{
rear=(rear+1)%size;
arr[rear]=f;
if(front==-1)
front=0;
}

void fun(tnode* &root,int v,int n)
{
if(!root)
{
root=new tnode(v);
}
int loc[max];
int k,cnt;
k=cnt=0;
for(int i=1;i<=n;i++)
{
if(pred==v)
{
loc[k]=i;
cnt++;
k++;
}
}
root->no=cnt;
root->childlist=new tnode*[cnt];
for(int i=0;i<cnt;i++)
{
root->childlist=NULL;;
}
for(int i=0;i<cnt;i++)
{
fun(root->childlist,loc,n);
}
}
void replicate(tnode* root,tnode* &ptr)
{
if(!ptr)
{
ptr=new tnode(root->data);
ptr->no=root->no;
ptr->childlist=new tnode*[ptr->no];
for(int i=0;i<ptr->no;i++)
{
ptr->childlist=NULL;
}
}
for(int i=0;i<ptr->no;i++)
{
replicate(root->childlist,ptr->childlist);
}

}
int cnt_ancestor(tnode* root,int k,int &cnt)
{
int k1;
if(root->data==k)
{
root->flag=1;
return 1;
}
for(int i=0;i<root->no;i++)
{
k1=cnt_ancestor(root->childlist,k,cnt);
if(k1)
{
root->flag=1;
cnt++;
return 1;
}
}
return 0;
}
tnode* make_root(tnode* root,int cnt)
{
if(cnt==0)
return root;
tnode* ptr;
int p,ind,i;
while(cnt!=0)
{
for(i=0;i<root->no;i++)
{
if(root->childlist->flag==1)
{
ind=i;
ptr=root->childlist;
}
}
for(i=0;i<ptr->no;i++)
{
q.insert(ptr->childlist[i]);
}
p=ptr->no;
ptr->no++;
ptr->childlist=new tnode*[ptr->no];
for(i=0;i<p;i++)
{
ptr->childlist[i]=q.del();
}
ptr->childlist[i]=root;
for(i=ind;i<(root->no)-1;i++)
{
root->childlist[i]=root->childlist[i+1];
}
root->childlist[i]=NULL;
root->no--;
root->flag=0;
root=ptr;
cnt--;
}
return ptr;
}
void display(tnode* root)
{
if(root->no==0)
{
cout<<root->data<<" ";
return;
}
else
{
cout<<root->data<<" ";
for(int i=0;i<root->no;i++)
{
display(root->childlist[i]);
}
}
}
int get_height(tnode* root)
{
int m=0;
if(root->no==0)
{
return 0;
}
else
{
for(int i=0;i<root->no;i++)
{
int k=1+get_height(root->childlist[i]);
if(k>m)
m=k;
}
}
return m;
}
lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=new node(d);
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void dfs(lnode* start,int v)
{
state[v]=1;
lnode* ptr=get_address(start,v);
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
pred[p]=v;
dfs(start,p);
}
temp=temp->link;
}
}
int main()
{
lnode* start=NULL;
int n,p,k,cnt;
int bh=999999;
int wh=-9999;
tnode** ptr;
tnode* root=NULL;
lnode* temp;
cin>>n;
ptr=new tnode*[n+1];
for(int i=1;i<=n;i++)
{
ptr[i]=NULL;
pred[i]=-1;
status[i]=0;
state[i]=0;
}
for(int i=1;i<=n;i++)
{
start=addafter1(start,i);
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
temp->right=addafter2(temp->right,k);
}
}
dfs(start,1);
fun(root,1,n);
for(int i=1;i<=n;i++)
{
replicate(root,ptr[i]);
cnt=0;
int c=cnt_ancestor(ptr[i],i,cnt);
ptr[i]=make_root(ptr[i],cnt);
height[i]=get_height(ptr[i]);

}
for(int i=1;i<=n;i++)
{
if(height[i]<bh)
{
bh=height[i];
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height[i]>wh)
{
wh=height[i];
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height[i]==wh)
cout<<i<<" ";
}
return 0;

}

Re: 10459 - The Tree Root

Posted: Wed May 21, 2014 12:30 pm
by prashantharshi
here is my revised code using just dfs on adjacency list and getting the maximum depth during dfs as the height when that vertex act as root
my code is giving perfect outupts stiil verdict is WA
need urgent help
#include<iostream>
#define max 5100
int state[max];
int height[max];
using namespace std;
struct node
{
int data;
node* link;
node(int d)
{
data=d;
link=NULL;
}
};
struct lnode
{
int d;
node* right;
lnode* down;
lnode(int k)
{
d=k;
right=NULL;
down=NULL;
}
};

lnode* addafter1(lnode* start,int d)
{
if(start==NULL)
{
start=new lnode(d);
return start;
}
lnode* temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
temp->down=new lnode(d);
return start;
}
node* addafter2(node* strt,int d)
{
if(strt==NULL)
{
strt=new node(d);
return strt;
}
node* temp=strt;
while(temp->link!=NULL)
{
temp=temp->link;
}
temp->link=new node(d);
return strt;
}
lnode* get_address(lnode* start,int v)
{
lnode* temp=start;
while(temp->d!=v)
{
temp=temp->down;
}
return temp;
}
void reset_status(int n)
{
for(int i=1;i<n;i++)
{
state=0;
}
}
void dfs(lnode* start,int v,int h,int &m)
{
state[v]=1;
lnode* ptr=get_address(start,v);
node* temp=ptr->right;
while(temp!=NULL)
{
int p=temp->data;
if(state[p]==0)
{
dfs(start,p,h+1,m);
}
temp=temp->link;
}
if(h>m)
m=h;
}
int main()
{
lnode* start=NULL;
int h,m,n,p,k;
int bh=999999;
int wh=-9999;
lnode* temp;
cin>>n;
for(int i=1;i<=n;i++)
{
start=addafter1(start,i);
temp=start;
while(temp->down!=NULL)
{
temp=temp->down;
}
cin>>p;
for(int j=0;j<p;j++)
{
cin>>k;
temp->right=addafter2(temp->right,k);
}
}
for(int i=1;i<=n;i++)
{
h=0,m=0;
reset_status(n);
dfs(start,i,h,m);
height=m;
}
for(int i=1;i<=n;i++)
{
if(height<bh)
{
bh=height;
}
}
cout<<"Best Roots : ";
for(int i=1;i<=n;i++)
{
if(height==bh)
cout<<i<<" ";
}
cout<<"\n";
for(int i=1;i<=n;i++)
{
if(height>wh)
{
wh=height;
}
}
cout<<"Worst Roots : ";
for(int i=1;i<=n;i++)
{
if(height==wh)
cout<<i<<" ";
}
return 0;

}

Re: 10459 - The Tree Root

Posted: Wed May 21, 2014 8:29 pm
by brianfry713
I ran your code on the sample input. Your code is printing:

Code: Select all

Best Roots : 1 
Worst Roots : 4 5 6 7 
You also have an extra space at the end of each line. The correct sample output is:

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7
Use the code blocks when posting code.

Re: 10459 - The Tree Root

Posted: Sat Jul 26, 2014 1:14 pm
by piyukr
How to find the best roots for this problem?

Re: 10459 - The Tree Root

Posted: Wed Jul 30, 2014 10:02 pm
by lighted
Sample Output

Best Rootsbb: 1
Worst Rootsb: 4 5 6 7
b is space.
brianfry713 wrote: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
brianfry713 wrote:I ran your code on the sample input. Your code is printing:

Code: Select all

Best Roots : 1 
Worst Roots : 4 5 6 7 
You also have an extra space at the end of each line. The correct sample output is:

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7
Use the code blocks when posting code.
They differ in one space after Best Roots. Is sample output correct?

Re: 10459 - The Tree Root

Posted: Thu Jul 31, 2014 10:30 pm
by brianfry713
The sample output is correct, there should be two spaces after Best Roots. I edited my previous post.

Re: 10459 - The Tree Root

Posted: Fri Aug 01, 2014 5:13 am
by lighted
piyukr wrote:How to find the best roots for this problem?
The way how I find best roots:
1. Do loop while nodes exits
2. In each step delete all nodes that have only one parrent.
3. Nodes which remain at last are best roots.

I read that in a tree remain 1 or 2 node. As i understood they are called centers of tree(or graph). :)

I joined input given in this thread.

Code: Select all

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

8
0
0
1 5
1 5
2 3 4
2 8 5
1 8
2 7 6

9
2 3 2
3 4 5 1
3 6 7 1
3 8 9 2
1 2
1 3
1 3
1 4
1 4


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

7
2 2 3
3 1 6 7
3 1 4 5
1 3
1 3
1 2
1 2
Acc output

Code: Select all

Best Roots  : 1
Worst Roots : 4 5 6 7
Best Roots  : 6
Worst Roots : 3 4 7
Best Roots  : 1 2
Worst Roots : 6 7 8 9
Best Roots  : 1 4
Worst Roots : 5 7 8
Best Roots  : 1
Worst Roots : 4 5 6 7

Re: 10459 - The Tree Root

Posted: Sat Sep 06, 2014 1:42 pm
by Farsan
Is the given tree connected or could there be any forest???Getting Wa... Passed all I/O of the forum when the tree is connected,here is my code

Code: Select all

//ACED

Re: 10459 - The Tree Root

Posted: Sat Sep 06, 2014 5:35 pm
by lighted
Your program doen't pass second test posted above.

Input

Code: Select all

8
0
0
1 5
1 5
2 3 4
2 8 5
1 8
2 7 6
Acc Output

Code: Select all

Best Roots  : 6
Worst Roots : 3 4 7
Your Output

Code: Select all

Best Roots  : 1 2 3 4 5 6 7 8
Worst Roots :

Re: 10459 - The Tree Root

Posted: Sat Sep 06, 2014 9:42 pm
by Farsan
That's why i asked whether is it possible that there is a forest instead of a tree in input.Even your output differs from the output i got herehttp://www.udebug.com/UVa/10459... I do not think there is any input where any node is isolated.

Re: 10459 - The Tree Root

Posted: Sun Sep 07, 2014 9:26 pm
by lighted
Yes, you are right. According to problem description
Then successively for each i'th node there will be a positive integer K following id of K nodes which are adjacent to i


I added 1st and 2nd node to the tree. Try input

Code: Select all

8
1 5
1 8
1 5
1 5
4 3 4 1 6
2 8 5
1 8
3 7 6 2
Acc. Output

Code: Select all

Best Roots  : 6
Worst Roots : 1 2 3 4 7
Your Output

Code: Select all

Best Roots  : 6
Worst Roots : 2 7
Output of forthright48 (uDebug)

Code: Select all

Best Roots  : 5
Worst Roots : 1 3 4
Sometimes it happens that we get accepted for partial solutions. It is because judge's input are weak and may not contain all critical input.
forthright48's solution at uDebug for problem 11428 was changed because it wasn't giving correct answers for some critical input, though it was accepted by judge.
It was changed to brianfry713's solution.

Re: 10459 - The Tree Root

Posted: Tue Sep 09, 2014 11:27 pm
by brianfry713
I uploaded my code and some small random input to:
http://www.udebug.com/UVa/10459
Farsan, your code fails some of those random input cases.

The judge's input only contains trees. lighted's input in the previous post is also invalid.

Re: 10459 - The Tree Root

Posted: Wed Sep 10, 2014 2:41 pm
by lighted
Invalid input

Code: Select all

8
1 5
1 8
1 5
1 5
3 3 4 1 <- node 6 is missing here
2 8 5
1 8
3 7 6 2
I edited input in my previous post. Outputs are still the same

Re: 10459 - The Tree Root

Posted: Thu Sep 11, 2014 9:22 am
by Farsan
Thanks brianfry713,you always help :).Struggled to find out worse roots but at last ACED.

Re: 10459 - The Tree Root

Posted: Sat Jun 10, 2017 11:37 pm
by ebb
Hi everyone,

I'm having trouble with this problem. My code (Java) passes all the inputs in this thread and in uDebug, but gets Runtime Error in the judge. I'm pretty sure it is the code that reads the input, because when I wrap it in a try catch I get Wrong Answer. When I remove the actual algorithm instead, I keep getting RE. When catching the exception, it doesn't matter if I stop completely, simply go to the next test case or ignore the exception: I always get Wrong Answer.

Here's my code in case someone can give me a hint of what could be wrong. I've removed the algorithm so we can focus on the input-reading code.

Edit: I removed the code, as I found my mistake.