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

User avatar
sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Location: Halifax, Nova Scotia, Canada
Contact:

what a mistake!

Post by sahand » Fri Apr 22, 2005 3:31 pm

Thanks sammy. That was a very funny mistake! :D
Sahand :wink:

surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

try to give an answer

Post by surya ss » Fri Jul 01, 2005 2:46 am

maybe it's out of date or you have it ac, but
I try to give a clue anyway

the clue is : you can't just find the shortest path from just one side,what i mean is :
in this input :
one
two
three

you have 6 path, not 3 path :
detail:
(1) from(o) to (e) length = 3
(2) from(e) to (o) length = 3
(3) from(t) to (o) length = 3
(4) from(o) to (t) length = 3
(5) from(t) to (e) length = 5
(6) from(e) to (t) length = 5

in you code you just have 3 path:
detail
(1) from(o) to (e) length = 3
(2) from(t) to (o) length = 3
(3) from(t) to (e) length = 5

so it got wrong answer
hope it can help

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

117 - WA, help PLEASE!

Post by coldfire » Sun Apr 09, 2006 10:38 pm

Hello .. i've tried to solve the problem with both disjktra and roy-floyd but i keep getting WA. Can anyone take a look on my code or give me some test data please ?!
{$S-,R-,Q-,B-}

const hValue = maxlongint div 2;

var i, j, q, nod, nod2: char;
grad: array['a'..'z'] of longint;
d: array['a'..'z', 'a'..'z'] of longint;
s: string;
t: longint;
found: boolean;

procedure read_data;
begin

// assign(input, '117.in'); reset(input);
// assign(output, '117.out'); rewrite(output);

while not eof(input) do begin

readln(s);
t := 0; found := false;
for i := 'a' to 'z' do
for j := 'a' to 'z' do d[i, j] := hValue;

while (s <> 'deadend') do begin

if s <> '' then begin

found := true;
inc(grad[s[1]]); inc(grad[s[length(s)]]);
inc(t, length(s));
d[s[1], s[length(s)]] := length(s);
d[s[length(s)], s[1]] := length(s);

end;

readln(s);

end;

nod := 'A'; nod2 := 'A';
for i := 'a' to 'z' do
if odd(grad) then
if nod = 'A' then nod := i else
if nod2 = 'A' then nod2 := i;

if nod <> 'A' then begin

for q := 'a' to 'z' do
for i := 'a' to 'z' do
for j := 'a' to 'z' do
if d[i, q] + d[q, j] < d[i, j] then d[i, j] := d[i, q] + d[q, j];

t := t + d[nod, nod2];
end;

if found then writeln(t);

end;

// close(input); close(output);

end;

begin

read_data;

end.

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm

Post by coldfire » Mon Apr 10, 2006 9:18 am

I've solved the problem. Just forgot to fillchar with 0 "grad" (degree) array at each new route :)

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

117: critical input/output

Post by emotional blind » Sun Jun 04, 2006 9:50 pm

I need critical input output for problem,
It is a very simple problem,
But i cant figure out where is my problem..
I am getting WAs,

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Mon Jun 05, 2006 7:02 pm

ACCEPTED :lol:

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

117 WA

Post by Artikali » Mon Jul 17, 2006 6:54 pm

I can't find why this is wrong; please help me to find mistakes
this my code

Code: Select all

//117 The Postal Worker rings once
#include <iostream>
#include <string>
#include <cassert>
using namespace std;
const char dead[]="deadend";
#define N 40
#define LEN 1000
#define inf 99999999
int edge[N][N],degree[N];
int main(){
	//freopen("a.in","r",stdin);
	char st[LEN];
	int len;
	int _wer=0,sum=0,odd1,odd2,x,y;
	while(1){
		_wer=0;
		for(int i=0;i<N;i++)
			for(int j=0;j<N;j++) 
				edge[i][j]=inf;
		for(int i=0;i<N;i++) degree[i]=0;
		while(cin>>st){
			_wer=1;
			if(strcmp(st,dead)==0) break;
			len=strlen(st);
			x=st[0]-'a';y=st[len-1]-'a';
			if (edge[x][y]>len){
			edge[x][y]=len;
			edge[y][x]=len;
			}
			degree[x]++;
			degree[y]++;
			sum+=len;
		}
		if(_wer==0) break;
		int q;odd1=-1;odd2=-1;
		for(q=0;q<N;q++) if (degree[q]%2!=0){odd1=q;q++;break;}
		for(;q<N;q++) if(degree[q]%2!=0){odd2=q;break;}

		if(odd1!=-1 && odd2!=-1)
		{
			assert(odd1!=odd2);
			for(int i=0;i<N;i++) edge[i][i]=0;
			for(int k=0;k<N;k++){
				for(int i=0;i<N;i++){
					for(int j=0;j<N;j++){
						if (edge[i][k]+edge[k][j]<edge[i][j])
							edge[i][j]=edge[i][k]+edge[k][j];
					}
				}
			}
		cout<<sum+edge[odd1][odd2]<<endl;
		}
		else cout<<sum<<endl;
	}
	return 0;
}
Thanks.

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jul 17, 2006 8:23 pm

Maybe reset sum to 0 *inside* the loop?

Btw, you should read other threads, someone had *exactly* the same mistake in their code. And if you missed it, you should've posted the question in one of those.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Tue Jul 18, 2006 4:37 am

Thank you very much, That was a stupid mistake of mine, i should be careful.

mukeshtiwari
Learning poster
Posts: 63
Joined: Tue Mar 07, 2006 6:51 pm
Location: india

confused by statesments of prob117

Post by mukeshtiwari » Wed Feb 14, 2007 4:36 am

hi everybody in problem statement it is give
The tour must begin and end at the same intersection.
it means that we have to find out euler tour .and euler tour is possible only when
An undirected graph contains an Eulerian cycle iff (1) it is connected and (2) each vertex is of even degree.
but problem statement also states that
There will be at most two intersections with odd degree.
in this situtation only euler tour is possible not cycle ..
An undirected graph contains an Eulerian path iff (1) it is connected and (2) all but two vertices are of even degree. These two vertices will be the start and end points of the path.
...now plz explain me the problem wheather we have to find euler cycle or euler tour ..becoz i think it is asking for cycle which is not possible when there will be odd virtex...

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: confused by statesments of prob117

Post by helloneo » Wed Feb 14, 2007 4:49 am

mukeshtiwari wrote:...now plz explain me the problem wheather we have to find euler cycle or euler tour ..becoz i think it is asking for cycle which is not possible when there will be odd virtex...
Neither of them..
You can use the same edges several times..

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Wed Feb 14, 2007 9:07 am

So, basically it is a 'Chinese Postman' problem.

mahan
New poster
Posts: 4
Joined: Fri Sep 22, 2006 10:20 am

Post by mahan » Sun Jul 22, 2007 9:12 pm

hi .. who can help me ? i got WA for this Q many time .. my Algorithm is very simple .. i add the edge weights and store them in sumEdges .. if there are 2 odd nodes , i find the min path between this 2 node with dijkstra algorithm , then add with sumEdges.. then print sumEdges ..

Code: Select all

[#include <iostream>
#include <string>
#include <fstream>

using namespace std;



const int Max=1000000; 
const int mx=10000;
const int bound=27;

int cost[bound][bound]={Max};
int sw[mx]={-1};
int i,j,k,count=0;

int dijkstra(int first,int last){
	sw[first]=1;
	int cur;
	int min=Max;

	for(j=1;j<bound;j++){
		min=Max;
		for(k=1;k<bound;k++){
			if(!sw[k]){
				if(cost[first][k]<min){ min=cost[first][k]; cur=k;}
			}
		}
		sw[cur]=1;

		for(i=0;i<bound;i++){
			if(!sw[i] && i!=first && i!=cur){
				if(cost[first][i]>cost[first][cur]+cost[cur][i]){
					cost[first][i]=cost[first][cur]+cost[cur][i];
				}
			}
		}
		if(cur==last) break;
	}
	return cost[first][last];
}


void main(){
		
	for(i=0;i<bound;i++){
		for(j=0;j<bound;j++){
			cost[i][j]=Max;
		}
	}
	
//	ifstream cin("117.in");

	char temp[1000];
	int firstNode,lastNode;
	int w=0;
	int l=0;

	while(1){
		cin>>temp;
		if(!strcmp(temp,"deadend")){
			w=0;
			firstNode=-1;
			lastNode=-1;
			int sumEdges=0;

			for(i=0;i<bound;i++){
				count=0;
				for(j=0;j<bound;j++){
					if(cost[i][j]!=Max){
						sumEdges+=cost[i][j];
						count++;
					}
				}
				if((count%2)){
					if(!w){
						firstNode=i;
						w=1;
					}
					else lastNode=i;
				}							
			}
			
			sumEdge/=2;
			
			if(firstNode!=-1)	sumEdges+=dijkstra(firstNode,lastNode);

			cout<<sumEdges<<endl;

			for(i=0;i<bound;i++){
				sw[i]=0;
				for(j=0;j<bound;j++){
					cost[i][j]=Max;
				}
			}
			continue;
		}
		else if(cin.eof()) break;
		int length=strlen(temp);
		l+=length;
		cost[temp[0]-'a'][temp[length-1]-'a']=length;
		cost[temp[length-1]-'a'][temp[0]-'a']=length;
		sw[temp[0]-'a']=0;
		sw[temp[length-1]-'a']=0;		
	}
}
thanx for ur attention

toni
New poster
Posts: 7
Joined: Wed Jul 25, 2007 6:03 pm

Post by toni » Mon Jul 30, 2007 7:02 pm

hello everyone, My algorithm is sum up all the paths and if there exist two odd degree nodes, use the Bellman_Ford to find shortest path between theis two nodes.

I try several cases and this program can help me find the correct answer but , I still got WA.

Maybe I have some bugs in my program, I really need your help!

Can anyone give me some test datas? Or some advices ,thx!

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:35 pm

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.

Post Reply

Return to “Volume 1 (100-199)”