## 11131 - Close Relatives

Moderator: Board moderators

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

### 11131 - Close Relatives

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
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
-> 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
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;
}

{
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)
{
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
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
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
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?

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:
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
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).

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

### Re: 11131 Close Relatives

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
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.