115 - Climbing Trees

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

Moderator: Board moderators

Max Fate
New poster
Posts: 6
Joined: Fri Mar 15, 2002 2:00 am

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
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am

115 - Climbing Trees

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... :roll:

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

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

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

PdR
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 am

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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

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
New poster
Posts: 24
Joined: Mon Dec 30, 2002 4:27 am

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

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
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

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
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

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
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

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
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

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

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

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

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
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland

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 !!!!!!!!!!!!!!!!!!!!!! :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil: :evil:

Almost Human
Learning poster
Posts: 93
Joined: Sun Jan 12, 2003 3:30 pm

115 : "Climbing Trees" Please Help

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

Post Reply

Return to “Volume 1 (100-199)”