429 - Word Transformation

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

Moderator: Board moderators

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 429

Post by Obaida » Sat Dec 11, 2010 5:15 pm

Why i am getting TLE? Any one please help me :(

Code: Select all

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cctype>
#include<cstdlib>
#include<cmath>
#include<sstream>
#include<fstream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<list>
#include<bitset>
#include<algorithm>
#include<functional>
using namespace std;

int main(){
    int t,cost;
    scanf("%d",&t);
    while(t--){
        string s;
        char line[25];
        vector<string>D;
        while(scanf("%s",line)){
            if(line[0]=='*')break;
            D.push_back(line);
        }
        gets(line);
        while(gets(line)){
            if(!line[0])break;
            stringstream is(line);
            string a,b;
            is>>a>>b;
            vector<string>d;
            for(int i = 0;i<D.size();++i)if(D[i].size()==a.size())d.push_back(D[i]);
            queue< pair<string,int> >Q;
            set< string >S;
            Q.push( make_pair(a,0) );
            S.insert(a);
            while(Q.size()){
                s = Q.front().first;
                cost = Q.front().second;
                Q.pop();
                if(s==b){
                    printf("%s %s %d\n",a.c_str(),b.c_str(),cost);
                    break;
                }
                for(int i = 0;i<d.size();++i){
                    int c = 0;
                    for(int j = 0;j<d[i].size();++j)if(d[i][j]!=s[j])++c;
                    if(S.find(d[i])!=S.end() || c!=1)continue;
                    S.insert(d[i]);
                    Q.push( make_pair(d[i],cost+1) );
                }
            }
        }if(t)puts("");
    }
    return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

MAMU
New poster
Posts: 6
Joined: Fri Apr 01, 2011 12:45 pm
Location: Dhaka, Bangladesh.

Re: 429 (Why RE??)

Post by MAMU » Thu Oct 13, 2011 11:32 am

My code:

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>

char s[220][15];bool sd[220][220];int dis[220];

inline void init_d(int n){for(int i=0;i<n;i++)dis[i]=24748364;}

void bfs(int i,int j,int n)
{
	for(;j<n;j++)
	{
		if(sd[i][j]==1&&dis[j]>dis[i]+1)
		{
			dis[j]=dis[i]+1;
			bfs(i,j+1,n);
			bfs(j,0,n);
			break;
		}
	}
}

int main()
{
	int f=0;
	char s1[15],s2[15];
	int t,z=1,i,j,k,a,n,e,g;
	gets(s1);
	t=atoi(s1);
	while(z++<=t)
	{
		if(z>2)putchar(10);
		i=0;
		while(gets(s[i])!=NULL&&strcmp(s[i],"*")!=0)
		{
			for(j=0;j<i&&s[i][0]!=0;j++)
			{
				if(strlen(s[i])==strlen(s[j]))
				{
					for(k=0,a=0;s[i][k]!=0;k++)
					{
						if(s[i][k]!=s[j][k])a++;
						if(a>=2)break;
					}
					if(a==1){sd[i][j]=1;sd[j][i]=1;}
				}
			}
			if(s[i][0]!=0)
				i++;
		}
		n=i;
		while(gets(s1)!=NULL&&s1[0]!=0)
		{
			i=strlen(s1)/2;s1[i]=0;
			for(i++,j=0;s1[i]!=0;i++,j++)
				s2[j]=s1[i];
			s2[j]=0;

			for(i=0,f=0;i<n;i++)
			{
				if(strcmp(s[i],s1)==0){e=i;if(f==2)break;f=1;}
				if(strcmp(s[i],s2)==0){g=i;if(f==1)break;f=2;}
			}
			init_d(n);
			dis[e]=0;
			bfs(e,0,n);
			printf("%s %s %d\n",s1,s2,dis[g]);
		}
	}
	return 0;
}
I just solve about 20 graph(dfs,bfs) problem... but this type of problem give me about 50 RTE... most of the case... not for stack over flow... I think in this problem, I cant read the input file properly...
Can anybody help??

zyz913614263
New poster
Posts: 3
Joined: Tue Oct 18, 2011 4:27 pm

Re: 429 Word Transformation

Post by zyz913614263 » Tue Oct 18, 2011 4:42 pm

is 'ba' and 'cb' right?

zyz913614263
New poster
Posts: 3
Joined: Tue Oct 18, 2011 4:27 pm

Re: 429 Word Transformation

Post by zyz913614263 » Tue Oct 18, 2011 6:44 pm

zyz913614263 wrote:is 'ba' and 'cb' right?
I got the AC
the transfer is
abc to abd right
but
abc to bad wrong
abc to abcd wrong
:D

User avatar
outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

429 - Word Transformation

Post by outsbook » Mon Nov 28, 2011 4:27 pm

BFS problem

1. Input all dictionary words to string array word[]
2. Find adjacency list for all word.
ab adjacency can be ac, ad,....,cb,db, and so on. i.e. only one character is different and two word length are same.
but ab adjacency can not be ab,abc,dab,cd and so on.
3. Now run BFS from start word to end word and find the move from start to end. i.e. shortest path.
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 429 Word Transformation

Post by mathgirl » Sun May 27, 2012 12:08 pm

I m getting RTE for this one. I tried with sample I/O and my code works.

Code: Select all

#include<stdio.h>
#include<iostream>
#include<vector>
#include<cstring>

using namespace std;

struct word
{
	char w[20];
};

vector<word> dict;
vector<vector<int> > conn;
vector<bool> chosen;
vector<int> dist;

bool same(char *a,char *b)
{
	if(strlen(a) != strlen(b))
		return false;

	for(int i = 0;i<strlen(a);i++)
	{
		if(a[i] != b[i])
			return false;
	}
	return true;
}

bool compare(char *a,char *b)
{
	if(strlen(a) != strlen(b))
		return false;

	int diff = 0;
	for(int i = 0;i<strlen(a);i++)
	{
		if(a[i] != b[i])
			diff++;

		if(diff > 1)
			return false;
	}
	return true;
}

void mindist(int dest,int d)
{
	vector<int> next;
	next.push_back(dest);
	int n = next.front();
	dist[n] = min(dist[n],d + 1);
	while(!next.empty())
	{
		n = next.front();
		if(!chosen[n])
		{
			chosen[n] = true;
			for(int i = 0;i < conn[n].size();i++)
			{
				dist[conn[n][i]] = min(dist[conn[n][i]],dist[n] + 1);
				next.push_back(conn[n][i]);
			}
		}

		next.erase(next.begin());
	}
}

int main()
{
	int t,re;
	re = scanf("%d",&t);
	bool first = true;

	while(t--)
	{
		while(getchar() != '\n');
		while(getchar() != '\n');

		char temp[100];
		
		while(scanf("%s",temp) && !same(temp,"*"))
		{
			word obj;
			strcpy(obj.w,temp);
			dict.push_back(obj);
			conn.push_back(vector<int>());
			int cur = dict.size() - 1;

			for(int i = 0;i < dict.size() - 1;i++)
			{
				if(compare(obj.w,dict[i].w) == 1)
				{
					conn[i].push_back(cur);
					conn[cur].push_back(i);
				}
			}
		}

		while(getchar() != '\n');

		if(!first)
			printf("\n");
		first = false;

		char start[20],dest[20];
		while(gets(temp) && strlen(temp))
		{
			char *pch;
	        pch = strtok(temp, " ");
	        strcpy(start,pch);
	        pch = strtok (NULL, " ");
	        strcpy(dest,pch);
			
			chosen.assign(dict.size(),false);
			dist.assign(dict.size(),1000);
			
			int s = -1,d = -1,i = 0;
			
			for(int i = 0;i < dict.size();i++)
			{
				if(same(start,dict[i].w))
				{	
					s = i;
					break;
				}
			}
			
			for(int i = 0;i < dict.size();i++)
			{
				if(same(dest,dict[i].w))
				{	
					d = i;
					break;
				}
			}

			int len = 0;

			mindist(d,-1);
			len = dist[s];
			printf("%s %s %d\n",start,dest,len);
		}

		dict.clear();
		conn.clear();
	}
	return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 429 Word Transformation

Post by brianfry713 » Fri Jun 01, 2012 12:37 am

Try this input:

Code: Select all

2

dip
lip
mad
map
maple
may
pad
pip
pod
pop
sap
sip
slice
slick
spice
stick
stock
*
spice stock
may pod

dip
lip
*
dip lip
Check input and AC output for thousands of problems on uDebug!

mathgirl
New poster
Posts: 36
Joined: Tue Apr 24, 2012 6:20 pm

Re: 429 Word Transformation

Post by mathgirl » Fri Jun 01, 2012 6:34 am

Thanks ! The problem was in reading the newlines after each test case. Got AC now.

pranon
New poster
Posts: 14
Joined: Mon Jul 23, 2012 2:39 pm

Re: 429 Word Transformation

Post by pranon » Mon Jul 23, 2012 5:02 pm

``WA" on this problem as well, with no apparent bugs apparent to me. Will be greatful for any help. :)

Code: Select all

Code removed. Should always remember to makenull() my queue. :D
Thanks in advance.
Last edited by pranon on Tue Jul 24, 2012 9:24 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 429 Word Transformation

Post by brianfry713 » Mon Jul 23, 2012 11:38 pm

Clear your queue between test cases.
Check input and AC output for thousands of problems on uDebug!

naved92
New poster
Posts: 3
Joined: Thu Jul 05, 2012 1:10 pm

Re: 429 Word Transformation

Post by naved92 » Mon Nov 26, 2012 6:45 pm

WA...cant fix the bug

Code: Select all

#include<cstdio>
#include<iostream>
#include<sstream>
#include<algorithm>
#include<cstdlib>
#include<queue>
#include<vector>
#include<cstring>
#include<map>
using namespace std;


char L[1024];
vector<string>graph;

int adjmatrix[256][256],n;
 bool visited[256];
 int dist[256];


void init()
{ n=0;
    graph.clear();
for(int i=0;i<256;i++)
  for(int j=0;j<256;j++)
    adjmatrix[i][j]=0;

}

bool is_dif_one(string a,string b)
{
    if(a.size() !=b.size())return false;
    int total=0;

    for(int i=0;i<a.size();i++)
     if(a[i]!=b[i])total++;
     if(total==1)return true;
     return false;
}
void make_a_graph()
{
  int i,j;

  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    {
        if(  is_dif_one(graph[i],graph[j])==1)adjmatrix[i][j]=1;

    }
}

int MAP(string &a)
{
    for(int i=0;i<n;i++)
    if(graph[i]==a)return i;

    return -1;
}
int main()
{

    int tc;
    gets(L);
    tc=atoi(L);

    while(tc--)
     {

         gets(L);

         istringstream IS;

         string word,source,end;

       //  map<string,int>MAP;

         int tot=0;
         while(gets(L))
         {
             IS.clear();
             IS.str(L);
             IS>>word;
             if(word=="*")break;
             graph.push_back(word);



         }

         n=graph.size();
         make_a_graph();



        while(gets(L))
        {
            IS.clear();
            IS.str(L);
            if(IS>>source>>end){

                /*BFS*/

                int S=MAP(source),D=MAP(end);

                queue<int>BFS;

               // memset(distance,-1,sizeof(distance));
              //  memset(visited,false,sizeof(visited));

for(int i=0;i<n;i++)
   {dist[i]=23456;visited[i]=false;}
                BFS.push(S);
                visited[S]=true;
                dist[S]=0;


                while(!BFS.empty())
                     {
                         int F=BFS.front();
                         BFS.pop();
                         if(F==D)break;
                         for(int i=0;i<n;i++)
                           {
                               int C=i;
                               if(visited[C]==false && adjmatrix[F][C]==1)
                                  { BFS.push(C);
                                      visited[C]=true;
                                      dist[C]=dist[F]+1;

                                  }
                           }
                     }
                  cout<<source<<" "<<end<<" "<<dist[D]<<endl;


                                                 }
        else break;
        }

        if(tc!=0)cout<<endl;
     }

return 0;
}

?????? ????
New poster
Posts: 7
Joined: Tue Apr 03, 2012 2:34 pm
Location: Manikgonj, Bangladesh

Re: 429 Word Transformation

Post by ?????? ???? » Tue Nov 27, 2012 6:37 pm

Code: Select all

Remove After Accepted

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 429 Word Transformation

Post by brianfry713 » Fri Nov 30, 2012 9:07 pm

naved92, did you mean to have a call to init()?
Check input and AC output for thousands of problems on uDebug!

karakuritempya
New poster
Posts: 3
Joined: Sun Oct 21, 2012 10:34 am

Re: 429 - Word Transformation

Post by karakuritempya » Fri Dec 14, 2012 3:51 pm

I am getting TLE for this problem :( . Does it matter to use getline(cin) ?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 429 - Word Transformation

Post by brianfry713 » Fri Dec 14, 2012 7:51 pm

I don't think that's the cause of your TLE. My AC code uses getline(cin,str) to read the starting and ending words, and cin >> str to read the dictionary.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 4 (400-499)”