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

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

Re: confused by statesments of prob117

Post by ani_mitr86 » Wed Jun 11, 2008 3:49 pm

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[0].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[1000];
int wt[1000], pre[MAX+1], rank[MAX+1];
int total=0, sz=0;
while(scanf("%s", a)!=EOF){
if(strcmp(a, "deadend")==0){
// 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[0]; 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

Post by x140l31 » Tue Jul 08, 2008 11:33 pm

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 !!!

Post by alessio » Sun Sep 28, 2008 11:06 pm

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 adjNode adjNode;
typedef struct node node;

struct adjNode {
	char letter;
	
	int weight;
	adjNode *next;
};
	
struct node {
	int adjNodes; /* number of adjacent nodes */
	
	int distance;
	int visited;
	
	adjNode *adjList;
};

void freeGraph(node graph[26]);

void initGraph(node graph[26]);

void addAdjNode(node *curNode, char lettAdjNode, int weight);

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

int dijkstraGraph(node graph[26], node *start,  node *end);

int main()
{
	node graph[26];
	node *oddNodeStart, *oddNodeEnd ;
	char string[500];
	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) {
			if (!strcmp(string, "deadend"))
			 	break;
			 	
			 addEdge(graph, string[0], string[strlen(string)-1], strlen(string));
			 total_weight += strlen(string);
		}
		if (res == EOF)
			break;
		
		for (res=0; res<26; res++) {
			if (graph[res].adjNodes % 2) {
				if (oddDegCnt) 
					oddNodeEnd = &graph[res];
				else
					oddNodeStart = &graph[res];
					
				oddDegCnt++;
			} else if (graph[res].adjNodes) {
				evenDegCnt++;
			}
			/*printf("%c %d ",res+'a',  graph[res].adjNodes);*/
		}

		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[26])
{
	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[26], node *start, node *end)
{
	node *smallest;
	adjNode *neighbor;
	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;
		
		neighbor = smallest->adjList;
		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[26])
{
	int i;
	for (i=0; i<26; i++) {
		adjNode *aux;
		while (graph[i].adjList) {
			aux = graph[i].adjList->next;
			free(graph[i].adjList);
			graph[i].adjList = aux;
		}
		graph[i].visited = 0;
		graph[i].distance = INFINITE;
		graph[i].adjNodes = 0;
		graph[i].adjList = NULL;
	}
}

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

void addAdjNode(node *curNode, char lettAdjNode, int weight)
{
	curNode->adjNodes++;

	if (curNode->adjList) {
		adjNode *aux = curNode->adjList;
		curNode->adjList = malloc(sizeof(adjNode));
		curNode->adjList->letter = lettAdjNode;
		curNode->adjList->weight = weight;
		curNode->adjList->next = aux;
	} else {
		curNode->adjList = malloc(sizeof(adjNode));
		curNode->adjList->letter = lettAdjNode;
		curNode->adjList->weight = weight;
		curNode->adjList->next = NULL;
	}
}

void addEdge(node graph[26], char let1, char let2, int weight)
{
	addAdjNode(&graph[let1-'a'], let2, weight);
	addAdjNode(&graph[let2-'a'], let1, 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

Post by BenKester » Tue Dec 23, 2008 7:13 pm

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

Post by mf » Tue Dec 23, 2008 9:08 pm

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

Post by MRH » Tue Jan 27, 2009 7:30 pm

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[1000];
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[1000];
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

Post by mf » Tue Jan 27, 2009 8:10 pm

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

Post by MRH » Tue Jan 27, 2009 8:39 pm

"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[1000];
long u,v,cost,sum,degree[300];
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

Post by mf » Tue Jan 27, 2009 9:32 pm

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

Post by MRH » Tue Jan 27, 2009 10:07 pm

thanks mf

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

Help me--117

Post by Hobby » Fri Aug 06, 2010 2:06 pm

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[2];
int main()
{
	//ifstream cin("117.txt");
	string s;
	while(1){
		int sum=0;
		int nodesNum=0;
		clearGlobal();
		while(cin>>s){
			if(!s.compare("deadend")) break;
			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[0];
	int end=oddNode[1];
	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[0]=-1;
	oddNode[1]=-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
Location: Bangladesh
Contact:

Re: 117 - The Postal Worker Rings Once

Post by Imti » Sun Jan 23, 2011 8:34 pm

Foe Those who are getting WA:
Input

Code: Select all

ab
cd
de
ea
deadend
car
deadend
car
computer
cor
deadend
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

Post by Cramer » Tue Jun 07, 2016 1:11 pm

can't find out the cause for getting WA :x
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)
    {
        if(lain == "deadend")
        {
            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);
                printf("%d\n", ans + add);
            }

            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[0];
        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

Post by lighted » Sun Mar 12, 2017 3:50 pm

Input

Code: Select all

mike
matt
mark
tie
kart
eek
deadend
Output

Code: Select all

25
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

Post Reply

Return to “Volume 1 (100-199)”