11492 - Babel

All about problems in Volume CXIV. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

11492 - Babel

Postby shiplu_1320 » Mon Sep 22, 2008 12:30 am

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

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

Re: 11492 - Babel

Postby jan_holmes » Tue Sep 23, 2008 7:04 pm

Try this :

Code: Select all
4
a b
a c aku
a c ku
c b kc
c b bada


It should return 5 instead of "impossivel".
jan_holmes
Experienced poster
 
Posts: 136
Joined: Fri Apr 15, 2005 3:47 pm
Location: Singapore

Re: 11492 - Babel

Postby Anindya » Mon Sep 29, 2008 11:12 am

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.
Anindya
New poster
 
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

Re: 11492 - Babel

Postby helloneo » Mon Sep 29, 2008 4:30 pm

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
helloneo
Guru
 
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11492 - Babel

Postby neilor » Fri Oct 03, 2008 6:30 pm

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)
{
x=adj[u][i];
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
neilor
New poster
 
Posts: 10
Joined: Fri Oct 03, 2008 6:00 pm

Re: 11492 - Babel

Postby Anindya » Fri Oct 03, 2008 8:09 pm

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.
Anindya
New poster
 
Posts: 28
Joined: Sun Feb 04, 2007 4:34 am
Location: EEE,BUET,DHAKA

Re: 11492 - Babel

Postby f74956227 » Tue Feb 03, 2009 3:01 pm

Could someone plz explain how to solve this problem using dijkstra?? I can't figure out how to process the multiple edge cost...
electron
f74956227
New poster
 
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan

Re: 11492 - Babel

Postby Chirag Chheda » Mon Mar 09, 2009 9:08 am

Can someone plz explain how to do the memorization using Dijkstra in this problem
Chirag Chheda
Learning poster
 
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 11492 - Babel

Postby Jehad Uddin » Sat Nov 07, 2009 4:50 pm

i m getting WA in this problem,pls help.... :oops:
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.
Jehad Uddin
Learning poster
 
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

11492 - Babel

Postby hotovaga » Mon Feb 21, 2011 7:59 am

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();
   
   adjList.clear();
   
   for(i=0;i<2*E;i++)
   adjList[i].clear();
   
   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];

           
         adjList[u].push_back(make_pair(len,(make_pair(d,ch))));
         adjList[d].push_back(make_pair(len,(make_pair(u,ch))));
      }

      //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;
      
         
         
         for(i = 0; i<adjList[cur.second.first].size(); i++){
                 
            next = adjList[cur.second.first][i];
            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;
}


Thanks in advance.
hotovaga
New poster
 
Posts: 4
Joined: Mon Nov 29, 2010 9:35 pm

Re: 11492 - Babel

Postby SyFy » Thu Jun 21, 2012 6:16 pm

:D 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. :wink:
SyFy
New poster
 
Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm
Location: Russia, Vladimir

Re: 11492 - Babel

Postby annisizzler » Sat Jul 28, 2012 3:24 am

getting wa constantly in this problem,is there anyone to help?
heres my code link:https://ideone.com/6Q8Ow
some critical i/o can also help?i have tried with all sample i/o s given here.
annisizzler
New poster
 
Posts: 4
Joined: Sat Apr 21, 2012 9:29 am

Re: 11492 - Babel

Postby Scarecrow » Sat Jul 28, 2012 1:45 pm

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.
Scarecrow
Learning poster
 
Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

Re: 11492 - Babel

Postby asifruetcse10 » Mon Aug 06, 2012 8:29 pm

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
asifruetcse10
New poster
 
Posts: 1
Joined: Mon Aug 06, 2012 8:17 pm

Re: 11492 - Babel

Postby mmfrb » Tue Oct 16, 2012 1:19 am

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;

vector < vii > adjList;
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;
      adjList.assign(m+2, vii());
      dist.assign(m+2, MAX);
      k = 0;
      for(i = 1; i <= m; ++i)
      {
         cin >> s1 >> s2 >> p;
         if(s1 == start || s2 == start)
            adjList[0].push_back(ii(i, 0));
         if(s1 == finish || s2 == finish)
         {
            adjList[i].push_back(ii(m+1, p.length()));
            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])
            {
               adjList[i].push_back(ii(j, p.length()));
               adjList[j].push_back(ii(i, parents[j].second.length()));
            }
            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)
            {
               v = adjList[u][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.
mmfrb
New poster
 
Posts: 13
Joined: Thu Aug 30, 2012 3:21 pm

Next

Return to Volume CXIV

Who is online

Users browsing this forum: No registered users and 1 guest