## 829 - Almost Balanced Trees

Moderator: Board moderators

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### 829 - Almost Balanced Trees

I have tried to solve this problem, but I got always wrong answer. Here is the input I have tested my program with:

Code: Select all

``````14

1 1 2 -1
1 0

1 3 10 1 15 0 2 2 6 0 7 1 4 0 9 1 21 0
1 3 10 0 2 2 6 0 7 1 4 0 9 1 21 0

1 1 2 0
1 0

-1 1 2 0
-1 0

1 1 0 0
1 0

1 1 2 0 1
1 0

1 1 2 0
1 0 1

1 1 2 0
2 1 1 0

1 1 2 0
3 1 1 0

1 2 2 1 3 1 4 0 5 0
1 0

1 2 2 1 3 0 4 0
1 2 2 1 3 0 4 0

1 2 2 1 3 0 4 0
2 2 1 1 4 0 3 0

1 1 1 0
1 0

1 2 2 0 3 0
1 2 1 0 1 0``````
Output:

Code: Select all

``````-1

1 -15

1 -2

-1

-1

-1

-1

1 1 2

-1

0

1 0

1 0

-1

-1
``````

rusi
New poster
Posts: 1
Joined: Thu Sep 12, 2002 3:01 pm

### RE: 829 Almost Balanced Trees

I also always get wrong answer and I have no idea why.

I'm not sure if you have to return -1 or 1 -2 for this particular input set:

Code: Select all

``````1 1 2 0
1 0 1
``````
You can construct the trees if you ignore the last node '1'. I'm not sure if the last node has to be ignored if the first two trees are valid.

Also, I was wondering if the trees are ordered. And finally, it doesn't say anywhere if the first tree will be on the first line and the second tree will be on the second line. Reading the problem statement I've got the impression that you can have the following input:

Code: Select all

``````1 1
2 0
1
0
``````

fds
New poster
Posts: 4
Joined: Fri Aug 30, 2002 4:10 pm

### Re: 829 Almost Balanced Trees

Adrian, all of your tests are correct except for the following 3 cases:

1 1 2 0 1
1 0

the first line doesn't define a proper tree according to the problem definition (last 1 shouldn't be there).

1 1 2 0
1 0 1

the output should be 1 -2 (yours is -1)

1 2 2 1 3 1 4 0 5 0
1 0

the output should be -1 (yours is 0)

You may wonder how do I know this it just happens I have the solution of the problem's author and hopefully it is "correct".

Hope this helps,

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Thanks for your reply. I made the mistake to assume that each tree is described in one line, and that I have to check if there is perhaps some integer that doesn't belong to the tree specification (in these cases i printed -1). Therefore my input is incorrect at some places.
Can you please verify this input again:
1

1 2 2 1 3 1 4 0 5 0
1 0

Because I think that the tree specification is ok (only unique positive integers), but the tree is not almost well balanced. Therefore I print 0.

fds
New poster
Posts: 4
Joined: Fri Aug 30, 2002 4:10 pm
1

1 2 2 1 3 1 4 0 5 0
1 0

Because I think that the tree specification is ok (only unique positive integers), but the tree is not almost well balanced. Therefore I print 0.
Yes, the output should be 0.

The solution I have doesn't handle multiple cases, that's why I ended up loosing track of that case and giving you a wrong hint, sorry.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
After a long time I try this problem again. Can someone please tell me if my output for the following test cases is correct?
3

1 2 2 1 3 2 4 1 5 0 6 0 9 2 8 1 7 0 10 0
1 2 2 1 3 2 4 1 5 0 6 0 9 2 8 0 10 0

1 2 2 1 3 0 4 1 5 0
1 2 4 0 2 1 3 0

1 0

Output:
1 -7

1 0

-1

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I found out with some asserts that in the input there are always 2 lines with data per test case, so I assume that each line defines one tree. So I think my problem lies not in reading the input, but I fear that the problem description left something out, like perhaps that the trees are unordered, and therefore for my 2nd test case the answer is perhaps 1 -5 ?

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

### 829 Almost Balanced Trees almost specified

I'm trying to cope with this problem but I think that the problem is at least underspecified.
Assume each tree is given as follows:
Does this mean that the input is well formed wrt the input description? (i.e. that the integers are unique and if a node has three children I'll find three subtrees in input?)
Should I continue reading the input stream over multiple lines until the tree is complete or should I assume that a tree is on a single line?
-1, if the given data does not correspond to the specification of the two trees as described above (i.e., your program must check whether is possible to build a tree from the given numbers, and whether the conditions on the integers are verified);
So I shouldn't assume that the tree was given as explained earlier, but I must check for consistency. So how do I know when to stop reading input? What is the thing I should have assumed about the input?

Finally, what should be the output if the trees are identical?

thanks in advance for any help!

Ciao!!!

Claudio

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Hi,
as I said, the input contains only two lines with data per test case. So the question remains, should we try to combine these lines and first read until first tree is finished, and then until second tree is finished (or end of data is reached), or is the first tree described in line one, and the second tree in line two?
And for equal trees, if first tree is well balanced, I am almost sure that output should be 1 0, because exactly one of the two operations should be used exactly once.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Adrian Kuegel wrote:After a long time I try this problem again. Can someone please tell me if my output for the following test cases is correct?
3

1 2 2 1 3 2 4 1 5 0 6 0 9 2 8 1 7 0 10 0
1 2 2 1 3 2 4 1 5 0 6 0 9 2 8 0 10 0

1 2 2 1 3 0 4 1 5 0
1 2 4 0 2 1 3 0

1 0

Output:
1 -7

1 0

-1
I finally managed to get accepted with an ugly and slow solution so now I'm able to answer:

Code: Select all

``````0

1 0

Segmentation fault
``````
So you can be sure that every input blocks consists of two trees each one on its own line

Ciao!!!

Claudio

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
I think, my output for my first test case is correct according to the problem description:
A tree is an almost well-balanced tree if at each node the depths of the subtrees rooted at its children are the same or differ at most by 1. The depth of a tree is 1 if the tree is a single leaf, or 1 plus the maximum of the depths of subtrees rooted at the children of its root.
So here is how the test case looks like as a tree:
1 2 2 1 3 2 4 1 5 0 6 0 9 2 8 1 7 0 10 0

Code: Select all

``````        1
2     9
3     8  10
4  6  7
5
``````
So nodes 5, 6, 7 and 10 have depth 1, nodes 4,8 depth 2, nodes 3 and 9 depth 3, node 2 depth 4, node 1 depth 5.
For node 1, the depth of subtrees is 4 (for node 2) and 3 (node 9).
and the subtrees with node 2 as root or node 9 as node are obviously almost well-balanced, so the tree is almost well balanced.
This test case is an example for that the given definition is not equivalent to the definition: all leaves should occur at depths that differ at most by one.
Which definition for almost well balanced did you use to get Accepted and to get as result for my test case "0" ?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Well, it seems you was lucky to get Accepted, since there is no such test case like my first test case in the input (I got Accepted with correct checking for almost well balanced).
My mistake was, I thought I should print -1 if the identifiers of the second tree are not contained in the set of identifiers of first tree. But if this occurs, that means only that second tree cannot be reached from first tree using one of the two operations.

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Adrian Kuegel wrote:This test case is an example for that the given definition is not equivalent to the definition: all leaves should occur at depths that differ at most by one.
Which definition for almost well balanced did you use to get Accepted and to get as result for my test case "0" ?
While reading input I keep track of the minimum and maximum depth of leaves and check if they differ by more than one. So I check against the unequivalent definition
I think that probably the dataset of the judge is small and so not all of the specifications are verified. My program is surely inefficient since I check for different requirements in successive steps, revisiting the trees two times and still runtime is 0:00.000...

Ciao!!!

Claudio

CDiMa
Experienced poster
Posts: 214
Joined: Fri Oct 17, 2003 5:49 pm
Location: Genova
Adrian Kuegel wrote:Well, it seems you was lucky to get Accepted, since there is no such test case like my first test case in the input (I got Accepted with correct checking for almost well balanced).
I already knew I was lucky. I wrote rapidly this program and it got AC P.E. at first try.
I just wanted to set up the program to be able to read input and then refine the checks at a later stage...
Adrian Kuegel wrote:My mistake was, I thought I should print -1 if the identifiers of the second tree are not contained in the set of identifiers of first tree. But if this occurs, that means only that second tree cannot be reached from first tree using one of the two operations.
Actually I do such a check...
While reading the leaves I store them in two arrays and then check if the leaves of tree B
is a subset of tree A. If not I output -1 since the problem states:
the set of integers appearing in nodes of B is contained in, or is equal to the corresponding set of A
and I'm required to check whether the conditions on the integers are verified. I didn't know which conditions to check and I thoght I should check if nodes of B were a subset of those of A. Probably I misunderstood this sentence and simply could assume it...

Ciao!!!

Claudio

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Hmm, funny. And I was almost sure that was the thing that got me so many WA.
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
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:
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;
}
I think it is correct. l[0] is number of nodes * 2 of first tree, l[1] is the same for second tree, and the other things should be obvious.