Page 2 of 4

Posted: Sat Nov 08, 2003 7:06 am
by Grinder
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.

:)

p117 Why WA

Posted: Tue May 11, 2004 4:21 pm
by chunyi81
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.

Problem 117 and 139 Why WA?

Posted: Wed May 12, 2004 1:06 pm
by chunyi81
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]

Problem 117 and 139 Why WA?

Posted: Fri May 14, 2004 6:13 am
by chunyi81
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?

Posted: Thu Jun 03, 2004 4:15 pm
by chunyi81
Please help. Thanks.

Posted: Sun Jul 25, 2004 4:07 pm
by chunyi81
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.

117

Posted: Fri Dec 03, 2004 5:25 pm
by sklitzz
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]

117 WA

Posted: Fri Jan 14, 2005 3:13 pm
by Eduard
I'm gettin 117 WA.Give some tests please.
Thanks.

Posted: Mon Jan 17, 2005 4:26 pm
by sohel
Instead of directly asking for test cases,
why don't you describe your algorithm..
.. in this way everyone will be helpful including you. :P

Posted: Tue Jan 18, 2005 4:32 pm
by Eduard
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

Posted: Tue Jan 18, 2005 6:30 pm
by Eduard
I find my little mistake and got AC. :D

Posted: Mon Jan 24, 2005 2:00 pm
by ImLazy
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.

Posted: Thu Apr 14, 2005 6:08 pm
by technobug
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:;
	}

}

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

Posted: Tue Apr 19, 2005 6:51 pm
by sahand
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!

Posted: Fri Apr 22, 2005 11:34 am
by Sanny
The graph is undirected. :wink:

Regards
Sanny