## 117 - The Postal Worker Rings Once

Moderator: Board moderators

ani_mitr86
New poster
Posts: 20
Joined: Mon May 28, 2007 4:36 pm
Location: India

### Re: confused by statesments of prob117

here is the code

#include<cstdio>
#include<cstring>
//#include<conio.h>

#define MAX 'z'
#define MIN 'a'
#define INFINITY 20000000000000000LL

typedef int vertex;

struct edge{
vertex u, v;
};

void bellman_ford(vertex source, long long* dist, edge* list, int* wt, int sz){
for(vertex i=MIN; i<=MAX; i++) dist=INFINITY;
dist[source]=0;
for(vertex i=MIN; i<MAX; i++) for(int j=0; j<sz; j++)
if(dist[list[j].v]>dist[list[j].u]+wt[j]) dist[list[j].v]=dist[list[j].u]+wt[j];
return;
}

int eulerian(edge* list,int* wt, int sz){
int deg[MAX+1];
memset(deg, 0, sizeof(deg));
for(vertex i=0; i<sz; i++){ deg[list.u]++; deg[list.v]++;}
vertex start=0, end=0, i;
for(i=MIN; i<=MAX; i++) if(deg%2==1){ start=i; break;}
for(i=i+1; i<=MAX; i++) if(deg%2==1){ end=i; break;}
if(start!=end){
long long dist[MAX+1];
bellman_ford(start, dist, list, wt, sz);
return (int)dist[end];
}
return 0;
}

void make_set(vertex v, vertex* pre, int* rank){
pre[v]=v;
rank[v]=0;
return;
}

vertex find(vertex v, vertex* pre, int* rank){
if(v!=pre[v]) pre[v]=find(pre[v], pre, rank);
return pre[v];
}

void set_union(vertex u, vertex v, vertex* pre, int* rank){
vertex pre_u=find(u, pre, rank), pre_v=find(v, pre, rank);
if(pre_u==pre_v) return;
if(rank[pre_u]>rank[pre_v]) pre[pre_v]=pre_u;
else{
pre[pre_u]=pre_v;
if(rank[pre_u]==rank[pre_v]) rank[pre_v]++;
}
return;
}

bool is_connected(edge* list, int sz, vertex* pre, int* rank){
for(vertex i=MIN; i<=MAX; i++) make_set(i, pre, rank);
bool visit[MAX+1];
for(vertex i=MIN; i<=MAX; i++) visit=false;
for(int i=0; i<sz; i++){
set_union(list.u, list.v, pre, rank);
visit[list.u]=true;
visit[list.v]=true;
}
vertex root=find(list.u, pre, rank);
for(vertex i=MIN; i<=MAX; i++) if(visit[i] && find(i, pre, rank)!=root) return false;
return true;
}

int main(){
//freopen("input.txt", "r", stdin);
char* a;
edge list;
int wt, pre[MAX+1], rank[MAX+1];
int total=0, sz=0;
while(scanf("%s", a)!=EOF){
// if(!is_connected(list, sz, pre, rank)) total/0;
printf("%d\n", total+eulerian(list, wt, sz)); total=0; sz=0;}
else{
wt[sz]=strlen(a);
total+=wt[sz];
list[sz].u=a; list[sz].v=a[wt[sz]-1]; sz++;
}
}
//getch();
return 0;
}

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: confused by statesments of prob117

ani_mitr86 wrote:When I tried to find the minimum distance by Bellman Ford it was giving WA. So, I tested if the graph is connected or not and I found that some unconnected graph is there contradicting the problem statement. so, there is a mistake in data set.
there isn't any mistake...

first graph is clearly a triangle and the second graph is a NOT Eulerian graph, there's three (disjoint) direct paths from 'd' to 's'

alessio
New poster
Posts: 1
Joined: Sun Sep 28, 2008 10:27 pm

### 117 The Postal Worker Rings Once - WA !!!

Hi,
I'm trying to solve the "117 The Postal Worker Rings Once" problem in C but I get WA and I have no clue on where could be the mistake.
The algorithm that I use is:
- if there are 0 node with an even degree (that is there are only 2 nodes with an odd degree) or 0 node with an odd degree (that is all the node have an even degree) then print the sum of the weight
- otherwise it means that there are 2 nodes with odd degree and other nodes with even degree. Now calculate the shortest path with dijkstra's algorithm and sum the weight of this path to the sum of the weights of all the nodes (this because we can start from a node with odd degree and reach the other node with odd degree passing through all the nodes of the graph, then we must return to the node we started).

My code passed the given test cases and also some test cases which I've made on http://www.uvatoolkit.com/problemssolve.php , unfortunately I'm still getting "Wrong Answer". This is the first time I use graph so I'm not 100% sure if the data structure I've used it's ok or if the dijkstra's algorithm I've implemented is correct (I've followed more or less http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm pseudocode).

Here's my code:

Code: Select all

``````#include <stdio.h>
#include <malloc.h>
#include <string.h>

#define INFINITE -1

typedef struct node node;

char letter;

int weight;
};

struct node {

int distance;
int visited;

};

void freeGraph(node graph);

void initGraph(node graph);

void addEdge(node graph, char let1, char let2, int weight);

int dijkstraGraph(node graph, node *start,  node *end);

int main()
{
node graph;
node *oddNodeStart, *oddNodeEnd ;
char string;
int res;
int total_weight;
int oddDegCnt, evenDegCnt;

initGraph(graph);

while (1) {
total_weight = oddDegCnt = evenDegCnt = 0;
oddNodeStart = oddNodeEnd = NULL;

while ((res = scanf("%s", string)) != EOF) {
break;

total_weight += strlen(string);
}
if (res == EOF)
break;

for (res=0; res<26; res++) {
if (oddDegCnt)
oddNodeEnd = &graph[res];
else
oddNodeStart = &graph[res];

oddDegCnt++;
evenDegCnt++;
}
}

if (!oddDegCnt || !evenDegCnt) {
printf("%d\n", total_weight);
freeGraph(graph);
} else {
int d1;
/*printf("odd node letters %c %c\n", 'a' + (oddNodeStart - graph), 'a' + (oddNodeEnd - graph)); */
d1 = dijkstraGraph(graph, oddNodeStart, oddNodeEnd);

printf("%d\n", total_weight + d1);
freeGraph(graph);
}
}

return 0;
}

node * findSmallestDist(node graph)
{
int i;
node *smallest = NULL;

for (i=0; i<26; i++) {
if (!graph[i].visited && graph[i].distance != INFINITE) {
if (!smallest)
smallest = (graph + i);
else if (graph[i].distance < smallest->distance)
smallest = (graph + i);
}
}

return smallest;
}

int dijkstraGraph(node graph, node *start, node *end)
{
node *smallest;
int alt;
int index;

for (alt = 0; alt<26; alt++) {
graph[alt].visited = 0;
graph[alt].distance = INFINITE;
}

start->distance = 0;
while (1) {
smallest = findSmallestDist(graph);
smallest->visited = 1;

while (neighbor) {
index = neighbor->letter - 'a';
alt = smallest->distance + neighbor->weight;

if (graph[index].distance != INFINITE) {
if (alt < graph[index].distance)
graph[index].distance = alt;
} else {
graph[index].distance = alt;
}

if (&graph[index] == end)
return graph[index].distance;

neighbor = neighbor->next;
}
}
}

void freeGraph(node graph)
{
int i;
for (i=0; i<26; i++) {
}
graph[i].visited = 0;
graph[i].distance = INFINITE;
}
}

void initGraph(node graph)
{
int i;
for (i=0; i<26; i++) {
graph[i].visited = 0;
graph[i].distance = INFINITE;
}
}

{

} else {
}
}

void addEdge(node graph, char let1, char let2, int weight)
{
}

``````
Do I have forgotten some special case(s) ? Or did I have implemented dijkstra's algorithm wrong ?

Any kind of help is really appreciated, thanks.

Alessio

BenKester
New poster
Posts: 1
Joined: Tue Dec 23, 2008 7:06 pm

### Re: 117 - The Postal Worker Rings Once

I see what you guys are saying and I'm able to get an AC. However, will this work for all scenarios? I'm not convinced.

What about if there are more than 2 odd degree nodes? For instance, say:

mike
matt
mark
tie
kart
eek

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 117 - The Postal Worker Rings Once

BenKester wrote:What about if there are more than 2 odd degree nodes?
If there are n odd-degree nodes, you need to find a set of n/2 paths between them such that 1) each path starts and ends on a odd-degree vertex, 2) for each odd-degree vertex there's exactly one path whose endpoint is this vertex, and 3) total length of these paths is minimized. Then just add the edges of these paths to the graph, and find an euler tour.

The problem of minimizing their total length can be reformulated as a minimum-cost matching problem in a complete graph with n vertices, where cost between i-th and j-th vertex is the length of shortest path between i-th and j-th odd-degree vertices in the original graph. For n up to about 15-20, you can solve it with dynamic programming, see problem 10296. For even bigger n, there are polynomial-time algorithms (with bounds like O(n^4), I think), but they're very hardcore.

Btw, this is called Chinese Postman problem in literature, google it if you're interested.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 117 - The Postal Worker Rings Once

why WA plz help me!!!!!!!!!!!!!!!!

#include<cstdio>
#include<string>
#include<iostream>
#define MAX 100
#define INF 1000000000
#define UNDEFINED -1

using namespace std;
char aa;
long cost,sum,degree[MAX+1];
long G[MAX+1][MAX+1],list[MAX+1][MAX+1],q[MAX+1], qPos[MAX+1];
long flag,od1,od2,Count[MAX+1];
typedef struct{
long c;
long parent;
}ss;
ss node;
Last edited by MRH on Tue Jan 27, 2009 10:23 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 117 - The Postal Worker Rings Once

Use [code]...[/code] tags to post source code.

I don't quite understand what your BFS() function is doing. If it's doing what it names says - some modification of breadth-first search, then I think it's doing it wrong, and you better replace it with a true shortest-path algorithm - e.g. Dijkstra's or Floyd-Warshall algorithm. Floyd-Warshall also takes a lot less work to do.

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 117 - The Postal Worker Rings Once

"HI GREAT HEALPER MF" plz this is my Dijkstra's code
this is also WA
[#include<cstdio>
#include<cmath>
#include<string>
#include<vector>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<iostream>

using namespace std;
struct fun{
long xnode, weight;
fun() {}
fun(long t, long w) : xnode(t), weight(w) {}
bool operator < (const fun &that) const {
return weight > that.weight;
}
};
char a;
long u,v,cost,sum,degree;
long flag,od1,od2;

int main()
{
long i,pc;

while(1)
{
flag=0;

]
Last edited by MRH on Tue Jan 27, 2009 10:21 pm, edited 1 time in total.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

### Re: 117 - The Postal Worker Rings Once

Use [code]...[/code] tags to post source code! Why do I have to repeat that? You think it's fun looking at unindented code?

Your code is way too complicated for such a simple task - why do you use DIjkstra with heap? The graph only has 26 vertices - so it's perfectly OK to use O(n^2) Dijkstra with adjacency matrix, or even O(n^3) Floyd-Warshall algorithm.

And what is this line supposed to do: "if(od1 && od2 && pc==2)"? Can't od1 and od2 be zeroes?

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 117 - The Postal Worker Rings Once

thanks mf

Hobby
New poster
Posts: 4
Joined: Thu Jul 29, 2010 2:35 pm

### Help me--117

Code: Select all

``````#include  <iostream>
#include <fstream>
#include <string>
using namespace std;
#define inf 99999999
#define N 40
int Graphics[N][N];
int degree[N];
bool visite[N];
void clearGlobal();
int GetOddDgreeNum();
int GetMinWeightWithTwoNode(int,int);
int oddNode;
int main()
{
//ifstream cin("117.txt");
string s;
while(1){
int sum=0;
int nodesNum=0;
clearGlobal();
while(cin>>s){
int len=s.length();
if (Graphics[s.at(0)-'a'][s.at(len-1)-'a']>len){
Graphics[s.at(0)-'a'][s.at(len-1)-'a']=len;
Graphics[s.at(len-1)-'a'][s.at(0)-'a']=len;
}

degree[s.at(0)-'a']+=1;
degree[s.at(len-1)-'a']+=1;
sum+=len;
}
if(GetOddDgreeNum()==0){
cout<<sum;
}
else{
cout<<sum+GetMinWeightWithTwoNode(sum,nodesNum);
}
if(cin.eof()) break;
cout<<endl;
}
}
int GetOddDgreeNum()
{
int k=0;
for(int i=0;i<N;i++){
if((degree[i]%2)==1){
oddNode[k++]=i;
}
}
return k;
}
int GetMinWeightWithTwoNode(int sum,int nodeNum)
{
int dp[N]={0};
int start=oddNode;
int end=oddNode;
int i,j;
for( i=0;i<N;i++){
if(degree[i]!=0){
visite[i]=false;
}
else{
visite[i]=true;
}
dp[i]=Graphics[start][i];
}
dp[start]=0;
visite[start]=true;
int nextNode;
for( i=1;i<N;++i){
if(degree[i]==0) continue;
int min=inf;
for(j=0;j<N;j++){
if(!visite[j]){
if(dp[j]<min){
nextNode=j;
min=dp[j];
}
}
}
visite[nextNode]=true;
for(j=0;j<N;j++){
if(degree[j]==0)  continue;
if(!visite[j]&&((min+Graphics[nextNode][j])<dp[j])){
dp[j]=min+Graphics[nextNode][j];
}
}
}
return dp[end];
}
void  clearGlobal()
{
for(int i=0;i<N;i++){
for(int j=0;j<N;j++)
Graphics[i][j]=inf;
degree[i]=0;
visite[i]=false;
}
oddNode=-1;
oddNode=-1;
}

``````
I thought this probeam may be easy , but it has problem me?
who can tell me where is the error?
in my thought,when the graphics has two odd degree nodes, the resule is sum of all len and add the shortpath of the node?
Help

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 117 - The Postal Worker Rings Once

Foe Those who are getting WA:
Input

Code: Select all

``````ab
cd
de
ea
car
car
computer
cor
``````
Output

Code: Select all

``````16
6
17
``````

Cramer
New poster
Posts: 2
Joined: Wed Aug 26, 2015 7:25 pm

### WA: 117 - The Postal Worker Rings Once

can't find out the cause for getting WA possible critical input/output had been checked. Code: Select all

``````#include<bits/stdc++.h>
#define total_alphabet 26

using namespace std;

int minDistance(int dist[], bool sptSet[])
{
// Initialize min value
int minima = INT_MAX, min_index;

for (int v = 0; v < total_alphabet; v++)
if (sptSet[v] == false && dist[v] <= minima)
minima = dist[v], min_index = v;

return min_index;
}

int dijkstra(int graph[total_alphabet][total_alphabet], int src, int dst)
{
int dist[total_alphabet];

bool sptSet[total_alphabet]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized

// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i < total_alphabet; i++)
dist[i] = INT_MAX, sptSet[i] = false;

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
for (int i = 0; i < total_alphabet-1; i++)
{
int u = minDistance(dist, sptSet);

// Mark the picked vertex as processed
sptSet[u] = true;

// Update dist value of the adjacent vertices of the picked vertex.
for (int v = 0; v < total_alphabet; v++)

// Update dist[v] only if is not in sptSet, there is an edge from
// u to v, and total weight of path from src to  v through u is
// smaller than current value of dist[v]
if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX
&& dist[u]+graph[u][v] < dist[v])
{
dist[v] = dist[u] + graph[u][v];
//cout << v << " --- " << dist[v] << endl;
}
}
//cout << dst << " --- " << dist[dst] << endl;
return dist[dst];

// print the constructed distance array
//printSolution(dist, V);
}

main()
{
string lain;
char ajaira_jinis = 'a', matha, lenja;
int cost[total_alphabet][total_alphabet], degree[total_alphabet];
int ans, saiz, odd_index1, odd_index2;
memset(cost, 0, sizeof cost);
memset(degree, 0, sizeof degree);
odd_index1 = odd_index2 = ans = 0;

while(cin >> lain)
{
{
for(int i = 0; i < total_alphabet; i++)
{
if(degree[i] % 2 != 0)
{
if(odd_index1 == 0)
odd_index1 = i;
else
odd_index2 = i;
}
}

if(odd_index1 == 0)
printf("%d\n", ans);
else
{
int add = dijkstra(cost, odd_index1, odd_index2);
}

memset(cost, 0, sizeof cost);
memset(degree, 0, sizeof degree);
odd_index1 = odd_index1 = ans = 0;
continue;
}
//bujhtasi na ki likhte hoibo !!! ;
saiz = lain.size();
ans += saiz;
matha = lain;
lenja = lain[saiz - 1];
matha = matha - ajaira_jinis;
lenja = lenja - ajaira_jinis;

cost[matha][lenja] = saiz;
cost[lenja][matha] = saiz;
//printf("%d --- %d = %d \n", matha, lenja, cost[matha][lenja]);

degree[matha]++;
degree[lenja]++;

}

return 0;
}

``````

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 117 - The Postal Worker Rings Once

Input

Code: Select all

``````mike
matt
mark
tie
kart
eek
``25``