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

Shahab
New poster
Posts: 24
Joined: Sun Nov 10, 2002 2:17 pm

Post by Shahab » Sun Nov 10, 2002 2:57 pm

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
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

10029

Post by SilVer DirectXer » Tue Jul 22, 2003 7:34 pm

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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sat Aug 02, 2003 7:58 am

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.
JongMan @ Yonsei

SilVer DirectXer
New poster
Posts: 39
Joined: Wed Jan 22, 2003 11:02 am

Post by SilVer DirectXer » Fri Aug 29, 2003 6:59 am

Thanks!
fully understand!

wenzhi cai
New poster
Posts: 9
Joined: Sat Jun 29, 2002 10:59 am
Location: china
Contact:

Post by wenzhi cai » Thu Sep 04, 2003 6:59 pm

Can anyone tell me how to solve this problem efficiently? :(

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Sep 04, 2003 7:10 pm


changgica
New poster
Posts: 3
Joined: Mon Sep 16, 2002 6:27 pm
Location: Singapore

10029 - plz help, i can't find what is wrong with my program

Post by changgica » Mon Sep 22, 2003 5:43 pm

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. :evil:

plz help me.

thanks in advance

ken

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim » Sat Feb 14, 2004 9:34 pm

Shahab wrote: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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Sat Feb 14, 2004 11:11 pm

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
JongMan @ Yonsei

User avatar
Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

Post by Maxim » Sun Feb 15, 2004 4:48 pm

Whinii F. wrote: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
New poster
Posts: 27
Joined: Thu Feb 19, 2004 1:19 pm

10029 Test Case

Post by Examiner » Thu Feb 19, 2004 1:24 pm

Code: Select all

ab
ba

drewsome
New poster
Posts: 16
Joined: Mon Dec 01, 2003 1:20 am
Contact:

10029 help! TLE

Post by drewsome » Thu Jul 07, 2005 8:53 am

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
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

editing step with Hash?

Post by SDiZ » Thu Aug 11, 2005 2:09 pm

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
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

TLE

Post by SDiZ » Thu Aug 11, 2005 6:17 pm

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.

SDiZ
New poster
Posts: 13
Joined: Fri Aug 05, 2005 12:20 pm
Location: Hong Kong
Contact:

AC

Post by SDiZ » Fri Aug 12, 2005 7:29 pm

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

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

Post Reply

Return to “Volume 100 (10000-10099)”