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

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

829 - Almost Balanced Trees

Post by Adrian Kuegel »

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

Post by rusi »

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

Post by fds »

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 :wink: it just happens I have the solution of the problem's author and hopefully it is "correct".

Hope this helps,

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

Post by Adrian Kuegel »

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

Post by fds »

Adrian Kuegel wrote: 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.
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.

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

Post by Adrian Kuegel »

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

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

Post by Adrian Kuegel »

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

Post by CDiMa »

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

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

Post by Adrian Kuegel »

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

Post by CDiMa »

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

Ciao!!!

Claudio

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

Post by Adrian Kuegel »

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" ?

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

Post by Adrian Kuegel »

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

Post by CDiMa »

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

Post by CDiMa »

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

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

Post by Adrian Kuegel »

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.

Post Reply

Return to “Volume 8 (800-899)”