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?
117 - The Postal Worker Rings Once
Moderator: Board moderators
-
bugzpodder
- Experienced poster
- Posts: 147
- Joined: Fri Jun 13, 2003 10:46 pm
117 - The Postal Worker Rings Once
Last edited by bugzpodder on Sun Jul 13, 2003 12:08 am, edited 1 time in total.
117 Good idea.
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).
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).
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
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.
Any way you slice it, it's not as easy to write as four for loops and a single statement.
-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
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.
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
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
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.
anywayz I've never used priority_queue with Dijkstra before. I am gonna try it now
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.-
Krzysztof Duleba
- Guru
- Posts: 584
- Joined: Thu Jun 19, 2003 3:48 am
- Location: Sanok, Poland
- Contact:
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]
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
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]
[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)
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?
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)
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?
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?
Please help me on 117
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...
I know it's my bug, but can't find it.
Does anyone have test inputs for 117? I'm interested in results too...