10029 - Edit Step Ladders

[Shahab]

I have two method to solve your problem, and both of them are related to the size of the strings (but I think the O(t*n) is better than O(n^2) where t refers to the length of the string)

In these two methods, you must find the step ladders exactly from its string (not finding them with checking) for example when you have the word "Step" you can understand that it is adjacent to "Stop".

In the first method , you can take all the words, Sort them with O(n logn) and then for each word find its adjacents by binary search. this method is O(t*n*logn). But the second is O(t*n).

The second method uses hash instead of Sorting and Searching with binary search. (Ofcourse I ignore problems that may happen by hashing). in this method you can make your graph with the above idea but not having the sort and search cost. but also having the hash cost.

[SilVer DirectXer]

input:
cat
dig
dog
fig
fin
fine
fog
log
wine

output:
5

why it is 5?
maybe i am misunderstanding the question.
the task is that we need to find out the smallest step for transforming each pairs of word from the top one by one..(cat->dig),(dig ->dog), (dog->fig),.....
and among these smallest number, we figure out the largest one?

[Whinii F.]

The task is to find the "longest" step ladder, which is a sequence of words that each words can be "transformed from" the previous word in the sequence.

For the sample input, the longest step ladder is
"dig fig fin fine wine". Which consists of four changing transformations and one adding transformation.

[SilVer DirectXer]

Thanks!
fully understand!

[wenzhi cai]

Can anyone tell me how to solve this problem efficiently?

[little joey]

http://online-judge.uva.es/board/viewtopic.php?t=3822

[changgica]

This is my code :

Code: Select all

//++++++++++++++++++++++++++++++++++++++++
//  10029 - Edit Step Ladders
//  (red)
//  [url]http://acm.uva.es/p/v100/10029.html [/url]
//++++++++++++++++++++++++++++++++++++++++

#include <iostream.h>
#include <stdio.h>
#include <string.h>
#include <limits.h>
//===========================================
#define MAX_N 25011
#define MAX_ST 20

int n;
int le[MAX_N];
char s[MAX_N][MAX_ST];

int result;

int c[MAX_N];


//===========================================
void input()
{
    int i;
    n=0;
    while (scanf("%s",s[++n])==1);

    --n;

    for (i=1;i<=n;++i)
        le[i]=strlen(s[i]);
}
//============================================
void sort(int first, int last)
{
    int i,j,z;
    char g[MAX_ST];
    char u[MAX_ST];

    i=first; j= last;
    strcpy(g,s[(i+j)/2]);

    do{
        while (strcmp(s[i],g)==-1) ++i;
        while (strcmp(s[j],g)== 1) --j;

        if (i<=j)
        {
            strcpy(u,s[i]);
            strcpy(s[i],s[j]);
            strcpy(s[j],u);
            z=le[i]; le[i]=le[j]; le[j]=z;
            ++i;
            --j;
        }
    } while (i<=j);

    if (i<last)  sort(i,last);
    if (j>first) sort(first,j);
}
//===========================================
// search u in the array s[1..x]
int search(int x, char u[])
{
    int first,last,g;
    int cmp;

    first=1; last=x;
    while (first<=last)
    {
        g=(first+last)/2 ;

        cmp=strcmp(u,s[g]);

        if (cmp==0)        
            return c[g];
        else
        if (cmp==1)
            first=g+1;
        else
            last=g-1;
    }

    return -1;
}
//============================================
void calculate(int x)
{
    int i,j,max,search_result;
    char u[MAX_ST];

    max=1;

    // deleting
    for (i=0;i<le[x];++i)
    {
        for (j=0;j<i;++j)
            u[j]=s[x][j];
        for (j=i+1;j<=le[x];++j)
            u[j-1]=s[x][j];
        
        search_result=search(x-1,u);

        if (max<search_result+1) max=search_result+1;
    }


    // replacing
    for (i=0;i<le[x];++i)
    {
        strcpy(u,s[x]);
        
        for (j='a';j<='z';++j)
        if (j!=s[x][i])
        {
            u[i]=j;
            search_result=search(x-1,u);

            if (max<search_result+1) max=search_result+1;
        }
    }

    //inserting
    for (i=0;i<=le[x];++i)
    {
        for (j=0;j<i;++j)
            u[j]=s[x][j];
        for (j=i+1;j<=le[x]+1;++j)
            u[j]=s[x][j-1];
        
        for (j='a';j<='z';++j)
        {
            u[i]=j;
            search_result=search(x-1,u);

            if (max<search_result+1) max=search_result+1;
        } 
    }

    // updating
    c[x]=max;
    if (result<max) result=max;
}
//============================================
void solve()
{
    int i;    

    if (n==0) { result=0;return;}
    result=1;
    c[1]=1;    
    
    for (i=2;i<=n;++i)
        calculate(i);
}
//============================================
void output()
{
    printf("%d\n",result);
}
//============================================
int main()
{
   freopen("test.txt","r",stdin);
    input();
//    sort(1,n);
    solve();
    output();
    return 0;
}

i did submit my program for several times. I have tested any trick i could guess. But it was always WA.

plz help me.

thanks in advance

ken

[Maxim]

I have two method to solve your problem, and both of them are related to the size of the strings (but I think the O(t*n) is better than O(n^2) where t refers to the length of the string)

...

The second method uses hash instead of Sorting and Searching with binary search. (Ofcourse I ignore problems that may happen by hashing). in this method you can make your graph with the above idea but not having the sort and search cost. but also having the hash cost.

I don't understand how you do it regardless to the size of alphabet! I've implemented the method with hashing, but I get TLE. Distribution in hash table is almost ideal. I set hash table size to M > N (really large table), where N is # of words in dictionary. I've noticed only words which differ at last letter have "adjacent" hash values.
So, my algorithm for constructing a graph has time complexity O(N*T*A), where T is word length, and A is size of alphabet.

How to do it without factor A?

Best Regards,
Maxim

[Whinii F.]

I don't think he completely bypassed the size of the alphabet, but I think he ignored it because it could be treated as a constant.

You can pass the time limit with hashing too, if you have a good implementation. Check out little joey's comments at:
http://online-judge.uva.es/board/viewto ... f8298c32a5

[Maxim]

I don't think he completely bypassed the size of the alphabet, but I think he ignored it because it could be treated as a constant.

You can pass the time limit with hashing too, if you have a good implementation. Check out little joey's comments at:
http://online-judge.uva.es/board/viewto ... f8298c32a5

Yeah, I've read that topic. I know it's a constant, but a "large" one. It does matter because 26 times slower can be crucial. Anyway, in last post I said my algorithm had time complexity O(N*T*A), and that wasn't true. It was O(N*A*T**) actually because hash function I used takes time linear in size of string to be hashed.
Problem was in data structure I used for representing the graph. I used set<int> from STL and that was killing program running time. Eventually I got AC with 4.771 secs.

Thanks to all!

Maxim

[Examiner]

Code: Select all

ab
ba

[drewsome]

Hi,

I've read the other posts on 10029, and from what I've read it seems to me my implementation should work. I think the culprit may be in my calcVariations() function, where I generate all possible edit steps for a string.. maybe STL string is too slow for this? In any case, I wrote my own linked list data structure for the graph which I thought would speed things up enough to get AC, but apparently not..

Any help would be great appreciated! Thanks

Code: Select all

// this code written by Andrew Rothbart, 2005
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
const int MAXSIZE = 16; // size of largest word in dictionary

string dict[25000];
int ct;

struct node {
	node* next;
	int val;
};

struct root {
	node *next;
	int length;
};

struct custGraph {
	root* words[25000];
	
	void add(int pos, int ins) {
		
		root* n = words[pos];
		node* temp = new node;
		
		temp->val = ins;
		temp->next = n->next;
		n->next = temp;
		
		return;
	}
	
	bool contains(string str) {
		return binary_search(dict, dict+ct, str);
	}
		
};

custGraph graph;

int calcLength(int index) {
	root *curr = graph.words[index];
	if (curr->length) return curr->length;
	

	node *nd = curr->next;
	int max = 0, temp;

	while (nd != 0) {
		temp = calcLength(nd->val);
		if (temp > max) max = temp;
		nd = nd->next;
	}
	
	curr->length = max + 1;
	return max + 1;
}

// connects graph.words[pos] to str if str is in the graph (ie. dict)
void addToGraph(int pos, string str) {
	
	string* lb = lower_bound(dict, dict+ct, str);
	
	if (*lb != str) return;
	graph.add(pos, lb - dict);
	
	return;
}

void calcVariations(string str, int pos) {
	
	string temp;
	
	// try deleting letters
	for (int i = 0; i < str.size(); i++) {
		temp = str; temp.erase(i,1);
		if (!temp.size() || temp < str) continue;
		addToGraph(pos, temp);
	}
	
	// try changing letters
	for (int i = 0; i < str.size(); i++) {
		for (int k = (int)str[i]+1; k <= 122; k++) {
			temp = str; temp[i] = (char)k;
			addToGraph(pos, temp);
		}
	}			
	
	// try adding letters
	if (str.size() >= MAXSIZE) return;
	
	for (int i = 0; i <= str.size(); i++) {
		for (int k = 97; k <= 122; k++) {
			string c;
			temp = str; c += (char)k;
			temp.insert(i, c.c_str());
			if (temp < str) continue;
			addToGraph(pos, temp);
		}
	}
	
	return;
}


int main() {
	
	string str;
	ct = 0;
	
	while (cin >> str) dict[ct++] = str;
	
	for (int i = 0; i < ct; i++) {
		root* n = new root;
		n->next = 0;
		n->length = 0;
		graph.words[i] = n;
		
		calcVariations(dict[i], i);
	}

	int max = 1, temp;
	for (int i = 0; i < ct; i++) {
		temp = calcLength(i);
		if (temp > max) max = temp;
	}
	
	cout << max << endl;
	
	return 0;
}
	

[SDiZ]

May anyone explain the "hash" method you use?

How do you check if two hash is an editing step?

or do you generate all possible editing steps? (i think this would be very large&slow)

[SDiZ]

I get a TLE using any algorithm I have on mind, anyone can give me some hints?
I suspect my string ops are too slow, but i have no ide how to improve it.

Code: Select all

[SDiZ]

my program get AC after change from STL map to hash_map.

STL map in gcc use rb_tree, which is slow in inserting.