## 10410 - Tree Reconstruction

Moderator: Board moderators

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am

### 10410 - Tree Reconstruction

Hello!

I tried to solve that problem, and got WA with 0.00x seconds. So I thought there might be multiple sets of input. There _ARE_ numbers after the first set of data. I tried and tried and ... still got WA.

I try to build the tree recursively, making some weird comparisons between BFS and DFS... Quite Hard to explain - and WA.

Is there any simple approach I didn't realize? Are there some special cases? Some test data would be appreciated.

Christian

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
14
7 8 12 4 5 1 6 11 2 3 10 9 13 14
7 8 4 5 2 3 12 1 6 10 14 11 9 13
5
5 4 3 2 1
5 4 3 2 1
Try this. My (AC) program returns
1:
2:
3:
4:
5: 2 3
6: 10
7: 8 12
8: 4 5
9:
10: 14
11: 9 13
12: 1 6 11
13:
14:
1:
2:
3:
4:
5: 1 2 3 4
After I solved this problem in the contest, I noticed my program was wrong though; the last test case can't be tree of height 1 because children are traversed in ascending order. Thus the last test case above MUST be
1:
2: 1
3: 2
4: 3
5: 4
But, for now, several solutions seems to be accepted...

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
Thank You! There seemed to be a bug in my subtree finding algorithm - I'd better call it "hack". I threw it away, wrote something totally new and got AC. Thanks for the test cases, my original program gave wrong answer on the first.

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am
It's a little-known fact that Yarin's phrase "I noticed my program was wrong", when used in this context, ACTUALLY means "SnapDragon pointed out that my program was wrong".

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:
It seems there is no test case such as:
5
5 4 3 2 1
5 4 3 2 1
because my program generates correct output:
1:
2: 1
3: 2
4: 3
5: 4
and also got AC.

There are some more tests:
16
12 13 2 7 1 6 5 8 4 9 10 11 15 16 3 14
12 13 2 1 4 9 6 10 11 7 5 15 16 8 3 14
10
9 3 5 2 7 1 10 4 6 8
9 3 2 7 1 4 10 6 8 5
and the output:
1: 4 9
2: 1 6
3:
4:
5: 15 16
6: 10 11
7: 5 8
8: 3 14
9:
10:
11:
12: 13
13: 2 7
14:
15:
16:
1: 4
2:
3: 2 7
4:
5:
6:
7: 1 10
8:
9: 3 5
10: 6 8

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
hello!
I tried to solve this problem but failed and failed. I still can't work out a correct algorithm.
Could somebody give me some hints? please..

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
If I correct saw problem descriptions, it didn't say that reconstructed tree could be binary tree ... So I think, that for input:
5
5 4 3 2 1
5 4 3 2 1

output should be any of posted before .... I got accepted in this way )

Dominik Michniewski
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

cplusplus
New poster
Posts: 13
Joined: Fri Feb 07, 2003 10:20 pm
I am now doing this problem....
and I got WA many times...
but I have tried all tests posted and my answers are the same
I can't figure out why I got WA, I am going mad~~
Can anyone please give me some more tests??
I am really appreciate for your help,Thank you very much.....

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
elloo
did u tried with

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

_________
made the force be with u

CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am
though my programme give right answer to the these input
I still got WA, can somebody give more tests?

Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

### 10410-tree reconstruction

Can someone point out whats wrong with my algo :

Code: Select all

``````    recurse (  bfstrace , dfstrace   ) {
if( size(trace)==1 ) return ;
if( size(trace)==2 ) make second element child of first && return ;

collect the children of bfstrace[0]   starting from bfstrace[1]

foreach child{
extract the bfs && dfs traces of subtree containing child as
root into  tmpbfs && tmpdfs

recurse(tmpbfs,tmpdfs)
}

}``````

currently it passes all the cases discussed above

also i assume there are no inputs like
3
1 4 3
1 3 4
if u can think of it .. u can do it in software.

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
SnapDragon wrote:It's a little-known fact that Yarin's phrase "I noticed my program was wrong", when used in this context, ACTUALLY means "SnapDragon pointed out that my program was wrong".
Can someone give an approach for this problem that is simple to code and correct (and easy to see)? Seems like this is the type of problem where you can come up with lots of ideas but its hard to see that they are correct for all cases.

dodouuu
New poster
Posts: 9
Joined: Tue Mar 24, 2009 7:50 pm

### Re: 10410 - Tree Reconstruction

I have passed all the test cases above. However, still wrong answer.... can anyone give me a big amount of test cases and the corresponding outputs. Very appreciate !!!

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10410 - Tree Reconstruction

Code: Select all

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

``````

Code: Select all

``````1: 2 3
2: 4 5
3:
4:
5:
1: 2 3
2: 4 5
3: 7
4:
5:
6:
7: 6
``````