11175 - From D to E and Back

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

Moderator: Board moderators

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

11175 - From D to E and Back

Post by black.phoenix » Tue Feb 27, 2007 1:50 pm

Hello!!!

What Graph Theory must be used to solve this problem???

Thanks!!!
You do not know whether the path is easy or hard unless you walk through it.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Tue Feb 27, 2007 4:10 pm

You don't need special theory.

Hint:
Let N1 be a set of nodes that has edge to 1. For example, if there are edges (0, 1), (1, 1), (5, 1), N1 sould be {0, 1, 5}. So as N2, and more..
Think about the relation between Ni and Nj

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

Post by sclo » Tue Feb 27, 2007 9:24 pm

This problem is much easier IMO then the equivalent problem on undirected graphs. (Line graphs). I did use some datastructure to make it fasther though.

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

Post by black.phoenix » Wed Feb 28, 2007 8:58 pm

Sorry.... I didn't get the idea yet... could you give me some more hints???

Maybe I'm thinking about the problem in a wrong way.... take 3rd case:

4
3
0 1
2 1
2 3

Now draw a directed graph where it has nodes namely 0, 1, 2, 3 and making edges as arrows from 0 to 1, from 2 to 1 and from 2 to 3. This graph can be the lying graph from the undirected (or directed both ways) graph with nodes n0,n1,n2,n3,n4 where there's an edge called A between each nA,nA+1 and between the others vertices there's no edge.

I was thinking in this way, so for the 3rd case I thought the answer would be "Yes" as it's possible for E to be the lying graph of D the way I described above. But I'm wrong and I'd like to know the correct logic to solve this problem.

Waiting for you replies!!! :-)
You do not know whether the path is easy or hard unless you walk through it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Mar 01, 2007 5:30 am

black.phoenix wrote:Now draw a directed graph where it has nodes namely 0, 1, 2, 3 and making edges as arrows from 0 to 1, from 2 to 1 and from 2 to 3. This graph can be the lying graph from the undirected (or directed both ways) graph with nodes n0,n1,n2,n3,n4 where there's an edge called A between each nA,nA+1 and between the others vertices there's no edge.
How many directed edges does your graph D have?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

Post by black.phoenix » Thu Mar 01, 2007 4:49 pm

none... the graph is undirected (or directed both ways as I said)..... it's a simple graph with 5 vertices which contains four edges.... from v0 to v1 (edge0), from v1 to v2 (edge1), from v2 to v3 (edge2), from v3 to v4 (edge3).... from this graph I can draw E, following the logic from the problem statement, which gives the lying graph for the 3rd example..... but the answer is "No" :o
You do not know whether the path is easy or hard unless you walk through it.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Thu Mar 01, 2007 5:28 pm

But doesn't we require D to be a directed graph? I think that means all edges in D should be directed edges.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Mar 01, 2007 6:06 pm

In other words - if you treat those undirected edges as two directed ones, and then you follow the instructions from the problem statement, how many nodes will the lying graph have?

I guess I am overthinking this one - can this be solved by calculating the square root of the matrix (or - determining if one exists)?

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

Post by black.phoenix » Thu Mar 01, 2007 8:47 pm

I still don't understand this problem.... :cry:
You do not know whether the path is easy or hard unless you walk through it.

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

Post by sclo » Fri Mar 02, 2007 12:03 am

SPOILER:



DELETED
Last edited by sclo on Sat Mar 03, 2007 1:29 am, edited 1 time in total.

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Fri Mar 02, 2007 4:55 pm

The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Fri Mar 02, 2007 7:20 pm

Ivan wrote:The input data seem to be a bit weak.
I managed to accept a code which is obviously wrong on pretty simple
test cases.
Can you show me one of those simple test cases? Perhaps you are not using the fact that D is allowed to have self-loops and multiple edges?
If only I had as much free time as I did in college...

Ivan
New poster
Posts: 35
Joined: Thu Dec 29, 2005 1:00 pm
Location: Sofia, Bulgaria

Post by Ivan » Fri Mar 02, 2007 9:34 pm

I've got AC two programs - based on somewhat different logic.
For the case:
1
5
4
0 1
0 2
3 2
3 4
one outputs "yes", the other "no"...
Strange...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Fri Mar 02, 2007 9:49 pm

The answer should be No. Can you send me the one that says Yes? I'm curious to see how it managed to pass all the tests.
If only I had as much free time as I did in college...

black.phoenix
New poster
Posts: 8
Joined: Sun Aug 06, 2006 3:07 am

Post by black.phoenix » Sat Mar 03, 2007 1:04 am

Hello Abednego!!!

Could you give me a more detailed explanation on how to solve this problem??? I've read what sclo wrote but I didn't get the idea yet.

He treated a vertex in D as a pair (a,b) where a and b are its edges. But why if there's some directed edge from (a,b) to (c,d) in D guarantees that b=c is in D???

I'd like to know if you could also point out what I misunderstood about the problem from my last posts above.

Thanks!!!
You do not know whether the path is easy or hard unless you walk through it.

Post Reply

Return to “Volume 111 (11100-11199)”