117 - The Postal Worker Rings Once

[ani_mitr86]

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]

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]

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]

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]

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]

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

[mf]

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]

"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;

]

[mf]

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]

thanks mf

[Hobby]

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]

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]

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)
    {
        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]

Input

Code: Select all

mike
matt
mark
tie
kart
eek
deadend

Output

Code: Select all

25