Page 1 of 3
Posted: Mon Mar 18, 2002 10:47 pm
by Max Fate
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
115 - Climbing Trees
Posted: Sat Feb 15, 2003 2:58 pm
by ei01036
Has anyone inputs for this problem? I'm getting WA and i can't find the problem...
Posted: Tue Aug 19, 2003 5:20 pm
by xbeanx
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.
Posted: Tue Sep 16, 2003 1:21 am
by bugzpodder
can you share the trick, xbeanx? my code was 99 lines long!!
Posted: Wed Sep 17, 2003 3:34 pm
by PdR
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):
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
Hope this helps.
Posted: Wed Sep 17, 2003 10:57 pm
by bugzpodder
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.
Posted: Thu Sep 18, 2003 2:08 am
by PdR
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
is wrong.
Posted: Fri Sep 19, 2003 4:14 pm
by xbeanx
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.
Posted: Sun Sep 21, 2003 12:19 am
by bugzpodder
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.
Posted: Mon Sep 22, 2003 2:02 pm
by xbeanx
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.
Posted: Tue Oct 28, 2003 12:58 am
by wsarzynski
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
Posted: Tue Oct 28, 2003 1:17 am
by wsarzynski
ok, i checked with sigsegv method and there are no such cases.
Posted: Tue Oct 28, 2003 2:44 am
by wsarzynski
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
Posted: Sat Nov 01, 2003 3:13 am
by wsarzynski
115 : "Climbing Trees" Please Help
Posted: Fri Nov 07, 2003 9:11 am
by Almost Human
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
