## 117 - The Postal Worker Rings Once

Moderator: Board moderators

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Contact:
I solved this problem. I use Floyed and dijkstra. In Floyed it got more time but in dijkstra it take 0.000 sec.

Ryan Pai
is absolutly right. It's the main thing. Euler path.

rafi7
may be ur problem in dijkstra or BMF. check this.

I hate three things one- Wrong Answer,TL and the problem which statement is not clear.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### p117 Why WA

I would like to clarify whether it is possible to have the following input for this qn:

computer
car
collar

Here 2 intersections are linked by 3 streets. How would this graph be represented using an adjacency matrix or adjacency list?

My code worked with the sample input but failed the above test case.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### Problem 117 and 139 Why WA?

I have checked through my code many times, submitted to OJ, but the OJ keep on replying WA. My code works with the given sample input, and will terminate at EOF(end of file). I find no bug in my code. I am using Djikstra's shortest path algorithm. I am using the integer value 1000000 to represent "infinity" in the adjacency matrix I used to represent the graph. I need only a 2D array of size 26 by 26 maximum since there are a maximum of 26 possible intersections ('a' to 'z' lowercase). Could those who got AC provide some input and output for which my program will fail?

Here is my WA code for problem 117. Any help will be greatly appreciated.

[c]
Resolved.
[/c]

For problem 139, I also get WA, but I find no bug. Here is my WA code for problem 139. My code can handle locality names with spaces such as "Los Angeles" and works with all the input in this forum. Where did I go wrong?

[c]
Resolved.
[/c]
Last edited by chunyi81 on Sun Jul 25, 2004 4:03 pm, edited 4 times in total.

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

### Problem 117 and 139 Why WA?

Can someone help me with problem 139 please? My code works with all the input in this board, but the judge keep on replying WA to my code. Where is the bug?

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore

chunyi81
A great helper
Posts: 293
Joined: Sat Jun 21, 2003 4:19 am
Location: Singapore
For problem 139, I realised that there is one very tricky input that I have overlooked. For STD codes 00 is a valid STD code, and not a IDD code.

Input
00 123\$10
000000
001234 1
#

Correct Output:
001234 123 1234 1 0.10 0.10

Hope this helps others who are still trying to solve the problem.

sklitzz
New poster
Posts: 32
Joined: Fri Dec 03, 2004 5:19 pm

### 117

I having trouble solving this problem.

This is my algorithm:
I keep track of how many edges do go from each vertex
If there are two odd degree vertexes, i find the shorthest path from the 2
verticies.

I get WA

This is my code:
[cpp]
#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;

struct edge
{
int x,y,w;
edge( int a, int b, int c ) { x = a; y = b; w = c; }
};
vector < edge > e;
vector < int > dist;
int slova[300] = { 0 };

int bellman_ford( int start, int end, int n )
{
dist.resize( (int)'a' + 31 );
for( int i = 0; i < dist.size(); ++i ) dist = 9999999;
dist[start] = 0;

for( int i = 0; i < n; ++i )
for( int j = 0; j < e.size(); ++j )
dist[e[j].y] <?= dist[e[j].x] + e[j].w;

return dist[end];
}

int main()
{
while( 1 )
{
int s = 0;
vector < int > odd;
string t;
cin >> t;
if( t == "" ) break;
{
int a = t[0];
int b = t[t.size()-1];
int c = t.size();
e.push_back( edge( a, b, c ) );
s += c;
++slova[a]; ++slova;
if( slova[a] % 2 != 0 && slova[a] != 1 ) odd.push_back( a );
if( slova % 2 != 0 && slova != 1 ) odd.push_back( b );
cin >> t;
}
//How many verticies do we have
int n = 0;
for( int i = 0; i < 300; ++i )
if( slova > 0 ) ++n;

if( odd.size() == 0) cout << s << endl;
else cout << s + bellman_ford( odd[0], odd[1], n ) << endl;

//Cleaning
e.clear();
dist.clear();
for( int i = 0; i < 300; ++i ) slova = 0;
}

return 0;
}[/cpp]

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

### 117 WA

I'm gettin 117 WA.Give some tests please.
Thanks.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York
why don't you describe your algorithm..
.. in this way everyone will be helpful including you.

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
Ok Sohel.
My algo.
Vertexes of graph are letters 'a'..'z'.Let K be number of vertexes wich have odd nodes.
if k=0 then answer=sum length(of all words).
k can't be 1!
if k=2 then answer=sum length(of all words)+shortest path from one odd vertex to another.
Eduard
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan
I find my little mistake and got AC.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China
Oh, I was so stupid that I used to think this problem very complicated. But now I see your algorithm which is so good. Thank you.
I stay home. Don't call me out.

technobug
Learning poster
Posts: 88
Joined: Sat Nov 15, 2003 6:41 pm
Location: Brasilien
Contact:
Hmmm... i tried going with floyd warshal...... the rest is the same. Any ideas?

Code: Select all

``````#include <iostream>
#include <string.h>
#include <stdio.h>
#include <algorithm>

using namespace std;
#define FOR(a,b) for(int a=0;a<b;a++)

#define MAXI (50)
int mat[MAXI][MAXI];
int t[MAXI];

void clear() {
FOR(i,MAXI) FOR(j,MAXI) mat[i][j]=2<<10;
FOR(i,MAXI) t[i]=0;
}

void floyd() {
FOR(i,MAXI) FOR(j,MAXI) if(i!=j) FOR(k,MAXI) if(i!=k && j!=k)
mat[j][k] = min(mat[j][i]+mat[i][k],mat[j][k]);
}

int main() {

char lin[10001];

while(true) {

clear();
int tot = 0;

while(true) {

// reads a line, if it should stop, stop
if(!(gets(lin))) return 0;
if(strlen(lin)==0) continue;

// connects them
int d = lin[0]-'a';
int p = lin[strlen(lin)-1]-'a';
t[d]++; t[p]++;
tot += strlen(lin);
mat[d][p] = min(mat[d][lin[p]],(int) strlen(lin));

}

floyd();

FOR(i,MAXI) if(t[i]%2) {
for(int j=i+1;j<MAXI;j++) if(t[j]%2) {
cout << (mat[i][j]+tot) << endl;
goto n;
}
}

cout << tot << endl;
n:;
}

}
``````

sahand
New poster
Posts: 19
Joined: Sat Mar 12, 2005 5:56 pm
Contact:

Hi,
This is my code for 117. It works for the sample inputs but I get WA when I submit it. Please help.

Code: Select all

``````Code removed!
``````
Last edited by sahand on Fri Apr 22, 2005 3:30 pm, edited 1 time in total.

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
The graph is undirected.

Regards
Sanny