## 10227 - Forests

Moderator: Board moderators

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:

### 10227 - Forests

i tried to solve that problem,
i matched all the sample output and input,

and it also works for the sample test cases that i made.

is there any inner trick, then plz let me know. thanx in advance.

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Did you consider that this problem has multiple input?
4 5
1 1
1 2
2 1
2 2

Output is 2.

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
hi, thanx for ur reply. Quoting from the problem ---------
People may have different opinions as to which trees, according to Berkeley, have made a sound. How many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees.

ur sample input is:
4 5
1 1
1 2
2 1
2 2
and output is: 2
but how?

cauze here people 1 hear the sound of tree 1,2
and people 2 also hear the sound of tree 1, 2

so as both of them hear the same set of tree
so just only one opinion holds.
So the output should be: 1

plz explain the matter.

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
The second opinion comes from persons 3 and 4, who don't hear any trees fall.

Stefan

Shahid
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Contact:
thanx pochmann.

i totally missed about the cases who doesn't hear anything.

but can someone explain me, the matter of multiple input? how should one tackle the problems of multiple input?
thanx.

pochmann
New poster
Posts: 28
Joined: Sat Jan 26, 2002 2:00 am
Contact:
In multiple input the different testcases are separated by an empty line. I'd suggest reading line after line with gets(...) and analyzing them with sscanf(...).

char line[100];
int a, b;
while( gets( line ) && sscanf( line, "%d%d", &a, &b ) == 2 ){
...
}

Stefan

crashzero
New poster
Posts: 4
Joined: Thu Oct 10, 2002 8:11 pm

### 10227 Forests

its possivel this kind of input data

1

3 4

if yes what is the result? (0??)

1

3 4
0 0

if yes what is the result?

2

3 4

if yes what is the result (2 zeros or 1 zero?)

crashzero
New poster
Posts: 4
Joined: Thu Oct 10, 2002 8:11 pm

### 10227 !HELP!

I simply can

Rajib
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am

### I/O For u...

It is a very beautiful problem. You have to be careful about problem statements all the time.

INPUT:
2

100 5
1 1
2 2
3 3
4 1
5 2
6 3

0 0
Output:
4

0

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
This problem is absolutely trivial if you use stl set in C++. I finished coding it in 2 mins and got AC

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
I've got AC and here's the answers:
its possivel this kind of input data

1

3 4

if yes what is the result? (0??)
No, the result should be 1, since all 3 people heard exactly no trees fell, their opinion would be the same, so there's only 1 set of opinion.
1

3 4
0 0

if yes what is the result?
This is not valid input data, since both i,j are numbered from 1

2

3 4

if yes what is the result (2 zeros or 1 zero?)
This set of data is not valid, since the first line of each test case must have P and T

rmotome
New poster
Posts: 14
Joined: Mon Jan 10, 2005 12:20 pm

### wooooooowwwwwwwwww! what the hell?

1,2,3 hold the same opinions as 4,5 and 6 respectively this makes 3 opinions in total not 4. Is there something I am missing? I have read the problem statement many times

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 10227 - Forests

i stored the trees for each person and then join the people if the trees are the same.

it is of the order (P*P*T) . Does anyone have it better than this ? what is the idea.

other approach
arr of STL sets
even i store the trees for each person in a set ( and then compare the sets for each person i and j and put them in a people set if they are same ).

Anyone have better solution or faster one ?

kmh4500
New poster
Posts: 3
Joined: Sun Oct 26, 2008 12:30 am

### Re: 10227 - Forests

Hint for fast one : q-sort

int q_recur(int st, int ed,int p)
part a=q_recur(st,j,p+1);
part b=q_recur(j+1,ed,p+1);

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 10227 - Forests

I am getting Wrong answer continuously. I can't think of any possible cases for which my code would fail. Can some one please help me and post some input/outputs on the board? Thanks in advance for the help.
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson