10227 - Forests

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

Moderator: Board moderators

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

10227 - Forests

Post by Shahid » Sun Feb 17, 2002 1:57 pm

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
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sun Feb 17, 2002 3:00 pm

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
Learning poster
Posts: 68
Joined: Fri Oct 26, 2001 2:00 am
Location: Dhaka, Bangladesh
Contact:

Post by Shahid » Fri Feb 22, 2002 12:32 pm

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:

Post by pochmann » Sat Feb 23, 2002 3:31 am

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
Location: Dhaka, Bangladesh
Contact:

Post by Shahid » Sun Feb 24, 2002 12:05 pm

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:

Post by pochmann » Sun Feb 24, 2002 12:33 pm

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

Post by crashzero » Fri Oct 11, 2002 12:42 pm

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!

Post by crashzero » Mon Oct 14, 2002 9:41 am

I simply can

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

I/O For u...

Post by Rajib » Tue Nov 09, 2004 3:59 pm

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 :lol:

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 9:57 am

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
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Mon Feb 13, 2006 10:05 am

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
Location: Kitchener, Ontario, Canada

wooooooowwwwwwwwww! what the hell?

Post by rmotome » Wed Aug 16, 2006 6:12 am

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

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

Re: 10227 - Forests

Post by tryit1 » Tue Sep 02, 2008 7:22 pm

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

Post by kmh4500 » Sun Jan 25, 2009 10:06 am

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

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

Re: 10227 - Forests

Post by plamplam » Thu Oct 13, 2011 11:10 pm

I am getting Wrong answer continuously. I can't think of any possible cases for which my code would fail. :x 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

Post Reply

Return to “Volume 102 (10200-10299)”