117  The Postal Worker Rings Once
Moderator: Board moderators

 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
Sahand
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
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
keep study every day
http://felixhalim.net/uva/hunting.php?id=99497
http://felixhalim.net/uva/hunting.php?id=99497
117  WA, help PLEASE!
Hello .. i've tried to solve the problem with both disjktra and royfloyd 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.

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 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,
It is a very simple problem,
But i cant figure out where is my problem..
I am getting WAs,

 A great helper
 Posts: 383
 Joined: Mon Oct 18, 2004 8:25 am
 Location: Bangladesh
 Contact:
117 WA
I can't find why this is wrong; please help me to find mistakes
this my code
Thanks.
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[len1]'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;
}

 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
it means that we have to find out euler tour .and euler tour is possible only whenThe tour must begin and end at the same intersection.
but problem statement also states thatAn undirected graph contains an Eulerian cycle iff (1) it is connected and (2) each vertex is of even degree.
in this situtation only euler tour is possible not cycle ..There will be at most two intersections with odd degree.
...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...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.
Re: confused by statesments of prob117
Neither of them..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...
You can use the same edges several times..
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 ..
thanx for ur attention
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[length1]'a']=length;
cost[temp[length1]'a'][temp[0]'a']=length;
sw[temp[0]'a']=0;
sw[temp[length1]'a']=0;
}
}
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!
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!

 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.