10150 - Doublets

[xrchz]

the binary search functions in c++ which return indices (and not just bool) are:
lower_bound
upper_bound
equal_range

they perform binary search on sorted list of data and return either first index where you could insert object without violating ordering, last index, or both indices.

look them up in an stl reference

[hiro]

Hi everybody...
Im having some trouble submitting Doublets...
i always get TL with 10,39 s, but in the ranking lista there's a submission that took about 28s...
I dont lnow why i get TL wiht my time...
Am i doing the right input?

Code: Select all

#include <iostream>
#include <list>
#include <deque>
#include <stdio.h>

using std::cin;
using std::cout;
using std::endl;

#include <map>
#include <string>

std::deque<string> dictionary;
std::map<string, std::deque<string>, std::less<string> > hash;

// Searches if theres a way to get in string sEnd, starting from string sStart
int procuraDoublet( string sStart, string sEnd )
{
	// If strings have different sizes they cant be doublets
	if ( sStart.length() != sEnd.length() )
		return 0;

	// if start string doesnt have any doublet, so there no way 
                // to reach end string
	if ( hash[sStart].front() == "empty" )
		return 0;

	// Otherwise, verify if theres a doublet
	for ( int i = 0; i < hash[sStart].size(); ++i )
		if ( hash[sStart][i] == sEnd )
		{
			cout << hash[sStart][i] << endl;
			return 1;
		}

	// if there wasnt any direct doublet, try second order doublet and so on
	for ( int i = 0; i < hash[sStart].size(); ++i )
		if ( procuraDoublet( hash[sStart][i], sEnd ) )
		{
			cout << hash[sStart][i] << endl;
			return 1;
		}
		
	return 0;	

}

int doublet( string s1, string s2)
{
	if ( s1.length() != s2.length() )
		return 0;
	int nDiff = 0;
	for ( int i = 0; i < s1.length(); i++ )
		if ( s1[i] != s2[i] )
		{
			nDiff++;
			if ( nDiff == 2 )
				return 0;
		}
	return 1;
}

int main()
{
	char entrada[18];
	int dictSize = 0;
	
	std::list<string> d;
	
	
	while (true )        
	{ 
		cin.getline( entrada, 17, '\n' );	
		if ( entrada[0] == '\0')
			break;
		
		d.push_back( entrada );
		if ( hash[entrada].empty() )
			hash[entrada].push_back("empty");
		
	}

	d.unique();
	dictSize = d.size();	

	while ( !d.empty() )
	{
		dictionary.push_back(d.front() );
		d.pop_front();
	}

	for ( int i = 0; i < dictSize; i++ )
	{
		if ( hash[dictionary[i]].front() == "empty" )
				hash[dictionary[i]].pop_front();

		for ( int j = 0; j < dictSize; j++ )
			if ( i != j )
				if ( doublet(dictionary[i], dictionary[j]) )
					hash[dictionary[i]].push_back(dictionary[j]);
	}
string s1, s2;

	while (cin >> s1 >> s2 )        
	{ 
		if (hash[s1].empty() )
			hash[s1].push_back("empty");
		if (hash[s2].empty() )
			hash[s2].push_back("empty");
		
		if (procuraDoublet( s2, s1 ) == 0 )
			cout << "No solution" << endl;
		else
			cout << s2 << endl;
			
		cout << endl;
				
	}

}

[..]

Hi everybody...
Im having some trouble submitting Doublets...
i always get TL with 10,39 s, but in the ranking lista there's a submission that took about 28s...

The 28s submission was submitted before server upgrade(about 2-3 years ago), at that time the server is slower so a larger time limit is given.

As you don't make any explanation on your code, I can't tell if you are using the right algorithm.

[Jer]

Can anyone help me??

I don't know why i got "Runtime Error (SIGSEGV)".

Code: Select all

#include <iostream>
#include <queue>
#include <stdlib.h>
#include <string>
#define maxV 25148 
using namespace std;
struct node
{	
	int v;
 	struct node *next; 
}; 
int V;
struct node *adj[maxV], *z;
char dic[maxV][20];
int val[maxV];
int path[maxV]; 

int comp(const void *a, const void *b)
{
    return(strcmp((char *)a,(char *)b));
}

int bsearch(char a[])
{
	int l = 0, r = V, x, t;
	while(r >= l)	{
		x = (l + r)/2;
		t = comp( a, dic[x]);
  		if(t == 0)	return x;
    	else if(t < 0)	r = x - 1;	  
    	else l = x + 1;
	}
	return -1;
} 


int main(void)
{ 
	struct node *t; 
	int i = 0, j, k, l, len; 
	char tmp[18];
	while(true)	{ 
   		cin.getline( dic[i], 17, '\n');    
      	if ( dic[i][0] == '\0') 
       		break; 
   		i++; 
	} 
	V = i - 1;
 	z = new node;	z->next = z; 
 	for( i = 0; i <= V; i++)	{
  		adj[i] = z;	 
  		adj[i]->v = i; 
	}
 	qsort(dic,V + 1,sizeof(dic[0]),comp);	//sort the words 
    for( i = 0; i <= V; i++)	{
  		len = strlen(dic[i])-1; 
    	for( j = 0; j <= len; j++)	{
     		for( k = 0; k <= 25; k++)	{	 
         		if(dic[i][j] != (char)('a'+ k))	{ 	//find the Doublets 
           			strcpy( tmp, dic[i]);     		
           			tmp[j] = (char)('a' + k);  
           			l = bsearch(tmp); 
           			if(l != -1)	{
           				t = new node;
             			t->v = l;	t->next = adj[i]; 	adj[i] = t;
                	}		
                } 
            } 		 	 
 	    } 
    }    
 	char a[18],b[18]; 
 	bool success; 
  	int sur, des; 
  	queue<int> q; 
  	
	while(cin>>a>>b)          
  	{
		memset(val,-1,sizeof(val));
		success = 0; 
   		sur = bsearch(a);	
      	des = bsearch(b);
		if(sur != -1 && des != -1)	{ 
      		if(sur == des)
				success = 1;
			q.push(sur);
      		val[sur] = sur; 
			while(!q.empty() && !success)	{	//BFS 
       			i = q.front();
         		q.pop();
				for(t = adj[i]; t != z; t = t->next)	{ 
					if(val[t->v] == -1)	{
						q.push(t->v);
              			val[t->v] = i; 
              			if(t->v == des)	{
              				success = 1;
              				break; 
             			}
             		} 
       			} 
       		}
		}
       	if(success)	{		//print the path 
       		i = 1; 
       		path[0] = des; 
       		for(int dad = val[des]; dad != sur ; i++, dad = val[dad])	{
           		path[i] =  dad; 
          	} 
          	path[i] = sur; 
         	for( ; i >= 0; i--)
          		cout<<dic[path[i]]<<endl; 
		} 
		else cout<<"No solution."<<endl;
		cout<<endl; 
	}
    return 0;    
}

[tRipper]

I'm really having trouble with this problem. Can someone tell me why this code gives WA? Basically i use STL set to store all the words and after that BFS to find the solution.

Code: Select all

#include <iostream>
#include <set>
#include <string>

using namespace std;

set <string> dict;
string red,start,end;

void solve(string start, string end) {
     string popis[500],sol[20];
     int pi[500],dno=0,vrh=1;
     popis[0]=start;
     pi[0]=0;
     bool gotovo=false;
     while (dno<vrh && !gotovo) {
           string r=popis[dno];
           for (int i=0; i<r.size(); i++) 
               if (r[i]!=end[i]) {
                  string r2=r;
                  r2[i]=end[i];
                  if (dict.find(r2)!=dict.end()) {
                     popis[vrh]=r2;
                     pi[vrh]=dno;
                     if (r2==end) {
                        gotovo=true;
                        break;
                     }
                     vrh++;
                  }
               }
           dno++;
     }
     if (!gotovo) {
        cout << "No solution." << endl << endl;;
        return;
     }
     
     int natrag=vrh,br=0;
     while (natrag) {
           sol[br++]=popis[natrag];
           natrag=pi[natrag];
     }
     cout << start << endl;
     for (int i=br-1; i>=0; i--) 
         cout << sol[i] << endl;
     cout << endl;
}
                     

int main() {
    getline(cin,red);
    while (red!="") {
          dict.insert(red);
          getline(cin,red);
    }    
    while (cin >> start >> end) {
          if (start.size()!=end.size() || dict.find(start)==dict.end() 
             || dict.find(end)==dict.end()) cout << "No solution." << endl << endl; else
          if (start==end) cout << start << endl << endl; else
          solve(start,end);
    }      
    return 0;
}

[ranger72]

I have implemented this one as a BFS which tries changing each letter of each word to any of the other letters, then uses binary search to check whether it is in the word array.

However, I always get TLE with ~10 seconds. How could I optimize this further?

My code is below:

Code: Select all

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <sstream>
using namespace std;

vector<string> words;
int dist[25143];
int parent[25143];

int binary_search(string s)
{
    int low = -1, high = words.size(), mid;
    while (high - low > 1)
    {
        mid = (high + low) / 2;
        if (words[mid] > s)
            high = mid;
        else
            low = mid;
    }
    if (low == -1 || words[low] != s)
        return -1;
    else
        return low;
}

void bfs(int start, int end)
{
    queue<int> q;
    q.push(start);
    
    dist[start] = 0;
    
    while (!q.empty())
    {
        int thisPos = q.front();
                
        if (thisPos == end)
            break;
        
        q.pop();
        
        for (int i = 0; i < words[thisPos].size(); ++i)
        {
            // Work on changing character i 
            string w = words[thisPos];
            for (int c = 'a'; c <= 'z'; ++c)
            {
                if (c == words[thisPos][i])
                    continue;
                w[i] = c;
                int m = binary_search(w);
                if (m != -1 && dist[m] == -1)
                {
                    // Haven't seen it yet so enqueue
                    dist[m] = dist[thisPos] + 1;
                    parent[m] = thisPos;
                    q.push(m);
                }
            }
        }
    }
    
    if (q.empty())
        cout << "No solution." << endl;
    else
    {
        // Reverse the output order
        stack<string> s;
        int pos = end;
        while (parent[pos] != -1)
        {
            s.push(words[pos]);
            pos = parent[pos];
        }
        cout << start << endl;
        while (!s.empty())
        {
            cout << s.top() << endl;
            s.pop();
        }
    }
}

int main()
{
    string s;
    while (getline(cin, s))
    {
        if (s.size() == 0)
            break;
        
        words.push_back(s);
    }
    
    sort(words.begin(), words.end());
    
    string s1, s2;
    while (getline(cin, s))
    {
        if (s.size() == 0)
            break;
        
        istringstream istr(s);
        istr >> s1 >> s2;
        
        // Initialize arrays
        for (int i = 0; i < words.size(); ++i)
            parent[i] = dist[i] = -1;
        
        int n1 = binary_search(s1), n2 = binary_search(s2);
        
        if (n1 == -1 || n2 == -1)
            cout << "No solution." << endl;
        else
            bfs(n1, n2);
        cout << endl;
    }
}

[bluebird]

This is supposed to be a simple BFS graph problem but for some reason I keep getting TLE.

My program first stores the dictionary into a sorted, unique vector. Then for each pair of words in a test case I just use a simple BFS with the first word as the source vertex. For each word in the chain, I modify the letter at each position from 'a' to 'z', and then use Binary Search to see if the word exists in the dictionary. If it does, I treat it like an adjacent vertex (i.e. mark it as "visited", push the index into the queue etc.). To save time, I also stop the BFS immediately when the destination word is visited. Finally, I go through the predecessor array and reverse the order of the words using a stack before printing it out.

Code: Select all

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

// At most 25,143 words
#define INF 30000


#define DEBUG false

using namespace std;

typedef unsigned short Int;

// Binary Search (Iterative version, to avoid stack overflow)
Int binSrch(vector<string>& dict, string val, Int left, Int right) {

  if(DEBUG) cout<<"Bsearch: "<<val<<'\n';
  Int mid;
  while (left <= right) {
    mid = (left+right)/2;
    if(DEBUG)cout<<"left: "<<left<<"\tmid: "<<mid<<"\tright: "<<right<<'\n';
    if(dict[mid]==val) return mid;
    if(val<dict[mid]) {
      if (mid==0) break;
      right=mid-1;
    }
    else if(val>dict[mid]) left=mid+1;
  }
  return INF;
}

void BFS(vector<string>& dict,
	 vector<Int>& p,
	 Int size,
	 Int& s, Int& d, bool& noSoln) {

  queue<Int> Q;
  string tmp;
  string uStr;
  Int u,v;

  vector<char> visited(size, 'w');
  for(Int i=0;i<size;i++) p[i]=INF;

  visited[s]='g';

  Q.push(s);
  
  while(!Q.empty()) {
    u=Q.front();
    uStr=dict[u];

    if(DEBUG) cout<<"dict[u]: "<<dict[u]<<'\n';

    for(Int i=0;i<uStr.size();i++) {
      for(char j='a';j<='z';j++) {
	tmp=uStr;
	if(tmp[i]!=j) {
	  tmp[i]=j;
	  v=binSrch(dict,tmp,0,size-1);
	  if (v!=INF && visited[v]=='w') {
	    visited[v]='g';
	    p[v] = u;

	    if (v==d) {
	      noSoln=false;
	      return;
	    }
	    Q.push(v);
	  }
	}
      }
    }
    if (DEBUG)cout<<"Q size: "<<Q.size()<<'\n';
    Q.pop();
    visited[u]='b';
  } // while

  noSoln=true;
}

// remove duplicate strings in the vector parameter
void getUnique(vector<string>& v) {
  string cur="";
  for(vector<string>::iterator i=v.begin();i!=v.end();) {
    if (cur!=*i) {
      cur = *i;
      ++i;
    }
    else i=v.erase(i);
  }
}

int main()
{
  string line,fir,sec;
  vector<string> dict;
  vector<Int> p;
  short testcases, numDiff;
  bool noSoln;
  stack<Int> output;
  string * db;
  Int size, firId, secId, prev;
  istringstream instream;

  while(getline(cin,line)&&line!="") dict.push_back(line);
  sort(dict.begin(), dict.end());
  getUnique(dict);

  size = dict.size();

  if(DEBUG)for(Int i=0;i<size;i++)cout<<dict[i]<<'\n';

  testcases=1;
  while(getline(cin,line)&&line!="") {
    instream.clear();
    instream.str(line);
    instream >> fir >> sec;
    if (DEBUG) cout<<"First: "<<fir<<" Second: "<<sec<<'\n';

    firId = INF;
    secId = INF;
    for(Int i=0;i<size;i++) {
      if (dict[i]==fir)	firId = i;
      if (dict[i]==sec) secId = i;
      if (firId != INF && secId != INF) break;
    }
    if (DEBUG) cout<<"ID: "<<firId<<"  "<<secId<<'\n';

    noSoln = false;
    if (firId == INF || secId == INF) noSoln=true;
    else {
      while (!output.empty()) output.pop();
      if (p.empty()) p.resize(size); 
      BFS(dict, p, size, firId, secId, noSoln);

      if(!noSoln) {
	while (secId != firId) {
	  if(p[secId]==INF) {
	    noSoln=true;
	    break;
	  }
	  output.push(secId);
	  secId=p[secId];
	}
	output.push(firId);
      }
    }

    // output

    // print an extra line between test cases
    if(testcases>=2) cout<<'\n';
    testcases++;

    // print the sequence
    if (noSoln) cout<<"No solution."<<'\n';
    else {
      if(DEBUG) cout<<"Yes solution"<<'\n';
      while(!output.empty()) {
	cout<<dict[output.top()]<<'\n';
	output.pop();
      }
    }
  }

  return 0;

}

[bluebird]

I got TLE as well. I had pretty much the same algorithm as yours, but I tried to speed it up by removing the duplicate words in the dictionary, and I used a boolean array instead of an int array to keep track of visited nodes.

[ahsanlatif]

Hello Everyone,
I am getting WA for this problem. I have tested quite a number of inputs for my self but unable to get AC on the OJ.
Can you kindly provide me with some inputs? Is there any thing tricky in this problem?

I am getting WA in 1.5 sec. How much did your AC took?

Waiting for your replies.

[Darko]

I really have a problem with this.. err... problem.

I have no idea how to do it. When people say "do BFS" - search for what? There can be 25k words, so I can't just build the graph. And there can be 16 letters in a word, so I just can't change letters one by one until I find something.

I would understand if both words had a letter in common (although that might be misleading) or if you change one letter in the first word into the corresponding letter in the second and it's guaranteed to be in the dictionary... but, what about this:

Code: Select all

ab
xb
xy
dy
de

ab de

If I look for db or ae, they are not in the dictionary. So I have to try all letters. Now, if those words were 16 letters long...

I just can't convince myself that anything would run in time. But it obviously does. Can someone give me a hint? Or at least tell me what is wrong with my reasoning?

[EDIT] For some reason I thought that there would be 25^16 different words. I thought the same way today when I tried to do 10029 (Edit step ladders). I have no idea why I get stuck with something like that. Of course, it is just 25*16 per word (even less in the case of 10029, but there are other things there). I can't get 10029 to run in time yet (in Java), will come back to 10150 after that one.

[willima]

I've been triying to solve this problem and always get TLE. I thought it was my search and I replaced it for binary search. Then I thought it was dijkstra, and I replaced it for BFS. And now I discovered that my program can't build the graph in the proper time!!

I build the graph bye an O(n^2) algorithm, where for each word I verify whether the others are doblets with it, just like this:

Code: Select all

// montagem do grafo
void montarGrafo ( void ){
	register int i, j;
	
	for ( i = 0; i < N - 1; i++ ){
		for ( j = i + 1; j < N; j++ ){
			if ( doublet ( word[i], word[j] ) ){
				W[i].vizinho.push_back(j);
				W[j].vizinho.push_back(i);
			}
		}
	}
}

Anyone can help me?

Thanks!

[stcheung]

This problem is just BFS, except instead of knowing all the edges beforehand, you would dynamically construct them as you process each node. The trick is to NOT do the doublet checking right at the beginning when you read in the dictionary. Instead, just store them in a hashtable. Then when you do BFS, construct all possible doublets of the word and check which of them are in the hashtable. And oh, I think how you generate all doublets might also matter too if you do it too inelegantly.

If my Java solution can get accepted in <1 sec with this simple approach, I am sure yours can too in more efficient languages.

[diego_engcomp]

Differently of others people on this post, I have been getting WA insted of TL on this problem and I have built an explicit graph and tried to find a path using bfs with the index of the words. My code passed on the test cases that I found here and others that I simulate on uvatoolkit.com. Can anybody helps me? Thanks and sorry for my english.

Code: Select all

Removed After AC

[Angeh]

used hash and binary Search to find all possible adjacent s form the dictionary ( sorted before )
use pointer sort for sorting the dictionary
construct the graph while you need the nodes dont pre-compute the graph
Good Luck

Code: Select all

AC  0.060 

[diego_engcomp]

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?