Page 1 of 1

10410 - Tree Reconstruction

Posted: Mon Nov 11, 2002 1:24 pm
by Christian Schuster
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.

Thanks in advance.

Christian

Posted: Mon Nov 11, 2002 2:55 pm
by Yarin
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...

Posted: Mon Nov 11, 2002 7:32 pm
by Christian Schuster
Thank You! There seemed to be a bug in my subtree finding algorithm - I'd better call it "hack". :roll: 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.

Posted: Mon Nov 11, 2002 7:54 pm
by SnapDragon
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". ;)

Posted: Tue Nov 12, 2002 11:45 am
by Alexander Grushetsky
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

Posted: Fri Mar 07, 2003 6:46 pm
by LittleJohn
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.. :cry:

Posted: Tue Apr 01, 2003 4:11 pm
by Dominik Michniewski
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

Posted: Mon Apr 07, 2003 11:28 pm
by cplusplus
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~~ :cry:
Can anyone please give me some more tests??
I am really appreciate for your help,Thank you very much.....

Posted: Tue Sep 16, 2003 9:10 am
by miras
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 8)

Posted: Thu Sep 02, 2004 2:38 pm
by CC
though my programme give right answer to the these input
I still got WA, can somebody give more tests?
:cry:

10410-tree reconstruction

Posted: Mon Sep 05, 2005 9:36 pm
by jagadish
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

Posted: Thu May 31, 2007 10:19 pm
by yiuyuho
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.

Re: 10410 - Tree Reconstruction

Posted: Fri Apr 03, 2009 9:53 am
by dodouuu
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 !!!

Re: 10410 - Tree Reconstruction

Posted: Fri Jul 17, 2009 9:04 pm
by tryit1

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