599 - The Forrest for the Trees

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

Moderator: Board moderators

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

599 - The Forrest for the Trees

Post by Dominik Michniewski » Tue Jan 27, 2004 1:11 pm

I think that it's easy problem , but I got several WA's when I try to solve it.
I use DFS to count trees and acorns, but I could miss something. Could anyone help me and post some test cases ?

My algorithm is:
1. Read data
2. for every unvisited node
2.1. if node has no edges -> it's acorn
2.2. else run DFS and increase number of trees if this is a tree (is tree if when I run DFS from node x I cannot reach node y such that x >= y)

Is my algorithm wrong ? Could anyone help me ?

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jan 27, 2004 2:11 pm

Dominik,
I think your algo is correct.
What is the output for the following testcase?

Code: Select all

1
(A,B)
(B,C)
(B,D)
(D,E)
(F,G)
****
A,B,C,E
I don't know if there are such trickies, but my AC program deals with them.

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Jan 27, 2004 2:34 pm

My program outputs:
[c]There are 1 tree(s) and 0 acorn(s).[/c]
I assumed, that if I don't get node name in list, I don't check it (but I don't eliminate edges from the tree). I try to send code, where I ignore edges, which are concatenated with non-intresting nodes [means: not in list] but WA too)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Tue Jan 27, 2004 6:29 pm

Well, my program gives 1 tree & 1 acorn. I can't think of any more special cases, apart from the no edges, no nodes and no nodes&edges cases...

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jan 28, 2004 2:23 pm

I got Accepted on this problem.
I think, that input data contains incorrect test cases - graph with cycles and so on ...
My accepted solution counts this 'trees' and 'acorns'. But in my opinion is something wrong with this IO ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Aleksandrs Saveljevs
New poster
Posts: 39
Joined: Fri Nov 14, 2003 11:18 pm
Location: Riga, Latvia
Contact:

Post by Aleksandrs Saveljevs » Wed Jan 28, 2004 4:33 pm

The data set is OK, no illegal test cases.
You can mail me your old code, I'll tell you what was wrong. :wink:

Dominik Michniewski
Guru
Posts: 832
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Jan 29, 2004 9:02 am

Maybe I have a mistake on my code... I try to search 'backwards' in my codes ;-) and if I find incorrect program I send it to you :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Wed Feb 16, 2005 2:15 pm

To Dominik,
Do you please explain me how did you get accepted?
It seems to me very easy, but I got WA several times.
My algorithm is:
1.Read Data.
2.for each unvisited node I check is there any cycle exits with it

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Location: TORONTO, CANADA

Post by daveon » Fri Sep 16, 2005 12:29 pm

Hi,

I think the problem is in cycle detection. Try looking for cycle detection algorithms that use DFS and color nodes with WHITE,GREY,BLACK.

At least that was my mistake.
Cheers. :)

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

Post by RC's » Mon Jul 30, 2007 1:39 pm

I don't understand what you mean.
A tree must not contain a cycle, right ?
So you mean the graph contains a cycle ?
Please give me test cases, because I'm still confused about the right answer.

calicratis19
Learning poster
Posts: 76
Joined: Mon Jul 21, 2008 8:50 am
Location: SUST,SYLHET,BANGLADESH.
Contact:

why wa

Post by calicratis19 » Sat Aug 01, 2009 2:04 pm

deleted.
Heal The World

piyukr
New poster
Posts: 17
Joined: Sun Jan 26, 2014 10:35 am

599-The forest for the trees

Post by piyukr » Sat Mar 29, 2014 2:15 pm

here is the problem statement:http://uva.onlinejudge.org/index.php?op ... roblem=540


Can I solve it in this manner?
First count the no. of vertices and edges in the graph.
Then using a bitset of size 26 , mark the vertices which has at least one edge.let it be count(say).
In a graph with no cycles,
no. of connected components=no. of vertices - no. of edges
Therefore ,
no of acorns=v-count and
no of trees= no of connected components - no of acorns.

Is this method a correct way to solve this problem?

I tried it on various test inputs and found it to be working well . However, my code for this got WA . code :http://ideone.com/jHvdzn

If the above method is correct can someone please help me debug the code?
Thank you.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 599-The forest for the trees

Post by brianfry713 » Mon Mar 31, 2014 10:43 pm

acorn not acron
Check input and AC output for thousands of problems on uDebug!

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 599-The forest for the trees

Post by vsha041 » Thu Apr 03, 2014 12:10 pm

brianfry713 wrote:acorn not acron
That was nice ! Attention to detail ! Sometimes I use windiff to compare sample output with my output just to catch these kind of "eye tricking" errors.

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 599-The forest for the trees

Post by apcastelein » Mon Jul 28, 2014 3:59 pm

I'm having an issue with my code. It works for the sample input but I get RE when submitting

Code: Select all

#include <stdio.h>
#include <map>
#include <vector>

using namespace std;

typedef vector<int> vi;

class UnionFind{
	private: 
		vi p,rank;
		int singles, sets;
	public: 
		UnionFind(int N){
			singles=sets=N;
			rank.assign(N,0);
			p.assign(N,0);
			for(int i=0;i<N;i++)
				p[i]=i;
		}
		int findSet(int i){
			return (p[i]==i) ? i : (p[i]=findSet(p[i]));
		}
		bool isSameSet(int i,int j){
			return findSet(i)==findSet(j);
		}
		void unionSet(int i,int j){
			if(!isSameSet(i,j)){
				int x=findSet(i), y=findSet(j);
				sets--;
				if(rank[x]==0)
					singles--;
				if(rank[y]==0)
					singles--;
				if(rank[x]>rank[y]) 
					p[y]=x;
				else{
					p[x]=y;
					if(rank[x]==rank[y]) rank[y]++;
				}
			}
		}
		int getSingles(){
			return singles;
		}
		int getSets(){
			return sets;
		}
};

int main(){
	int TC, E, V, trees, acorns;
	char from[26],to[26],t;
	map<char,int> m;
	scanf("%d",&TC);
	while(TC--){
		E=0;
		m.clear();
		//scan in edges
		while(scanf(" (%c,%c)",&from[E],&to[E])==2)
			E++;
		//scan in vertices
		V=0;
		scanf("%s");
		scanf(" %c",&t);
		m[t]=V;
		V++;
		while(scanf(",%c",&t)==1){
			m[t]=V;
			V++;
		}
		//UFDS
		UnionFind* U=new UnionFind(V);
		for(int i=0;i<E;i++)
			U->unionSet(m[from[i]],m[to[i]]);
		acorns=U->getSingles();
		trees=(U->getSets())-acorns;
		printf("There are %d tree(s)  and %d acorn(s).\n",trees,acorns);
	}
	return 0;
}
I was trying to some test input and

Code: Select all

1
(A,B)
(A,C)
...
(A,V)
****
A,B,C,...,Z
works fine but

Code: Select all

1
(A,B)
(A,C)
...
(A,W)
****
A,B,C,...,Z
Gives me a very wierd error where the TC variable is somehow reset to 42 and it gives me 42 results with all but the first being 0 trees, 1 acorn

Post Reply

Return to “Volume 5 (500-599)”