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

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:
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
Thanks!
fully understand!

wenzhi cai
New poster
Posts: 9
Joined: Sat Jun 29, 2002 10:59 am
Location: china
Contact:
Can anyone tell me how to solve this problem efficiently? little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 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

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;

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.

ken

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
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:
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

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
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

Code: Select all

ab
ba

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

10029 help! TLE

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;
int ct;

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

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

struct custGraph {
root* words;

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

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

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

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?

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

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

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

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