115 - Climbing Trees

Max Fate · Post by **Max Fate** » Mon Mar 18, 2002 10:47 pm

The quote is

Consider academic advisees and advisors as exemplars of such a single parent genealogy (we assume a single advisor, i.e., no co-advisors).

I cannot get what is it, do they mean that person have no more than 1 parent or maybe one may have 2 parents? (or more?!)

By the way if one has any tests for the problem please publish them

ei01036 · Post by **ei01036** » Sat Feb 15, 2003 2:58 pm

Has anyone inputs for this problem? I'm getting WA and i can't find the problem...

xbeanx · Post by **xbeanx** » Tue Aug 19, 2003 5:20 pm

Here's some sample input:

Code: Select all

b a
c a
d b
e b
f b
g b
h c
i c
j c
k c
l d
m d
n e
o e
p e
q f
r f
s g
t g
u g
f h
w h
x h
y i
z j
aa k
bb k
cc k
dd k
ee k
ff l
gg m
hh n
ii o
jj p
kk q
ll r
mm s
nn t
oo u
pp v
qq w
rr x
ss y
tt z
uu aa
vv bb
ww cc
xx dd
yy ee
zz ff
no.child no.parent
l ee
m k
v a
b zz
l m
d c
h g
ee ee
i z
c zz
t n
c y
a zz
q ff
h d
w d

And it's accepted output:

Code: Select all

2 cousin
1 cousin removed 1
no relation
great great grand parent
sibling
0 cousin removed 1
1 cousin
child
0 cousin removed 1
0 cousin removed 4
1 cousin
grand parent
great great great grand parent
3 cousin
1 cousin
1 cousin removed 1

My program for this problem is the shortest so far (not counting problem 100). This is very easy and there's a trick that can let you do it in about 15 lines.

::EDIT:: {for keyword search}
115 p115 115: tree trees climb climbing family families child children parent parents sibling input sample

PS: I added the keywords above because it seems like searches never work for me anymore.

bugzpodder · Post by **bugzpodder** » Tue Sep 16, 2003 1:21 am

can you share the trick, xbeanx? my code was 99 lines long!!

PdR · Post by **PdR** » Wed Sep 17, 2003 3:34 pm

xbeanx wrote:My program for this problem is the shortest so far (not counting problem 100). This is very easy and there's a trick that can let you do it in about 15 lines.

You may be using 15 lines of code... but you surely are producing wrong output!

My accepted solution gives:

Code: Select all

2 cousin
1 cousin removed 1
no relation
great great grand parent
sibling
0 cousin removed 1
1 cousin
sibling
0 cousin removed 1
0 cousin removed 4
1 cousin
grand parent
great great great grand parent
1 cousin removed 1
1 cousin
1 cousin removed 1

Notice the diference in lines 8 and 14 (the input):

Code: Select all

ee ee
q ff

ee isn't a child of ee, but it's surely a sibling as have the same parent (degree 0)
also look at the tree of q ff:

Code: Select all

      a
    /   \
   /     \
   c     b
   |   / |
   h  /  d
   | /   |
   f     l
   |     |
   q     ff

Clearly it's a

Code: Select all

1 cousin removed 1

Hope this helps.

bugzpodder · Post by **bugzpodder** » Wed Sep 17, 2003 10:57 pm

hmm ee and ee should not be in the input at all, (look at the corrections) so this makes no difference. but i have ran my code using the same data set and found everything as a match except for ee and ee. the line 14 was no exception. my code got accepted after I caught the empty spaces and lines at the end of the input.

PdR · Post by **PdR** » Thu Sep 18, 2003 2:08 am

By definition p and q are ``cousins'' if and only if they are related (i.e., there is a path from p to q in the implicit undirected parent-child tree). Let r represent the least common ancestor of p and q (i.e., no descendent of r is an ancestor of both p and q), where p is an m-descendent of r and q is an n-descendent of r.

Look at the tree I previously designed and you find that 'a' is a common ancestor, but 'b' also is! So we can't use 'a' as an ancestor, only 'b'.

As you can see the output

Code: Select all

3 cousin

is wrong.

xbeanx · Post by **xbeanx** » Fri Sep 19, 2003 4:14 pm

My code is longer than 15 lines. But the 'core' of it (besides the input parsing and whatnot) is only around 15 lines.

And the judge told me it was the right output.

It only takes 2 nested for loops (to check each member of each family), and then set k = Math.min(m, n); and j = Math.abs(n-m);

Then the print method takes 4 more lines.

Of course, I have deliberately been vague.

bugzpodder · Post by **bugzpodder** » Sun Sep 21, 2003 12:19 am

speaking of which, the shortest problem i wrote was for hashmat the brave warrior, it was so stupid -- just find the maximum of two numbers or something. anyone could have done the whole problem in 10 lines or less. but i dont understand why this is even in the archive in the first place, other than that i think it is part of the hosted competition here.

xbeanx · Post by **xbeanx** » Mon Sep 22, 2003 2:02 pm

Sometimes the trivial problems are the hardest. Especially when they word them in such a way as to make you think you have to do something spectacular.

wsarzynski · Post by **wsarzynski** » Tue Oct 28, 2003 12:58 am

i'm confused, help pls.
what should i printf for this case:
d a
e a
d c
c b
e b
no.child no.parent
d e

wsarzynski · Post by **wsarzynski** » Tue Oct 28, 2003 1:17 am

ok, i checked with sigsegv method and there are no such cases.

wsarzynski · Post by **wsarzynski** » Tue Oct 28, 2003 2:44 am

i checked this 1 cousin removed 1 vs. 3 cousin case
and it's ok, but i get WA.
what doi printf for graph as in example and query:
a f

wsarzynski · Post by **wsarzynski** » Sat Nov 01, 2003 3:13 am

i lost couple of hours, but got Accepted
INPUT IS ...
THERE ARE EMPTY LINES / LINES WITHOUT TWO FULL NAMES

I DON'T LIKE PROBLEMS LIKE THIS !!!!!!!!!!!!!!!!!!!!!!

Almost Human · Post by **Almost Human** » Fri Nov 07, 2003 9:11 am

I think the parent-child relation will constuct a tree, so that a node will have only 1 parent. So perhaps I should just build a vector table to store names and their parents. Am I right ?

please help. Thanks

OJ Board

115 - Climbing Trees

115 - Climbing Trees

115 : "Climbing Trees" Please Help