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

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

what a mistake!

Thanks sammy. That was a very funny mistake! Sahand surya ss
New poster
Posts: 22
Joined: Sat Jun 11, 2005 7:31 pm

try to give an answer

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!

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;

begin

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

while not eof(input) do begin

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(t, length(s));
d[s, s[length(s)]] := length(s);
d[s[length(s)], s] := length(s);

end;

end;

nod := 'A'; nod2 := 'A';
for i := 'a' to 'z' do
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

end.

coldfire
New poster
Posts: 8
Joined: Sat Mar 12, 2005 4:47 pm
I've solved the problem. Just forgot to fillchar with 0 "grad" (degree) array at each new route emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

117: critical input/output

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,

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
ACCEPTED Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

117 WA

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;
#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;
len=strlen(st);
x=st-'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
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
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

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

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
So, basically it is a 'Chinese Postman' problem.

mahan
New poster
Posts: 4
Joined: Fri Sep 22, 2006 10:20 am
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;
int firstNode,lastNode;
int w=0;
int l=0;

while(1){
cin>>temp;
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-'a'][temp[length-1]-'a']=length;
cost[temp[length-1]-'a'][temp-'a']=length;
sw[temp-'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
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

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.