829 - Almost Balanced Trees

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

Moderator: Board moderators

Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova

Post by CDiMa »

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:

1 0
2 0

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

Code: Select all


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])
if (j >= l[0])
return 0;
return 1;
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 ;)



New poster
Posts: 44
Joined: Tue Jun 06, 2006 6:44 pm
Location: Nova Scotia, Canada

Post by LithiumDex »

-almost well balanced: abs(mindepth(root)-maxdepth(root)) <= 1
-one tree per line
-remeber to output -del in case of delete! (that's what got me AC)

note to judge, I have received rank 1 on this problem.. even though other's have solved it in 0.000 before me... is this do to memory usage that I am not seeing?
- Chris Adams

Post Reply

Return to “Volume 8 (800-899)”