10029 - Edit Step Ladders

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

Moderator: Board moderators

vivekv16
New poster
Posts: 1
Joined: Fri Nov 03, 2006 1:39 am

Runtime error (0.000 CPU, Min memory)

Post by vivekv16 » Tue Nov 28, 2006 5:13 am

Im getting Runtime error on my code for 10029, It gives a segmentation fault and Im not sure if I am using that large a chunk of memory. Anyway, I thought I'll see if you guys can help me out before I give up. My algo in short is this: hash all words into hash-table, for each word generate all possible edit-steps and check hash-table to see if it exists. Build a graph and do DFS. Im sorry the code's huge. :oops:

Code: Select all

#include <iostream>
#include <cmath>
#include <string.h>
#include <vector>
#include <cstdlib>
#include <cstdio>
using namespace std;

#define HASH_TABLE_SIZE 75000
#define WHITE 0
#define GRAY 1
#define BLACK 2

typedef struct hash_table_t_st{
  int wordIndex;
  struct hash_table_t_st *next;
}hash_table_t;

char **dict;
int n;
hash_table_t **hash_table;
int conflicts=0;
vector<int> *adjacency_list;
int *vertex_color;
int max_esl=0;

void insert_hash_table(int hash_index, int wordIndex)
{
  hash_table_t *temp;
  if(hash_table[hash_index]==NULL)
    {
      hash_table[hash_index] = (hash_table_t *) calloc(1, sizeof(hash_table_t));
      hash_table[hash_index]->wordIndex = wordIndex;
      hash_table[hash_index]->next = NULL;
    }
  else
    {
      temp = hash_table[hash_index];
      hash_table[hash_index] = (hash_table_t *) calloc(1, sizeof(hash_table_t));
      hash_table[hash_index]->wordIndex = wordIndex;
      hash_table[hash_index]->next = temp;
      conflicts++;
    }
}

void hash_word(int wordIndex)
{   
  unsigned int iter=0, hash_index, value=0;
  int shift=6;
  unsigned int mask = ~0U << (8*sizeof(unsigned int) - shift);
  while(dict[wordIndex][iter])
    {
      value = (value & mask) ^ (value << shift) ^ dict[wordIndex][iter];
      iter++;
    }
  
  hash_index = (value%HASH_TABLE_SIZE);
  insert_hash_table(hash_index, wordIndex);  
}

void hash_dict()
{
  for(int i=0; i<n; i++)
    hash_word(i);
}

void print_dict()
{
  for(int i=0; i<n; i++)
    cout << dict[i] << endl;
}

void draw_edge(int v1, int v2)
{
  adjacency_list[v1].push_back(v2);
}

int get_index(char *word)
{
  hash_table_t *h_iter;
  unsigned int iter=0, hash_index, value=0;
  int shift=6;
  unsigned int mask = ~0U << (8*sizeof(unsigned int) - shift);
  while(word[iter])
    {
      value = (value & mask) ^ (value << shift) ^ word[iter];
      iter++;
    }
  hash_index = (value%HASH_TABLE_SIZE);
  h_iter = hash_table[hash_index];
  if(h_iter == NULL)
    return -1;
  else
    while(h_iter)
      {
        if(strcmp(dict[h_iter->wordIndex], word) == 0)
          return h_iter->wordIndex;
        else
          h_iter = h_iter->next;
      } 
  return -1;
}

void compute_edit_step_chain(int index)
{
  char add_edit_step[16], sub_edit_step[16], change_edit_step[16];  
  int iter=0;
  const int len=strlen(dict[index]);
  int i, idx;
  
  for(int pos=0; pos<len; pos++)
    {
      if(len < 16)
        {
          for(i=0; i<26; i++)
            {
              memset((char *) add_edit_step, '\0', 16);
              strncpy((char *) &add_edit_step,dict[index], pos);
              add_edit_step[pos] = char(97+i);
              strncat((char *) &add_edit_step[pos+1], (char *) &dict[index][pos], len-pos);
              idx = get_index((char *) add_edit_step);
              if(idx>=0)
                draw_edge(index, idx);
            }
        }
       if(len > 0)
        {
              memset((char *) sub_edit_step, '\0', 16);        
              strncpy((char *) &sub_edit_step, dict[index], pos);
              strncat((char *) &sub_edit_step[pos], (char *) &dict[index][pos+1], len-(pos+1));
              idx = get_index((char *) sub_edit_step);
              if(idx>=0)
                draw_edge(index, idx);
        }        
       for(i=0; i<26; i++)
         {
           memset((char *) change_edit_step, '\0', 16);
           strcpy((char *) &change_edit_step, dict[index]);
           if(change_edit_step[pos]!=char(97+i))
             {
             change_edit_step[pos]=char(97+i);
             idx = get_index((char *) change_edit_step);
             if(idx>=0)
               draw_edge(index, idx);
             }
         }       
    }
}

int dfs(int vertex)
{
  vertex_color[vertex] = GRAY;
  int max_depth=1, depth=1, i=0, iter=0; 
  do
    {
      iter = (adjacency_list[vertex])[i];     
      if(vertex_color[iter]==WHITE)
        depth+= dfs(iter);
      max_depth>?=depth;
      i++;      
    }while(i < adjacency_list[vertex].size());
  vertex_color[vertex] = BLACK;
  return max_depth;  
}

void compute_longest_esl()
{
  for(int i=0; i<n; i++)
    {
      if(adjacency_list[i].empty())
        compute_edit_step_chain(i);
    }
  for(int i=0; i<n; i++)
    {
      if(adjacency_list[i].empty())
        vertex_color[i]=BLACK;
      else if(vertex_color[i] == WHITE)
        max_esl >?= dfs(i);
    }
}

int main()
{
  n=0;
  char inp[16];
  hash_table = (hash_table_t **) calloc (HASH_TABLE_SIZE, sizeof(hash_table_t *));  
  dict = (char **) calloc(25000, sizeof(char *));
  while (cin >> inp)
    {
      dict[n]=(char *) calloc(strlen(inp),sizeof(char));
      strcpy(dict[n],inp);
      n++;
    }
  vertex_color = (int *) calloc(n, sizeof(int));
  adjacency_list = (vector<int> *) calloc(n, sizeof(vector<int>));
  hash_dict();  
  compute_longest_esl();
  if(max_esl > 0)
    cout << max_esl-1 << endl; 
  else 
    cout << 0;
  for(int i=0;i<n;i++)
    free(dict[i]);
  free(dict);
  free(adjacency_list);
  free(vertex_color);
  return 0;
}
Thanks. :oops: :oops: :oops: :oops: :oops:

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Mon Jan 29, 2007 8:03 am

little joey wrote: I haven't tried, but I think 0 seconds isn't even enough to read the input, so all those on the top of the list are probably cheating little w@nk3rs.
Well, I finally solved this one and then I saw those 0.000's... and checked. This program runs in 0.010:

Code: Select all

#include <stdio.h>
int main(){
        char s[32];
        while(gets(s) != NULL);
        return 0;
}

User avatar
seulkiro
New poster
Posts: 6
Joined: Sun Feb 15, 2004 2:13 am
Location: Canada
Contact:

Re: Runtime error (0.000 CPU, Min memory)

Post by seulkiro » Thu Feb 08, 2007 6:55 pm

vivekv16 wrote:My algo in short is this: hash all words into hash-table, for each word generate all possible edit-steps and check hash-table to see if it exists. Build a graph and do DFS. Im sorry the code's huge. :oops:
I don't think that DFS is required to solve this problem. My accepted program is very similar to yours in structure. What I do is keep track of the depth of each node as I build the graph. And print out the biggest value.
waikiki..

Karim
New poster
Posts: 7
Joined: Sun Sep 24, 2006 4:11 pm

10029 TLE

Post by Karim » Wed Mar 14, 2007 5:52 pm

I tried to solve the problem but i am getting TLE

My algorithm is :

1) Read the words and insert in map
2) generate all edit step words from each word (i) and if the word

exist then add edge between word (i) and the other word
3) DFS to get Max depth

I think it works in 25000*16*26*(log 25000)


can anyone tell me how to optimize it or another faster way

Thanks

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
 
string name[25002];
int n=1;
int m=-1;
vector<int> adjl[25001];
 
string del(int i,int j)
{
	string s=name[i];
	s.erase(s.begin()+j);
	return s;
}
 
string chan(int i,int j,int k)
{
	string s=name[i];
	s[j]=(char)(k);
	return s;
}
 
string add(int i,int j,int k)
{
	if(j!=0)
	{
		string s=name[i].substr(0,j);
		s+=(char)(k+'a');
		s+=name[i].substr(j);
		if(s.length()>16)
			return "";
		return s;
	}
	else
	{
		string c=name[i];
		c= (char)(k+'a') + c;
		return c;
	}
}
map<string,int> mm;
int bin_search(string s)
{
	return mm[s]==0?-1:mm[s];
}
 
void DFS(int ind,int dep)
{
	if(dep>m)
		m=dep;
	int i;
	for(i=0;i<adjl[ind].size();i++)
	{
		DFS(adjl[ind][i],dep+1);
	}
}
	
 
 
int main()
{
	int i,j,k,l;
	//freopen("d.in","rt",stdin);
	//freopen("d.out","wt",stdout);
	while(1)
	{
		cin>>name[n++];
		if(cin.fail())
			break;
		mm[name[n-1]]=n-1;
	}
	string s;
	int x;
	for(i=1;i<n;i++)
	{
		for(j=0;j<name[i].length();j++)
		{
			s=del(i,j);
			x=bin_search(s);
			if(x!=-1&&x>i)
				adjl[i].push_back(x);
			for(k=name[i][j];k<='z';k++)
			{
				s=chan(i,j,k);
				x=bin_search(s);
				if(x!=-1&&x>i)
					adjl[i].push_back(x);
				if(name[i].length()!=16)
				{
					s=add(i,j,k);
					x=bin_search(s);
					if(x!=-1&&x>i)
						adjl[i].push_back(x);
				}
			}
		}
		if(name[i].length()!=16)
		{
			for(k=name[i][j];k<='z';k++)
			{
				if(name[i].length()==16)
					break;
				s=add(i,j,k);
				x=bin_search(s);
				if(x!=-1&&x>i)
				adjl[i].push_back(x);
			}
		}
	}
	for(i=1;i<n;i++)
	{
		DFS(i,1);
	}
	cout<<m<<endl;
    return 0;
}
[/code]

bestyt
New poster
Posts: 3
Joined: Tue Nov 04, 2003 7:11 am

Post by bestyt » Wed Jun 13, 2007 7:37 am

Hi,

I'm trying to solve this problem with almost same algorithm you've got.
BUT, I don't still have AC..I'm tottely depressed.

First, make hash table
Second, make possible sequence each one word. And then searching hash table whether subsequence is in or not.
Third, If it is existed, save it in array. and do loop until end of dictionary.

It worked on my handcraft sample input data. BUT I got WA..
Would you provide me OUTPUT coresponding input below?

Code: Select all

aaaaaa
aaaaaaa
aaaaaah
aaaaah
aaaah
aaah
aaarg
aaarge
aaarh
aabrge
aacrd
aacre
aaraah
aard
araah
ard
arde
arded
ardev
raah
rdev
vaah
vaahe
VaahB
I got

Code: Select all

9
Thanks in advance.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 13, 2007 2:49 pm

Code: Select all

VaahB
is not a correct input since the given input only has lowercase letters. So,

Input:

Code: Select all

aaaaaa
aaaaaaa
aaaaaah
aaaaah
aaaah
aaah
aaarg
aaarge
aaarh
aabrge
aacrd
aacre
aaraah
aard
araah
ard
arde
arded
ardev
raah
rdev
vaah
vaahb
vaahe
Output:

Code: Select all

11
Hope it helps.

Edit : The input wasnt right. But now its fixed.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Post by andysoft » Thu Jul 12, 2007 2:45 pm

but we need (n^2-n)/2 operations to do it - that's too big even for cpp.
Now I lay me down to sleep...
my profile

maxdiver
Learning poster
Posts: 51
Joined: Tue Sep 04, 2007 2:12 pm
Location: Russia, Saratov
Contact:

Post by maxdiver » Sun Oct 07, 2007 12:51 pm

Please could anybody send me the solution of this problem?

I tried to solve it with hashing + DP, but i get WA with 0.7 sec :(

Thanks.

rmpowell77
New poster
Posts: 5
Joined: Fri Aug 25, 2006 11:42 pm

Post by rmpowell77 » Mon Mar 31, 2008 6:10 am

Jan wrote: Output:
10
Hope it helps.
My submission just got AC, and I get 11 for the output.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: question about 10029 (Edit Step Ladder)

Post by Jan » Tue Apr 01, 2008 9:54 pm

The reason is simple. The input was not fully correct (not sorted). The problem states..
The input to your program consists of the dictionary - a set of lower case words in lexicographic order - one per line
However, thanks for showing that. I am updating my previous post.
Ami ekhono shopno dekhi...
HomePage

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10029 - Edit Step Ladders

Post by andysoft » Sun Dec 21, 2008 1:52 pm

Hey, is there any way to solve this problem with my approach? I get TLE. And my method is as following:
read all words from dictionary
for each word make all transformations (848 transformations totally for remove, add and insert character, I think)
and for each transformed word make a binary search to know, if it was in dictionary

and, of course, we keep maximum and so on.

The method is correct, but my both implementations in C++ with STL and Pascal with optimized code without calling procedures - they give Time Limit.
Any idea on how to improve this? Speed it up a little bit... There are 100 million operations, it is many, but not too many I think.

Thank you.
Now I lay me down to sleep...
my profile

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10029 - Edit Step Ladders

Post by andysoft » Sun Dec 21, 2008 2:01 pm

just laid in bed a little and thought of an improvement.
I can use hashing to check if the word is in dictionary within O(1) time, and not within O(log 25000) time.
But to hash a string of lowercase chars of length 16, we need 43608742899428874059776 bits of memory, and this is too much.
Of course it's possible to think of some more efficient hashing functions, but in this case I should handle collisions, but I have no experience of handling collisions...
Am I going in right direction in my thoughts?

PS and if I decide to use STL hash_map, then how should I include it?
#include <hash_map> gives compilation error both on UVa and on my MinGW...
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10029 - Edit Step Ladders

Post by mf » Sun Dec 21, 2008 2:55 pm

Handling collisions is the heart of any hash-table.
Two popular schemes are open addressing and chaining.

Alternatively, instead of hash-tables, you can use tries.
Their worst-case complexity of lookup is the same as average-case complexity of hashing - O(length of string). (In practice though they tend to be slower than hashing because they're less friendly to CPU caches)

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:

Re: 10029 - Edit Step Ladders

Post by andysoft » Sun Dec 21, 2008 3:00 pm

Will it then pass the time limit?
Now I lay me down to sleep...
my profile

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10029 - Edit Step Ladders

Post by mf » Sun Dec 21, 2008 3:03 pm

I've used hashing with chaining, it passes in 1.5 seconds.

Post Reply

Return to “Volume 100 (10000-10099)”