117 - The Postal Worker Rings Once

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

Moderator: Board moderators

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

117 - The Postal Worker Rings Once

Post by bugzpodder » Sat Jul 12, 2003 5:05 am

my logic is as follows:
find the sum of all path
if there are no nodes with odd degree, output the sum
otherwise if there is one exactly (so far i am at a loss to see how this is possible, please enlighten me) output sum + minimum distance from one of its neighbours to it.
otherwise if there are two exactly, output sum+shortest distance between the two. i used dijkstra's algorithm for the sssp.

i got WA, any tricks that i should be aware of?
Last edited by bugzpodder on Sun Jul 13, 2003 12:08 am, edited 1 time in total.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

117 Good idea.

Post by Ryan Pai » Sat Jul 12, 2003 9:16 am

Euler (Yes, the same as the one mentioned in the background) proved a theorem about graphs. And it's one that any computer scientist could prove with a little graph theory and much thought (the amazing thing is that Euler proved it without having any graph theory, for he was the one to invent it).

It goes like this: In a undirected graph there is an Euler Path (one that crosses each edge once and only once) iff there are at most two nodes with odd degree (Isn't it lucky the problem writers decided to give these exact conditions?)

So, lets consider the possibilities:

0 nodes of odd degree: In this case, the start node can very well serve as the end node, so the path is just all the edges.

1 node of odd degree: This can never happen. It can be proved by induction if you want, the key thing to notice is that if a graph with N edges can never have an odd number of nodes with odd degree, then that forces a graph with N+1 edges to carry on the property.

2 nodes of odd degree: In this case, the Euler path starts from one of the odd degree nodes and finishes in the second. So you have to start in the first, go through all the edges to get to the second, and then get back to the first as quick as possible.

In short, you were going about it the right way. You might want to veryify your dijkstra's. I would even go so far as to reccomend using a different shortest path algorithm, bellman ford, although slower mathematically, is easier to write (and for large such a small graph, it doesn't matter anyways).

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jul 12, 2003 4:02 pm

Dijkstra isn't that hard if you use template class priority_queue provided in STL (C++).

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:

Post by Ryan Pai » Sat Jul 12, 2003 5:28 pm

Except that the priority_queue doesn't have an update operation, so you lose the efficiency that dijkstra's provides. Ways to work around that would be to use the make_heap and then just write a little fix_heap operation, or perhaps do some wacky stuff with multisets.

Any way you slice it, it's not as easy to write as four for loops and a single statement.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jul 12, 2003 6:09 pm

What do you want do use update operation for? All you need is push and top/pop (get/erase minimum) working in O(log n). How can one lose the efficiency here?

Of course you're right that there is no way to fit it in a few lines, but even 20-30 lines aren't that much if you know and feel what you write. And it's good to practice some algorithms in relatively easy tasks from Valladolid to code them faster in future.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sat Jul 12, 2003 7:45 pm

I used cin.eof() to check for no more test cases but apparently i forgot to get the last space and newline character ! i fixed it now. Thanks all!

anywayz I've never used priority_queue with Dijkstra before. I am gonna try it now :D so what do i do? push the distance to the source node in the priority_queues, and do top/pop every time? but how do you update the distances to the source node since they are in the priority_queue?? your help is appreciated.

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Jul 12, 2003 10:29 pm

I assume that nodes are somehow indexed by integers.

For every node you keep (for instance, in an extra boolean array) if it is "fixed".

Lets choose one of the given nodes as the starting one. At the very begining only it is fixed.

If p is a pair of integers, then p.first is length of a path from starting node to node of index p.second. We will keep such pairs in priority_queue of integer pairs (priority_queue<pair<int,int> >). At the begining only the neighbours of the starting node will be there with appropriate distances
.
In each step we will take the node which is closest to the starting node. If already has been fixed, nothing happens.
If it wasn't, then it is. In that case we put all its neighbours into the queue with distances from the starting node equal to the sum of distances from starting one to the one just popped and from it to the neighbour currently visited (we don't care if that neighbour already has been pushed to the queue).
When we pop the node that we are to find the shortest path from the starting one we can stop and return the length of the path.

Few remarks: priority_queue always returns the biggest element. You can define your own comparating funtion or you can simply multiply the path length by -1.

I highly recommend you web page [url]http://www.sgi.com/tech/stl/[/url] if you have any doubts while using STL.

If that wasn't clear maby my code will be helpful

[cpp]
//graph is a class
int graph::shortest_path(int a, int b)
{
bool visited[26];for(int i=0;i<26;i++)visited[i]=false;
visited[a]=true;
priority_queue<pair <int, int> > q;
pair<int, int> p,t;
list<pair <int, int> >::iterator it=tab[a].neighbours.begin();
while(it!=tab[a].neighbours.end())
{
p.first=(-1)*it->second;p.second=(it++)->first;
q.push(p);
}
p=q.top();q.pop();
while(p.second!=b)
{
if(!visited[p.second])
{
visited[p.second]=true;
it=tab[p.second].neighbours.begin();
while(it!=tab[p.second].neighbours.end())
{
if(!visited[it->first])
{
t.first=p.first-(it->second);
t.second=it->first;
q.push(t);
}
it++;
}
}
p=q.top();
q.pop();
}
return p.first;
}
[/cpp]

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

Post by bugzpodder » Sun Jul 13, 2003 12:06 am

interesting, using -1*weight to have the priority_queue sorting the pair the way it is suppose to! thx for the code

[cpp]//graph is a class
int graph::shortest_path(int a, int b)
{
bool visited[26];for(int i=0;i<26;i++)visited=false;
visited[a]=true;
priority_queue<pair <int, int> > q;
pair<int, int> p,t;
list<pair <int, int> >::iterator it=tab[a].neighbours.begin();
while(it!=tab[a].neighbours.end())
{
p.first=(-1)*it->second;p.second=(it++)->first;
q.push(p);
}
p=q.top();q.pop();
while(p.second!=b)
{
if(!visited[p.second])
{
visited[p.second]=true;
it=tab[p.second].neighbours.begin();
while(it!=tab[p.second].neighbours.end())
{
if(!visited[it->first])
{
t.first=p.first-(it->second);
t.second=it->first;
q.push(t);
}
it++;
}
}
p=q.top();
q.pop();
}
return p.first;
} [/cpp][/cpp]

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 8:34 pm

Hey guys. I need your help.

I am missing the logic here, I believe. I calculated the sum of all edges, that is pretty easy.

Then, I implemented Bellman-Ford to find the shortest path. I'm pretty sure it is correct, since I've tried it on a couple of graphs.

But when I add the sum of edges with the shortest path the number is too big.

For example, the sum of all the edges in input sample #2 is 106.
The shortest path between the two odd nodes is (numbered in order that they appear in the input) 2->9->7->8->11. Which, represented by letters is d->e->y->k->s.

The weight of the shortest path is 19 (4+5+4+6). So, the final answer is 106+19 which is > the sample output.

So what am I doing wrong?

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 8:37 pm

Hey guys. I need your help.

I am missing the logic here, I believe. I calculated the sum of all edges, that is pretty easy.

Then, I implemented Bellman-Ford to find the shortest path. I'm pretty sure it is correct, since I've tried it on a couple of graphs.

But when I add the sum of edges with the shortest path the number is too big.

For example, the sum of all the edges in input sample #2 is 106.
The shortest path between the two odd nodes is (numbered in order that they appear in the input) 2->9->7->8->11. Which, represented by letters is d->e->y->k->s.

The weight of the shortest path is 19 (4+5+4+6). So, the final answer is 106+19 which is > the sample output.

So what am I doing wrong?

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Thu Aug 21, 2003 8:42 pm

The sum of the shortest path is indeed 19. However, the sum of all the edges in the second sample input is 95, not 106.

Since the difference between 106 and 95 is 9 .. and the sum of the edges in the first graph is 9, you are probably not clearing the edges for each new test case.

xbeanx
Experienced poster
Posts: 114
Joined: Wed Jul 30, 2003 10:30 pm
Location: Newfoundland, Canada (St. John's)

Post by xbeanx » Thu Aug 21, 2003 10:24 pm

HeHeH. You know, I figured that out about 5 seconds after I posted that last message. I feel like an idiot. :)

Thanks U-Man.

User avatar
ezra
New poster
Posts: 31
Joined: Thu Nov 21, 2002 2:11 pm

Post by ezra » Mon Aug 25, 2003 6:29 pm

i use DFS recursive to find the shortest path between the odd degree nodes just for simplicity but i think dijkstra is so much better for speed.

symme7ry
New poster
Posts: 7
Joined: Fri Aug 22, 2003 10:23 am

Post by symme7ry » Sat Sep 20, 2003 8:59 am

IMO, floyd warshall is the best algorithm to use here. It's easier to type in than any of the sinle souce shortest path algorithms, and it is fast enough.

rafi7
New poster
Posts: 1
Joined: Thu Oct 30, 2003 11:25 am

Please help me on 117

Post by rafi7 » Fri Oct 31, 2003 9:47 am

I implemented both algorithms: Bellman-Ford and Dijkstra. I works perfectly on example provided, bud and I get WA.

I know it's my bug, but can't find it.

Does anyone have test inputs for 117? I'm interested in results too...

Post Reply

Return to “Volume 1 (100-199)”