10150 - Doublets

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

Moderator: Board moderators

xrchz
New poster
Posts: 1
Joined: Tue Oct 05, 2004 8:10 am

Post by xrchz » Tue Oct 05, 2004 8:13 am

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
New poster
Posts: 5
Joined: Sun Oct 10, 2004 11:34 pm

10150 - Doublets

Post by hiro » Sat Oct 30, 2004 8:19 pm

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

}

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: TL on 10150 - Doublets

Post by .. » Sun Nov 28, 2004 7:12 pm

hiro wrote: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.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Jer
New poster
Posts: 10
Joined: Wed Nov 19, 2003 2:07 pm

10150 Doublets

Post by Jer » Sun Feb 20, 2005 3:44 pm

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
New poster
Posts: 22
Joined: Sun Mar 13, 2005 5:04 pm
Location: out there

Post by tRipper » Wed Jul 06, 2005 7:14 pm

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;
}
If I am out of my mind, it's all right with me.

ranger72
New poster
Posts: 1
Joined: Fri Oct 21, 2005 9:49 pm

10150: Doublets -- TLE?

Post by ranger72 » Fri Oct 21, 2005 10:03 pm

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
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

10150 (Doublets) TLE

Post by bluebird » Sun Oct 30, 2005 11:07 pm

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
New poster
Posts: 12
Joined: Mon Oct 17, 2005 2:35 am
Location: Canada

Post by bluebird » Mon Oct 31, 2005 11:51 pm

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
New poster
Posts: 10
Joined: Sat Jan 14, 2006 4:52 pm
Location: Lahore

10150 (Doublets) Testcases required

Post by ahsanlatif » Mon Jan 30, 2006 4:04 pm

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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Thu Aug 31, 2006 5:31 am

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.

User avatar
willima
New poster
Posts: 13
Joined: Wed Dec 07, 2005 1:19 pm
Location: Brazil

Graph?

Post by willima » Fri Oct 20, 2006 1:25 am

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!
"Don't let the day go by
Don't let it end
Don't let the day go by, in doubts
The anwser lis within"

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

Re: 10150 - Doublets

Post by stcheung » Fri Oct 03, 2008 1:34 am

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
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

Re: 10150 - Doublets

Post by diego_engcomp » Wed Sep 09, 2009 3:41 am

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
Last edited by diego_engcomp on Thu Sep 10, 2009 4:01 am, edited 1 time in total.

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

Re: 10150 - Doublets

Post by Angeh » Wed Sep 09, 2009 1:02 pm

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 
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

diego_engcomp
New poster
Posts: 9
Joined: Sat Jul 18, 2009 1:18 am

Re: 10150 - Doublets

Post by diego_engcomp » Wed Sep 09, 2009 4:55 pm

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?

Post Reply

Return to “Volume 101 (10100-10199)”

Who is online

Users browsing this forum: No registered users and 1 guest