10227 - Forests

[Shahid]

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.

[Adrian Kuegel]

Did you consider that this problem has multiple input?
And what about this input:
4 5
1 1
1 2
2 1
2 2

Output is 2.

[Shahid]

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]

The second opinion comes from persons 3 and 4, who don't hear any trees fall.

Stefan

[Shahid]

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]

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]

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]

I simply can

[Rajib]

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

Hope it will help you. Good luck

[sclo]

This problem is absolutely trivial if you use stl set in C++. I finished coding it in 2 mins and got AC

[sclo]

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]

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]

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]

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]

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.