## 11492 - Babel

Moderator: Board moderators

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

### 11492 - Babel

Why getting WA? any critical test cases.......?

Code: Select all

``````/*
Problem name: Babel
Author      : Shiplu
Algorithm   : Dijkstra
*/
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
struct abc
{
int x,cost,ch;
}temp,u;
struct comp
{
bool operator()(const abc &a,const abc &b)
{
return a.cost>b.cost;
}
};
char str[4005][53];
int d[4005],inf=1077952576,m;
vector< pair <int , int> > G[4005];
int findStore(char *x)
{
int i;
for(i=0;i<m;i++)
if(!strcmp(str[i],x))
break;
if(i==m)
strcpy(str[m++],x);
return i;
}
int main()
{
int i,n,start,end,j,k,in=1<<6;
pair<int,int> v;
char x[55],y[55],word[4005][55];
while(scanf("%d",&n)==1)
{
if(n==0)
break;
m=0;
scanf("%s %s",x,y);
start=findStore(x);
end=findStore(y);
memset(d,in,sizeof(d));
for(i=0;i<4002;i++)
G[i].clear();
for(i=0;i<n;i++)
{
scanf("%s %s %s",x,y,word[i]);
j=findStore(x);
k=findStore(y);
G[j].push_back(make_pair(k,strlen(word[i])));
G[k].push_back(make_pair(j,strlen(word[i])));

}
d[start]=0;
priority_queue<abc,vector<abc>,comp> Q;
temp.x=start;
temp.cost=0;
temp.ch=0;
Q.push(temp);
while(!Q.empty())
{
u=Q.top();
Q.pop();
if(u.cost>d[u.x])
continue;
for(i=G[u.x].size()-1;i>=0;i--)
{
v=G[u.x][i];
if(u.ch!=word[v.first][0]-96 && d[u.x]+v.second<d[v.first])
{
d[v.first]=d[u.x]+v.second;
temp.x=v.first;
temp.cost=d[v.first];
temp.ch=word[v.first][0]-96;
Q.push(temp);
}
}
}
if(d[end]<inf)
printf("%d\n",d[end]);
else
printf("impossivel\n");
}
return 0;
}
``````

jan_holmes
Experienced poster
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore
Contact:

### Re: 11492 - Babel

Try this :

Code: Select all

``````4
a b
a c aku
a c ku
c b kc
``````
It should return 5 instead of "impossivel".

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### Re: 11492 - Babel

I can't understand why my code gets WA.
Plz someone tell me some cases where my code may fail.
I used dijkstra.Help me.Thanks in advance.

Code: Select all

``Code removed after AC.``
Last edited by Anindya on Fri Oct 03, 2008 8:12 pm, edited 1 time in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

### Re: 11492 - Babel

Try this case..

Code: Select all

``````3
aaa aaa
aaa bbb x
bbb ccc yy
ccc aaa zzz
0``````
I don't know what the expected output would be .. But my AC code prints..

Code: Select all

``0``

neilor
New poster
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

### Re: 11492 - Babel

Dear Anindya.

I don´t know if you correct your code, anyway the error is because a small test is missing (bold)
if(u==st)
{
v=x.dest;
lv=x.cost[0]-'a';
if (x.cost.size() < dis[v][lv])
dis[v][lv]=x.cost.size();
x.tot=dis[v][lv];
q.push(x);
}

if you use the same map with bellman-ford you can optimize de code to half time

Best regards

Anindya
New poster
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

### Re: 11492 - Babel

Thanks a lot neilor & helloneo .
I thought that when i am updating a vertex from source,i need not to check whether this value is smaller than previous stored value.
I forgot the following line:
The same pair of languages may have several words associated to it.
From my WA it is clear that they may even have the same initial letter & that is not an error of the problemsetter.This is completely valid according to problem description.
Anyway,thanks everyone for help.

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

### Re: 11492 - Babel

Could someone plz explain how to solve this problem using dijkstra?? I can't figure out how to process the multiple edge cost...
electron

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11492 - Babel

Can someone plz explain how to do the memorization using Dijkstra in this problem

Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11492 - Babel

i m getting WA in this problem,pls help....

Code: Select all

``````no one replied ...
anyway....
got acc.....
``````
Last edited by Jehad Uddin on Sat Feb 13, 2010 7:12 am, edited 1 time in total.

hotovaga
New poster
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

### 11492 - Babel

This is my approach, I can't understand why I am getting WA.

Code: Select all

``````#include<iostream>
#include<utility>
#include<cstdio>
#include<vector>
#include<string>
#include<map>
#include<queue>

#define MAX_INT 1077952576

using namespace std;

int E,len;

int cost[2*2000+10],res;
bool visited[2*2000+10];

map<string,int>v;
vector< vector< pair< int,pair<int,char> > > > adjList(2000*2+10);
priority_queue<pair< int,pair<int,char> > > pq;

void initialize()
{

int i,j;

for(i = 0; i<=E*2; i++)
cost[i] = MAX_INT;

for(i =0; i<=E*2; i++)
visited[i] = false;

v.clear();

for(i=0;i<2*E;i++)

pq = priority_queue<pair< int,pair<int,char> > > ();
res = MAX_INT;
}

int main()
{

int i,j,k,u,d,cnt;

while(scanf("%d",&E)==1){
if(E==0)
break;

initialize();

string s1,s2,s3;

cin>>s1>>s2;

cnt = 2;

v[s1] = 0;  //source vertex indexed to 0
if(v.find(s1) == v.find(s2)){
res  = 0;

}

v[s2] = 1; //destination vertex indexed to 1

for(i=0; i<E; i++){
s1.clear();
s2.clear();
s3.clear();

cin>>s1>>s2>>s3;

if(v.find(s1) == v.end()){
v[s1] = cnt;
u = cnt++;
}

else
u = v.find(s1)->second;

if(v.find(s2) == v.end()){
v[s2] = cnt;
d = cnt++;
}
else
d = v.find(s2)->second;

len = s3.size();

char ch = s3[0];

}

//end of taking input
//Dijkstra Begins
cost[0] = 0;

pair<int,pair<int,char> > cur, next;

pq.push(make_pair(0,make_pair(0,'1')));

while(!pq.empty()){
cur = pq.top();
pq.pop();

cur.first = -cur.first;

if(visited[cur.second.first])
continue;
visited[cur.second.first] = true;

if(next.second.second == cur.second.second)
continue;
if(visited[next.second.first])
continue;

int curcost = cost[cur.second.first] + next.first;

if(curcost < cost[next.second.first]){
cost[next.second.first] = curcost;
}
pq.push(make_pair(-curcost,make_pair(next.second.first,next.second.second)));
}
}

if( res ==0 )
printf("0\n");
else if(cost[1]== MAX_INT)
printf("impossivel\n");
else
printf("%d\n",cost[1]);
}

return 0;
}
``````

SyFy
New poster
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Contact:

### Re: 11492 - Babel

nice problem! Solved it with Dijkstra + Java in 1.020

Used priority queue and stored in it three values (toNodeId, ch, len), where:
toNodeId - node id to which this edge goes
ch - first character of the word "on" this edge
len - current path len

the main problem I think was to guess the way to store "best paths" from start point to all other.

good luck to all!
there are NO tricky testcases.

annisizzler
New poster
Posts: 4
Joined: Sat Apr 21, 2012 9:29 am

### Re: 11492 - Babel

getting wa constantly in this problem,is there anyone to help?
some critical i/o can also help?i have tried with all sample i/o s given here.

Scarecrow
Learning poster
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11492 - Babel

annisizzler, try this I/O. Your code gives 9.

Input

Code: Select all

``````4
a c
c b kh
b a ku
c b akarman
b a akua
0``````
Output

Code: Select all

``````6
``````
Do or do not. There is no try.

asifruetcse10
New poster
Posts: 1
Joined: Mon Aug 06, 2012 8:17 pm

### Re: 11492 - Babel

Try This Cases:

Code: Select all

``````3
aaa aaa
aaa bbb x
bbb ccc yy
ccc aaa zzz
11
a c
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a f
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a g
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
11
a d
a b abcd
a b bl
a b bd
b c bfs
b c b
b e bn
b e cndk
e d bcd
e d abcde
e g cde
e g ab
0``````
Output Should be:

Code: Select all

``````impossivel
5
impossivel
8
9
``````

mmfrb
New poster
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

### Re: 11492 - Babel

Why TLE? I'm just running a normal dijsktra algorithm, and my output is correct for all the inputs in this thread.
I'd be very grateful if someone could help me. Thanks

Code: Select all

``````#include <cstdio>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <iostream>

#define MAX 2147483645

using namespace std;

typedef pair <int, int> ii;
typedef vector <ii> vii;

string s1, s2, p, start, finish;
pair < pair <string, string>, string > parents[2010];
vector <int> dist;
int i, j;
priority_queue <ii, vector <ii>, greater <ii> > pq;

int main()
{
int m, u, d, k;
ii front, v;
while(scanf("%d", &m) && m)
{
cin >> start >> finish;
dist.assign(m+2, MAX);
k = 0;
for(i = 1; i <= m; ++i)
{
cin >> s1 >> s2 >> p;
if(s1 == start || s2 == start)
if(s1 == finish || s2 == finish)
{
k++;
}
for(j = 1; j < i; ++j)
if((s1 == parents[j].first.first || s1 == parents[j].first.second || s2 == parents[j].first.first || s2 == parents[j].first.second) && p[0] != parents[j].second[0])
{
}
parents[i] = make_pair(make_pair(s1, s2), p);
}

if((int)adjList[0].size() == 0 || k == 0)
{
printf("impossivel\n");
continue;
}

dist[0] = 0;
pq.push(ii(0, 0));

while(!pq.empty())
{
front = pq.top(); pq.pop();
u = front.second; d = front.first;

if(dist[u] == d)
for(int i = 0; i < (int)adjList[u].size(); ++i)
{
if(dist[u] + v.second < dist[v.first])
{
dist[v.first] = dist[u] + v.second;
pq.push(ii(dist[v.first], v.first));
}
}
}

if(dist[m+1] == MAX) printf("impossivel\n");
else printf("%d\n", dist[m+1]);
}
return 0;
}
``````
Last edited by mmfrb on Tue Oct 16, 2012 4:29 pm, edited 3 times in total.