## 359 - Sex Assignments And Breeding Experiments

Moderator: Board moderators

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am

### 359 - Sex Assignments And Breeding Experiments

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
``````

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
Hi!

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.

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
Per wrote:Hi!

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.

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?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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?

junbin
Experienced poster
Posts: 174
Joined: Mon Dec 08, 2003 10:41 am
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..

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
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?

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I don't think it has to be bicolorable:

AB -> C
AC -> E

Thus, A is the parent and grandparent of E...

Christian Schuster
Learning poster
Posts: 63
Joined: Thu Apr 04, 2002 2:00 am
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.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:
Thanx everybody. I got AC.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.

ardiankp
New poster
Posts: 27
Joined: Mon Nov 01, 2004 4:04 pm
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