11131 - Close Relatives

[taha]

I am getting Wrong Answer, so i want to make sure of some issues:

- Is it only one input set ??
- My splution is as follows:

I buid a tree rooted by the first person that appears in the input and traverse this tree, once right to left and once left to right. If the 2 traversals give the same result then we have only 1 listing, otherwise we have 2 listings as the solution, is that right ??

-Any other special cases ??

[sohel]

-> Yes, only 1 input set.

-> Yes, your method is correct. I used the same approach to get Aced in the contest.

--> special case : there might be spaces within a name.

[taha]

Well i cannot find why this does not work.

Code: Select all

FILE *in = stdin;


vector<string> tokenize(string s, string ch) { 
  vector<string> ret; 
  for( int i = 0, j; i < s.size(); i = j+1 ) { 
    j = s.find_first_of(ch, i); 
    if( j == -1 ) j = s.size(); 
    if( j-i > 0 ) ret.push_back( s.substr(i, j-i) ); 
  } 
  return ret; 
} 

string readline()
{
	char ch;
	string ret;

	while(fscanf(in,"%c",&ch)!=EOF)
	{
		if(ch=='\n') return ret;
		ret+=ch;
	}

	return ret;
}


class node { public:
vi a;
string name;
};


map<string,int> p;
node z[6000];

void solve(int turn)
{
	int i;
	fo(i,z[turn].a.size())
		solve(z[turn].a[i]);

	printf("%s\n",z[turn].name.c_str());
}

void solve2(int turn)
{
	int i;
	for(i=z[turn].a.size()-1 ; i>=0 ; i--)
		solve(z[turn].a[i]);

	printf("%s\n",z[turn].name.c_str());
}

int main()
{
	int i,n,k=0,flag=0;	
	string s;
	vs v;
	char ch;

	fo(i,6000)
		z[i].a.clear();
	
	while(1)
	{
		s=readline();
		if(s.size()==0) break;

		v=tokenize(s,",");
		
		fo(i,v.size())
			if(p.find(v[i])==p.end())
			{
				z[k].name=v[i];
				p[v[i]]=k++;
			}

		for(i=1 ; i<v.size() ; i++)
			z[p[v[0]]].a.push_back(p[v[i]]);			
	}

	fo(i,6000)
		if(z[i].a.size()>1)
			flag=1;

	if(flag)
	{
		printf("2\n\n");
		solve(0);
		printf("\n");
		solve2(0);
	}

	else
	{
		printf("1\n\n");
		solve(0);
	}

	return 0;
}

[danielrocha]

I'm having a really hard time understanding this problem's statement. I've re-read it some times and I still haven't figured it out. Could some one please try to explain it here?

[Per]

I'm having a really hard time understanding this problem's statement. I've re-read it some times and I still haven't figured it out. Could some one please try to explain it here?

Which part of the problem statement are you having trouble with?

[danielrocha]

I'm sorry. I've re-re-read the problem statement, and it's getting clearer. So I'm suppose to give the minimum amount of lists that would allow the unambiguous reconstruction of the tree?[/list][/quote]

[Per]

I'm sorry. I've re-re-read the problem statement, and it's getting clearer. So I'm suppose to give the minimum amount of lists that would allow the unambiguous reconstruction of the tree?[/list]

Yes. Note that any set of lists you give will either uniquely define a tree or be invalid because it defines a general DAG rather than a tree -- i.e. it defines someone to have several children (which I guess you could view as an ambiguity).

[fh]

I buid a tree rooted by the first person that appears in the input and traverse this tree, once right to left and once left to right. If the 2 traversals give the same result then we have only 1 listing, otherwise we have 2 listings as the solution, is that right ??

-Any other special cases ??

Mine is always print 2 ways of listing using post order traversal and got AC.

The problem statement didn't mention what is 'm' means! Are we supposed to be guess it? So my experiments above shows that the judge output is always 2 (or is it because of the single data only)?

IMHO, the problem is not very clear on 'm'.

[sohel]

Yes, it is because there is only one case in the judge data.

Number of lists will be 1 if degrees of all the vertex is at most 1.
So just printing 2 blindly would have resulted in WA, had there been more than one case.