10150 - Doublets

[Angeh]

But my problem isn't time. My code runs in 2 secs. I get WA not TLE. Can you post some critical test cases please?

try this !!

Code: Select all

roaster
coastal
postal
booster
roasted
coasted
rooster

booster roasted
coastal postal

your output is

Code: Select all

booster
rooster
roaster
roasted

No solution.

No solution.

3 outputs?

congratulation
your code got AC 1.208
you process always one more case
I edited your code like this !!

Code: Select all

    //Doublets
    /* @JUDGE_ID: 00000 10150 C++ */
    //Técnicas Utilizadas: BFS
    #include <iostream>
    #include <string.h>
    #include <vector>
    #include <deque>

    using namespace std;

    int palavras=0;
    char dicionario[25500][20];
    int tamanhos[25500];
    vector< deque<int> > grafo(25500,deque<int>());

    bool isDoublet(char str1[], int &tam1, char str2[], int &tam2){
       if (tam1!=tam2)
          return false;
        int conta=0;       
       for (int i=0; i<tam1; i++){
          if (str1[i]!=str2[i]){         
             conta++;
             if (conta>1)
                   return false;
          }
       }   
       return true;
    }

    bool bfs(int start, int end, vector<int> &parent){
       vector<bool> discovered(palavras+1,false);
       deque <int> q;
       int v, i;
       q.push_back(start);
       discovered[start]=true;
       while (q.size()) {
         v = q.front();
         q.pop_front();
         for (i=0; i<grafo[v].size(); i++)       
           if (discovered[grafo[v][i]]==false){
              q.push_back(grafo[v][i]);
              discovered[grafo[v][i]]=true;
              parent[grafo[v][i]]=v;
              if (discovered[end])
                 return true;
           }       
       }
       return false;
    }

    void find_path(int start, int end, vector<int> &parent){
       if ( (start==end) || (end==-1)){
          printf("%s\n",dicionario[end]);     
       }else{     
          find_path(start,parent[end],parent);
          printf("%s\n",dicionario[end]);
       }
    }

    int main(){   
		/*freopen("in.txt","r",stdin);
		freopen("out.txt","w",stdout);//*/
       while(1){
          scanf("%s",dicionario[palavras]);
          tamanhos[palavras]=strlen(dicionario[palavras]);
          for(int i=palavras-1; i>=0; i--){         
             if(isDoublet(dicionario[i],tamanhos[i],dicionario[palavras],tamanhos[palavras])){
                grafo[palavras].push_back(i);
                grafo[i].push_back(palavras);
             }
          }
          cin.ignore();
          if(cin.peek()=='\n')
             break;
          palavras++;     
       }
       cin.ignore();
	   int i=0;//------
       while(1){
          char origem[20], destino[20];
          int origemidx=-1,destinoidx=-1;
          scanf("%s %s",origem,destino);
		  cin.ignore();
          if(cin.eof())
             break;
		  if(i++)
			    printf("\n");
		  if(strlen(origem) != strlen(destino) ){
			printf("No solution.\n");
			continue;
		  }

          for(int i=0; i<=palavras; i++)
             if(strcmp(dicionario[i],origem)==0){
                origemidx=i;
                break;
             }
          for(int i=0; i<=palavras; i++)
             if(strcmp(dicionario[i],destino)==0){
                destinoidx=i;
                break;
             }
          if(origemidx==-1 || destinoidx==-1){
             printf("No solution.\n");
          }
		  else{
             vector<int> parent(palavras+1,-1);         
             if(bfs(origemidx,destinoidx,parent))           
                find_path(origemidx,destinoidx,parent);           
             else
				 printf("No solution.\n");	
		  }
       }
       return 0;
    }

[diego_engcomp]

Oh man, a really thank your help. I think that my program was wrong because I don't considered a '\n' in the end of the last test case. But the important is that I get AC with your little modification, thanks.

[amoor]

Hi ,,

I am trying to solve this problem but it gave me WA :S I make BFS for the possible words then backtrack the result and print it ,,

Code: Select all

Removed after getting AC :D

Can anybody help me ..

[sohel]

Have you looked at the discussions of this thread - http://acm.uva.es/board/viewtopic.php?f=10&t=42
Don't create a new thread for a problem that already exists. Make your post in an existing thread!

[Shafaet_du]

TRIE is good

[live_lie]

i use bfs and got TLE....? what is the best approach...?

[Shafaet_du]

@Live_lie:
Bfs can pass the time limit if you can build the graph efficiently. I used trie instead of map and passed the limit.

[live_lie]

@ Shafaet_du: if you dont mind,i am not so expert can you sortly expalin what is "trie " and how to use it or provide me some link to know about it.
thanks for the reply.

[live_lie]

thank you Shafaet vai. i have an Ac now ..i just changed the data structure i used.

[Scarecrow]

can someone help me speed up my code please? continuously getting TLE
seems the isValidPair function needs some speeding up. but can't find a way

Code: Select all

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<vector>
using namespace std;

int cmprFunc(const void *, const void *);
int binarySearch(char *, int, int);
bool isValidPair(int, int);
bool bfs(int, int);
void printSequence(int);

struct word
{
    char *s; int index;
}words[25150];

struct
{
    char word[17]; bool visitStatus; int parent;
    vector<int>adjNodes;
}graph[25150];

int main()
{
    int i, j, p1, p2; bool newln = false; char s1[17], s2[17];

    for(i = 0, gets(graph[i].word); graph[i].word[0]; gets(graph[++i].word))
    {
        words[i].s = graph[i].word;
        words[i].index = i;

        for(j = 0; j<i; j++)
            if(isValidPair(j, i))
            {
                graph[j].adjNodes.push_back(i);
                graph[i].adjNodes.push_back(j);
            }
    }

    qsort(words, i, sizeof(word), cmprFunc);

    while(scanf("%s %s", s1, s2)!=EOF)
    {
        if(newln)
            printf("\n");
        if(strlen(s1)==strlen(s2))
        {
            p1 = binarySearch(s1, 0, i-1);
            p2 = binarySearch(s2, 0, i-1);
            if(p1!=-1 && p2!=-1)
            {
                for(j = 0; j<i; j++)
                    graph[j].visitStatus = false;

                if(bfs(words[p1].index, words[p2].index))
                    printSequence(words[p2].index);
                else
                    printf("No solution.\n");
            }
            else
                printf("No solution.\n");
        }
        else
            printf("No solution.\n");

        newln = true;
    }

    return 0;
}

bool isValidPair(int i, int j)
{
    if(strlen(graph[i].word)!=strlen(graph[j].word))
        return false;

    int mismatch = 0, k;
    for(k = 0; graph[i].word[k] && mismatch<2; k++)
        if(graph[i].word[k]!=graph[j].word[k])
            mismatch++;

    return mismatch==1;
}

int cmprFunc(const void *x, const void *y)
{
    return strcmp(((word *)x)->s, ((word *)y)->s);
}

int binarySearch(char *s, int low, int high)
{
    if(low>high)
        return -1;

    int mid = (low+high)/2, compareVal;

    if(!(compareVal = strcmp(s, words[mid].s)))
        return mid;
    if(compareVal<0)
        return binarySearch(s, low, mid-1);
    return binarySearch(s, mid+1, high);
}

bool bfs(int u, int v)
{
    queue<int> q;
    q.push(u);
    graph[u].visitStatus = true;
    graph[u].parent = -1;

    while(!q.empty())
    {
        u = q.front();
        q.pop();
        if(u==v)
            return true;

        for(int sz = graph[u].adjNodes.size(), i = 0; i<sz; i++)
            if(!graph[graph[u].adjNodes[i]].visitStatus)
            {
                q.push(graph[u].adjNodes[i]);
                graph[graph[u].adjNodes[i]].visitStatus = true;
                graph[graph[u].adjNodes[i]].parent = u;
            }
    }

    return false;
}

void printSequence(int i)
{
    if(graph[i].parent==-1)
    {
        printf("%s\n", graph[i].word);
        return;
    }

    printSequence(graph[i].parent);
    printf("%s\n", graph[i].word);
}

[brianfry713]

If there are 25143 words in the dictionary, how many times does isValidPair() get called? Then there are two calls to strlen(), how long does that take with a word of 16 letters?

[three0s]

For some weird reason my code runs faster with linear search compared to binary search.
sort - binary search 0.156s
sort - linear search 0.144s
linear search 0.152s

[jh123456]

Does anyone knows, why is still answer WRONG ANSWER?

Code: Select all

#include <cstdlib>
#include <iostream>
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <stack>
#include <cstdlib>
#include <iostream>
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <list>

using namespace std;

std::vector<string> slova;


//struct 
//std::queue<string> graf;
std::map<string,bool> obsahuje;
std::map<string,bool> obsahujeSlovnik;

//std::stack<string> graf;
std::vector<string> graf;

bool endreached = false;
void vytvorGraf(string startW, string endW){
	if(!obsahujeSlovnik[startW] || !obsahujeSlovnik[endW])
		return;
	if(startW.length() != endW.length())
		return;

//	if(startW.length() != endW.length())
		//return;

	string ref = startW;
	for(int i = 0; i < startW.length(); i++){
		for(int j = 0; j < 26; j++){
			string slovo = "";
			slovo = startW;
			slovo[i] = 97 + j;

			if(obsahujeSlovnik[slovo] && !obsahuje[slovo]) {


				graf.push_back(slovo);
				//graph.push(slovo);
				obsahuje[slovo] = true;
				//cout << slovo;

				if(slovo == endW){
					endreached = true;
					return;
				}
				//cout << endl;
				vytvorGraf(slovo,endW);
				
				if(obsahuje[endW])
					return;
				else{
					graf.pop_back();
					obsahuje[slovo] = false;
					return;
				}


			}


		}


	}
	return;
	//return graf;
}

void clear(){
	std::stack<string> grafEMPTY;
	
	//std::swap( graf, grafEMPTY );
	graf.clear();
	obsahuje.clear();
	endreached = false;
}

void vypis(){
	/*
	while(!graf.empty())
	{
		cout << graf.top();
		graf.pop();

		if(!graf.empty())
			cout << endl;
	}*/
	for(int i = 0; i < graf.size(); i++){
		cout << graf[i];

		if(i+1 < graf.size())
			cout << endl;

	}

}

int main(){
	string w;
	string input[2];



	std::queue<string> fronta;


	while(getline(cin,w) && w.size() > 0){
		//cout << w << endl;
		slova.push_back(w);
		obsahujeSlovnik[w] = true;
	}

	std::sort(slova.begin(),slova.end());
	bool init = false;
	
	/*string w1 = "";
	string w2 = "";*/
	/*
	char line[16 << 3], w1[16], w2[16];
	while(gets(line) && sscanf(line, "%s %s", w1, w2) == 2){
		if(init == true)
			cout << endl;
		init = true;
		clear();
		vytvorGraf(w1,w2);

		if(graf.size() > 1)
			vypis();
		else
			cout << "No solution." << endl;



		//if(
	}*/

	while( cin >> input[0] >> input[1]){
		if(init == true)
			cout << endl << endl;
		init = true;

		if(input[0] == input[1]){
			cout << input[0];

		}else{
			std::stack<string> abcd;
			//cout << abcd[0];
			
			clear();
			vytvorGraf(input[0],input[1]);
			//qsort(graf
			if(graf.size() > 1)
				vypis();
			else
				cout << "No solution.";
		}
		
		/*if(!cin.eof())
			cout << endl << endl;*/
	}


	return 0;
}

[brianfry713]

Print a newline at the end of the last line.

[mahade hasan]

got TLE plz help me out ........

Code: Select all

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<queue>
#include<vector>
#include<map>
using namespace std;
vector<string>Book;
map<string,string>Map;
typedef pair<string,int>Pair;

bool Difference(string S,int I)
{
   int Count=0,K;
   if(S.size()!=Book[I].size()) return false;
   for(K=0;K<S.size();K++)
   if(S[K]!=Book[I][K]) ++Count;
   
   return (Count==1)? true:false;
}

bool BFS(string A,string B)
{
   int I;
   string S;
   bool Status[25150]={0};
   queue<string>Q;
   Q.push(A);
   while(!Q.empty())
   {
      S=Q.front();
      Q.pop();
      if(S==B) return true;
      for(I=0;I<Book.size();I++)
      if(!Status[I]&&Difference(S,I))
      {
         Status[I]=1;
         Map[Book[I]]=S;
         Q.push(Book[I]);
      }
   }
   return false;
}

int main()
{
   int I,K,L,M,N=0,Tcase,Ans;
   char Input[50],*Tok;
   string A,B;
   //scanf("%d",&Tcase);
   //while(Tcase--)
   //{
      Book.clear();
      //Book.size();
      scanf("\n");
      while(gets(Input)&&strlen(Input))
      {
         Book.push_back(Input);  
      }
      //if(N>0) printf("\n");
      //printf("hgfhfghfghfgh\n");
      N=0;
      scanf("\n");
      while(gets(Input))
      {
         Map.clear();
         //printf("%s\n",Input);
         Tok=strtok(Input, " ");
         //printf("%s\n",Input);
         A=Tok;
         Tok=strtok(NULL, " ");
         B=Tok;
         Map[A]='\0';
         
         if(N>0) printf("\n");
         
         if(BFS(A,B))
         {
            vector<string>V;
            //V.push_back(B);
            while(B!=A)
            {
               V.push_back(B);
               B=Map[B];
            }
            V.push_back(A);
            for(I=V.size()-1;I>-1;I--)
            printf("%s\n",V[I].c_str());
         }
         else
         printf("No solution.\n");
         ++N;
         //Ans=BFS(A,B);
         //printf("%s %s %d\n",A.c_str(),B.c_str(),Ans);
      }
   //}
   return 0;
}

[/color]