359 - Sex Assignments And Breeding Experiments

[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

[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.

[junbin]

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?

[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?

[junbin]

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]

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]

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.

[Larry]

I don't think it has to be bicolorable:

AB -> C
AC -> E

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

[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.

[sidky]

Thanx everybody. I got AC.

[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

[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.

[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