Page 1 of 1
359 - Sex Assignments And Breeding Experiments
Posted: Mon Feb 09, 2004 1:17 pm
by junbin
I'm trying to solve q359 Sex Assignments And Breeding Experiments and keep getting WA.
I need to clarify some doubts:
1) As long as there are no vertical cycles in the graph, ie: node A is not the ancestor of itself, and there is a valid male/female assignment, then the graph is sexy.
2) A node can "mate" with any other node, even it's own descendent (ie: A is the parent of B, B is the parent of C, and A can "mate" with C to produce D)
3) A node can have either 0, 1 or 2 parents, no more.
I know only Per, Adrian and Joey has solved this question, so I'm hoping one of them will be nice and help me answer my queries as well as test the following test data
input:
Code: Select all
5 6
1 3
2 3
1 4
2 4
1 5
2 5
3 3
1 2
2 3
3 1
8 8
1 5
2 5
2 6
3 6
3 7
4 7
2 8
4 8
7 6
1 5
2 5
2 6
3 6
3 7
4 7
8 9
4 3
3 1
3 2
4 5
4 6
3 7
8 1
8 2
8 5
13 13
5 6
1 6
1 2
2 3
3 4
2 7
3 9
9 13
10 13
10 12
8 10
8 11
6 8
13 14
5 6
1 6
1 2
2 3
3 4
2 7
3 9
9 13
10 13
10 12
8 10
8 11
6 8
13 9
9 13
1 3
1 4
2 4
3 9
3 5
4 5
4 7
5 6
6 8
7 8
8 9
3 6
5 7
9 13
1 3
1 4
2 4
3 9
3 5
4 5
4 7
5 6
6 8
7 8
8 9
3 6
5 8
my output:
Code: Select all
Graph number 1 is sexy
Graph number 2 is not sexy
Graph number 3 is not sexy
Graph number 4 is sexy
Graph number 5 is sexy
Graph number 6 is sexy
Graph number 7 is not sexy
Graph number 8 is not sexy
Graph number 9 is not sexy
Posted: Mon Feb 09, 2004 2:25 pm
by Per
Hi!
Here are some answers:
1) ...and as long as noone has more than two parents, yes.
2) Yes.
3) Only in order for the graph to be sexy, the input doesn't have that restriction.
Your I/O is correct.
Posted: Mon Feb 09, 2004 4:27 pm
by junbin
Per wrote:Hi!
Here are some answers:
1) ...and as long as noone has more than two parents, yes.
2) Yes.
3) Only in order for the graph to be sexy, the input doesn't have that restriction.
Your I/O is correct.
I don't understand.. my code churns out the right output for all possibilies.. and I reserve enough memory space for 23000 nodes which is definitely more than enogh (I tested the judge for this).. but still WA.
This is getting very perplexing..
Does anyone have any extra special test cases they can send my way please?
Posted: Tue Feb 10, 2004 1:05 am
by Per
I don't think the input contains any especially tricky cases... I even stopped myself from including a graph with 0 vertices (which shouldn't be a problem, but anyway...).
If you want, you can send me your code and I'll check it.
Btw, what do you mean by "vertical" cycles? Are they any different from regular cycles?
Posted: Tue Feb 10, 2004 6:08 am
by junbin
Per wrote:I don't think the input contains any especially tricky cases... I even stopped myself from including a graph with 0 vertices (which shouldn't be a problem, but anyway...).
If you want, you can send me your code and I'll check it.
Btw, what do you mean by "vertical" cycles? Are they any different from regular cycles?
If I'm not wrong, in this problem, regular cycles are allowed. In other words, the graph is not a tree as we know it in computer science (acyclic).
A simple example:
A gives birth to B and C
B and C gives birth to D
A and E gives birth to E
This graph is clearly sexy (A - male, B- male, C - female, D - female, E - irrelevant).
This graph also contains regular cycles (A - B - D - C - A OR A - E - D - B - A, etc.)
A "vertical" cycle is one where by only travelling either up or down (vertically), you can get back to yourself.
eg:
A gives birth to B and C
B and C gives birth to D
D gives birth to A
from A, we move up to D, then up to either B or C and then we can get back to A (by moving up).
OR
from B, we move down to D and then down to A and then down to B.
ps: I'll send you my code when I get home tonight..
Posted: Tue Feb 10, 2004 9:56 am
by Per
Ah, OK. Since I consider the graph as being directed, it becomes regular cycles to me.
For directed graphs, being acyclic is not the same as being a tree.
But I think the term vertical cycle and its description is somewhat confusing, since it depends on how you draw the graphs.
Posted: Sat Nov 13, 2004 4:32 am
by sidky
Here's how i solved:
1. I treated the input as a directed graph. First, I checked if any node's indegree is greater than 2.
2. Then i checked, if there is any cycle in the graph.
3. Then i made another graph, where each edge represented the parents of a node. the edges are undirected. I checked whether the second graph is bicolourable. If it is, the graph is sexy.
but i received WA. is my method wrong, or am I missing something?
thanks in advance.
Posted: Thu Feb 10, 2005 7:23 pm
by Larry
I don't think it has to be bicolorable:
AB -> C
AC -> E
Thus, A is the parent and grandparent of E...
Posted: Fri Feb 11, 2005 12:24 am
by Christian Schuster
The original directed "parent graph" does not need to be bipartite (or bicolorable, however you call it), but the undirected "mate graph" must be, since no two mates may be of the same sex.
The mate graph for Larry's example contains only the edges AB and AC, and it is bipartite.
Posted: Sat Jun 18, 2005 6:13 am
by sidky
Thanx everybody. I got AC.
Posted: Fri Apr 14, 2006 7:19 pm
by ardiankp
Hi, anybody has more sample I/O?
I tried many I/O, my program solved them all, but still got wrong answer..
I used the same method as described here.
In checking for cycle, I did eliminate nodes which has 0 in-degrees continuously. If all nodes are eliminated, then there's no cycle.
In checking for bipartite, I just use standard DFS..
Did I miss something?
Usually I don't like people posting codes, but I might do that here.. a bit frustated
Posted: Sun Apr 23, 2006 5:49 pm
by mf
Watch out -- there are repeated edges in the input!
It seems, that if the same pair x, y appears multiple times, in order to get AC, you should output that the graph is not sexy.
Posted: Mon Apr 24, 2006 7:40 pm
by ardiankp
LOL.. yes, that makes me get WA.. now got ACC. Thanks.
Initially I just ignore multiple edges.. if you said X is parent of Y, then you said it again.. then it is no problem, right? :S
Thanks a million