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

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

Post by wsarzynski » Sat Nov 08, 2003 5:50 am

There are inputs with many parents for some nodes.
And input is :evil:
you had a topic on 115 with date Sat Nov 01, 2003 2:13 am,
it is very helpfull

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

115

Post by Solaris » Thu Aug 05, 2004 6:57 pm

I don't think the input consists of cases where one node can have multiple parents. My code got AC without checking for that case.

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

115 WA, please somebody take a look, need help

Post by surya ss » Wed Jun 29, 2005 8:36 am

I don't know why my code got WA
please some body help

here is my code

Code: Select all

AC
Last edited by surya ss on Sat May 07, 2011 7:11 pm, edited 1 time in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

Post by chunyi81 » Wed Jun 29, 2005 9:15 am

By reading your code, I found a problem.

From the input description:
Parent-child pairs are terminated by a pair whose first component is the string "no.child''

This part of your code does this:

Code: Select all

      if(strcmp(c,"no.child")==0 && strcmp(p,"no.parent")==0) break; 
You should only check that strcmp(c,"no.child") == 0

Hope this helps.

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

still WA

Post by surya ss » Wed Jun 29, 2005 11:02 am

thanks chunyi81, I miss that,
but I have change it, but it still got WA,
is there anything I miss?
any I/O ?

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

ac at last

Post by surya ss » Wed Jun 29, 2005 11:15 am

thanks for the help chunyi81
ac at last

I was wrong in making the level of the family tree
in this code :

Code: Select all

   for(i=0;i<jum;i++) 
      if(fam[i].parent) fam[i].n=fam[i].parent->n+1; 
I have change in recursive form and it got Ac
:)

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

Post by coldfire » Sun Apr 09, 2006 11:46 am

I keep getting WA with my NlogN algorithm.

I have some questions:

* Can a child have multiple parents?!
* What do we do with a blank line query or an incomplete line query? Ignore it or write 'no relation' ?

Any tricky test cases welcomed.

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

Post by coldfire » Sun Apr 09, 2006 12:49 pm

I finally got AC.

* Yes, a child can have multiple parents (That's why my LCA didn't work)
* There are no incorrect querys.

So because of multiple parents i changed the complexity of program to O(Querys * N).

gloriousjob
New poster
Posts: 1
Joined: Thu Oct 27, 2005 8:44 pm

Post by gloriousjob » Thu Apr 13, 2006 9:31 pm

Actually, my program only allows single parents and it got accepted. This statement in the problem spec clarifies that:

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

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

Post by 898989 » Thu Aug 24, 2006 12:53 am

In other threads they say two wrong things

1)That child may have more than one parent this is wrong
and my program ( using only two dimension arrays without building any tree or making recursive calls) is based on that only parent have many childers.

2)Also they said that there is empty lines...hmhmhm. :lol:

Finally i would like to thank the problemsetter 4 this nice problem.
Sleep enough after death, it is the time to work.
Mostafa Saad

Ron
Learning poster
Posts: 55
Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA

Re: 115 - Climbing Trees

Post by Ron » Fri May 30, 2008 11:04 pm

After a long time...finally i got accepted it.
My ac program doesn't allow multiple parents.

A valid input for this prob. -->>
  • 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
    v 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
my ac output :-->>
  • 2 cousin
    1 cousin removed 1
    great grand child
    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

llvllahsa
New poster
Posts: 2
Joined: Wed Dec 23, 2009 10:23 pm

Help please!!!

Post by llvllahsa » Wed Dec 23, 2009 10:29 pm

I also have problem with Climbing Trees!:(
for all the suggested testcases i produce a valid answer! but i can't find the bug!:(
the judge sends WA!

Can anyone help me please?!...

Code: Select all

import java.io.IOException;
import java.util.HashMap;
import java.util.StringTokenizer;

public class P115 {
	int[] parent;
	public static void main(String[] args) {
		int index = 1;
		HashMap hm = new HashMap();
		String line = ReadLn(100);
		StringTokenizer st = new StringTokenizer(line);
		P115 p = new P115();
		p.parent = new int[300];
		String[] words = new String[2];
		words[0] = st.nextToken();
		words[1] = st.nextToken();
		while (!words[0].equals("no.child")) {
			if (hm.get(words[0]) == null)
				hm.put(words[0], (Object) (Integer.valueOf(index++)));
			if (hm.get(words[1]) == null)
				hm.put(words[1], Integer.valueOf(index++));
			p.parent[((Integer) hm.get(words[0])).intValue()] = ((Integer) hm
					.get(words[1])).intValue();
			line = ReadLn(80);
			st = new StringTokenizer(line);
			words[0] = st.nextToken();
			words[1] = st.nextToken();
		}
		while ((line = ReadLn(100)) != null) {
			st=new StringTokenizer(line);
			words[0]=st.nextToken();
			words[1]=st.nextToken();
			int ind1 = -1;
			if (hm.get(words[0]) != null)
				ind1 = ((Integer) hm.get(words[0])).intValue();
			int ind2 = -1;
			if (hm.get(words[1]) != null)
				ind2 = ((Integer) hm.get(words[1])).intValue();

			if (ind1 != -1 && ind2 != -1) {
				int[] way1 = new int[index + 1000];
				int[] way2 = new int[index + 1000];
				p.dfsInstead(ind1, way1);
				p.dfsInstead(ind2, way2);
				int w1 = p.findlastIndex(way1);
				int w2 = p.findlastIndex(way2);
				/*
				 * int w1k=w1; int w2k=w2;
				 */
				int commonIndex = 0;
				if (way1[w1 - 1] != way2[w2 - 1]) {
					System.out.println("no relation");
				} else {
					while (w1 > 0 && w2 > 0 && way1[--w1] == way2[--w2]) {
						commonIndex++;
					}
					if (way1[w1 + 1] == way2[w2 + 1] && w1 == w2 && w1 == 0)
						System.out.println("sibling");
					else if (w2 == 1 && w1 == 0 && way2[w2] == way1[w1])
						System.out.println("parent");
					else if (w1 == 1 && w2 == 0 && way2[w2] == way1[w1])
						System.out.println("child");
					else if (w2 == 0 && way1[w1] == way2[w2]) {
						for (int i = 0; i < w1 - 2; i++) {
							System.out.print("great ");
						}
						System.out.println("grand child");
					} else if (w1 == 0 && way1[w1] == way2[w2]) {
						for (int i = 0; i < w2 - 2; i++) {
							System.out.print("great ");
						}
						System.out.println("grand parent");
					} else {
						System.out.print(Math.min(w1, w2) + " cousin");
						if (w1!=w2) {
							System.out.print(" removed " + (Math.abs(w1 - w2)));
						}
						System.out.println();
					}
				}
			} else {
				System.out.println("no relation");
			}
		}
	}

	int findlastIndex(int[] way) {
		int ind = 0;
		while (way[ind++] != 0)
			;
		return ind - 1;
	}

	void dfsInstead(int index, int[] array) {
		int d = 0;
		while (index != 0) {
			array[d++] = index;
			index = parent[index];
		}
	}

	static String ReadLn(int maxLg) // utility function to read from stdin
	{
		byte lin[] = new byte[maxLg];
		int lg = 0, car = -1;

		try {
			while (lg < maxLg) {
				car = System.in.read();
				if ((car < 0) || (car == '\n'))
					break;
				lin[lg++] += car;
			}
		} catch (IOException e) {
			return (null);
		}

		if ((car < 0) && (lg == 0))
			return (null); // eof
		return (new String(lin, 0, lg));
	}

}

llvllahsa
New poster
Posts: 2
Joined: Wed Dec 23, 2009 10:23 pm

Re: 115 - Climbing Trees

Post by llvllahsa » Wed Jan 06, 2010 6:34 pm

I got Accepted by increasing size of Arrays!!!!

at5anpo3
New poster
Posts: 7
Joined: Sun Apr 29, 2012 6:46 pm

Re: 115 - Climbing Trees

Post by at5anpo3 » Sun Apr 29, 2012 6:52 pm

Bringing in my small contribution for all the people who are getting WA at this problem.

- names can (and WILL) contain '-' character. Therefore '-' should not be considered a delimiter of names but rather a character just as 'a'...'z', '.' are. I found this the very hard way while scouting the internet for the original text of the problem at http://www.cs.duke.edu/courses/cps100/f ... amily.html (look for the link to http://www.cs.duke.edu/courses/cps100/f ... /family.in). Notice how there is a name "michael.ben-or". I simply assumed that this might be the case here and after that I got ACC.

- there is at least 1 child with more than 1 parent.

This should never happen.

Best Regards,
at5anpo3

Marcgal
New poster
Posts: 3
Joined: Tue Jul 02, 2013 6:19 pm

Re: 115 - Climbing Trees

Post by Marcgal » Tue Sep 29, 2015 1:23 am

OK, so now my small contribution to anyone who struggles with WA in this problem.

Contrary to what many people have claimed here, there are no nodes with more than one parent in the input. This has been confirmed with the following code. This input is, therefore, invalid:

Code: Select all

A B
A C
no.child no.parent
There are also no query pairs asking you to determine the relationship between two same elements, contrary to what some input examples might suggest. This has been confirmed with the following code. This input is, therefore, invalid:

Code: Select all

A B
no.child no.parent
A A
However, there are doubled parent-child pairs (i.e. two parent-child pairs that establish same relationship between two elements). This might have tricked some into believing that there may be nodes with two different parents. This has been confirmed with the following code. This input is, therefore, valid:

Code: Select all

A B
A B
no.child no.parent
A B
Also among the query pairs there are lines that contain "no.child" as their first component. This has been confirmed with the following code. Such lines are to be processed normally. This input is, therefore, valid:

Code: Select all

A B
no.child no.parent
no.child B
And the correct answer is

Code: Select all

no relation

Post Reply

Return to “Volume 1 (100-199)”