11131 - Close Relatives

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

Moderator: Board moderators

Post Reply
taha
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

11131 - Close Relatives

Post by taha » Mon Oct 23, 2006 10:19 am

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 ??

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Oct 23, 2006 11:20 am

-> 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
New poster
Posts: 12
Joined: Mon Oct 31, 2005 10:17 am
Location: Egypt

Post by taha » Mon Oct 23, 2006 11:33 am

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;
}

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 23, 2006 4:41 pm

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?
Daniel
UFRN HDD-1
Brasil

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Oct 23, 2006 10:51 pm

danielrocha wrote: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?

User avatar
danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha » Mon Oct 23, 2006 11:01 pm

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]
Daniel
UFRN HDD-1
Brasil

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Oct 23, 2006 11:16 pm

danielrocha wrote: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).

User avatar
fh
Learning poster
Posts: 59
Joined: Wed Jan 19, 2005 3:24 pm
Location: Jakarta
Contact:

Re: 11131 Close Relatives

Post by fh » Fri Oct 27, 2006 10:50 am

taha wrote: 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'.
Visit my script to hunt UVA problem here:
http://felix-halim.net/uva/hunting/
-----------------------
Felix Halim

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Fri Oct 27, 2006 7:09 pm

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.

Post Reply

Return to “Volume 111 (11100-11199)”