10410 - Tree Reconstruction

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10410 - Tree Reconstruction

Post 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

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

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

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

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

SnapDragon
Problemsetter
Posts: 22
Joined: Tue Jun 11, 2002 12:35 am

Post 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". ;)

Alexander Grushetsky
New poster
Posts: 28
Joined: Wed Jul 31, 2002 10:33 am
Location: Ukraine
Contact:

Post 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

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan

Post 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:

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post 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
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

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

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post 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)

CC
New poster
Posts: 8
Joined: Tue Oct 14, 2003 5:02 am

Post by CC »

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

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

10410-tree reconstruction

Post 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
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:

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

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

Re: 10410 - Tree Reconstruction

Post 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 !!!

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

Re: 10410 - Tree Reconstruction

Post 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

Post Reply

Return to “Volume 104 (10400-10499)”