## 829 - Almost Balanced Trees

Moderator: Board moderators

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Adrian Kuegel wrote:Hmm, funny. And I was almost sure that was the thing that got me so many WA.
I think I found out why...
Adrian Kuegel wrote:But I asserted that there is a case in the input where the node identifiers of second tree are not contained in first tree.
Now for example for:
2

1 0
2 0

1 2 2 1 3 1 4 0 5 0
6 0
my program would print
1 0
0
my program prints

Code: Select all

``````-1

0``````
Adrian Kuegel wrote:And I changed my program just back so that it would print -1 in this case, and got WA again.
And here is my check routine:
[c]int iscontained() {
int i,j;
for (i=0; i<l[1]; i+=2) {
for (j=0; j<l[0]; j+=2)
if (tree[1] == tree[0][j])
break;
if (j >= l[0])
return 0;
}
return 1;
}[/c]
I think it is correct.

I think it is correct too, although I do it in a different way.
I do a quicksort on the set of leaves of the two trees and compare them. This was the fastest way I could think of...

I think the problem lies with the order we do the checks.
I do the checks in this order:
• if one of the trees is not well-formed: -1
number of nodes of tree B greater than those of tree A: -1
treeA almost unbalanced(i.e. by the alternate unequivalent definition ): 0
nodes of tree B not a subset of those of tree A: -1
if number of nodes of B equals those of A
• if topology of tree differs: 1 0
if no swap transformation applies: 1 0
otherwise print: 1 node1 node2

if tree B cannot be obtained by a leaf deletion: 1 0
otherwise print: 1 -leaf

So if B isn't a subset of A but A is unbalanced I print 0 instead of -1...
Or such a case doesn't exist in judge's input or it expects you output 0 although I think your answer is corrected by the problem statement.

As I said earlier, the problem is a bit underspecified and now I add the judge's input is undespecified too

Ciao!!!

Claudio

LithiumDex
New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm