115 - Climbing Trees

[wsarzynski]

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

[Solaris]

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]

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

here is my code

Code: Select all

AC

[chunyi81]

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]

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]

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]

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]

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]

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]

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.

Finally i would like to thank the problemsetter 4 this nice problem.

[Ron]

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]

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]

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

[at5anpo3]

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]

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