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

Grinder
New poster
Posts: 9
Joined: Fri Oct 17, 2003 11:49 am
Location: Bangladesh
Contact:

Post by Grinder » Sat Nov 08, 2003 7:06 am

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

Post by chunyi81 » Tue May 11, 2004 4:21 pm

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

computer
car
collar
deadend

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?

Post by chunyi81 » Wed May 12, 2004 1:06 pm

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?

Post by chunyi81 » Fri May 14, 2004 6:13 am

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

Post by chunyi81 » Thu Jun 03, 2004 4:15 pm

Please help. Thanks.

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

Post by chunyi81 » Sun Jul 25, 2004 4:07 pm

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

Post by sklitzz » Fri Dec 03, 2004 5:25 pm

I having trouble solving this problem.

This is my algorithm:
I read edges and add sum them up.
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;
while( t != "deadend" )
{
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

Post by Eduard » Fri Jan 14, 2005 3:13 pm

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

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

Post by sohel » Mon Jan 17, 2005 4:26 pm

Instead of directly asking for test cases,
why don't you describe your algorithm..
.. in this way everyone will be helpful including you. :P

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

Post by Eduard » Tue Jan 18, 2005 4:32 pm

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

Post by Eduard » Tue Jan 18, 2005 6:30 pm

I find my little mistake and got AC. :D
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
ImLazy
Experienced poster
Posts: 215
Joined: Sat Jul 10, 2004 4:31 pm
Location: Shanghai, China

Post by ImLazy » Mon Jan 24, 2005 2:00 pm

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:

Post by technobug » Thu Apr 14, 2005 6:08 pm

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;

			// if deadend --> next
 			if(strcmp(lin,"deadend")==0) break;

			// 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:;
	}

}

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

117 - The Postal Worker Rings Once - WA - please help!

Post by sahand » Tue Apr 19, 2005 6:51 pm

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:

Post by Sanny » Fri Apr 22, 2005 11:34 am

The graph is undirected. :wink:

Regards
Sanny

Post Reply

Return to “Volume 1 (100-199)”