10410 - Tree Reconstruction

[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

[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...

[Christian Schuster]

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]

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]

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]

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]

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

[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~~
Can anyone please give me some more tests??
I am really appreciate for your help,Thank you very much.....

[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

[CC]

though my programme give right answer to the these input
I still got WA, can somebody give more tests?

[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

[yiuyuho]

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]

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]

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