10029 - Edit Step Ladders
Moderator: Board moderators
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Re: 10029 - Edit Step Ladders
and how should an efficient hashing function look like? I have idea only about one which takes many gigabytes of memory...
Now I lay me down to sleep...
my profile
my profile
Re: 10029 - Edit Step Ladders
Take that function modulo hash table's size.
And generally it's a good idea to make hash table's size to be at least twice the number of elements you want to put in it, and make it a prime (for chaining)
And generally it's a good idea to make hash table's size to be at least twice the number of elements you want to put in it, and make it a prime (for chaining)
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Re: 10029 - Edit Step Ladders
Hey again.
I have implemented hashing, but it doesn't solve my problem - I keep getting TLE (there are 13 of them already)...
I am in complete despair...
Here is how I do hashing:
I followed your advice on chaining, I implement it using linked list (in one direction).
This is how I insert element to list
This is how I get index of word in the dictionary by word itself
Here is my entire code, but I don't think it is useful now.
I have implemented hashing, but it doesn't solve my problem - I keep getting TLE (there are 13 of them already)...
I am in complete despair...
Here is how I do hashing:
Code: Select all
function getHash (const s: str16): longint;
begin
getHash := 0;
tt := 1; //1, 26, 26^2, 26^3, ..., 26^16
for tti:=1 to length(s) do //all the length
begin
getHash := (getHash + (tt * (ord(s[tti])-ord('a')+1)) mod MAXHASH) mod MAXHASH; //26^n * ordinal_of_the_character
tt := (tt * 26) mod MAXHASH; // 26^n => 26^(n+1)
end
end;
This is how I insert element to list
Code: Select all
procedure insList (const s: str16; const i:integer);
begin
tt := getHash (s);
tt2 := new (prec);
(tt2^).ind := i;
(tt2^).next:= hashMap[tt];
hashMap[tt] := tt2;
end;
Code: Select all
function getInd (const s: str16): longint;
var
t: prec;
begin
tt := getHash (s); //keep hash in 'tt'
if hashMap[tt] = nil then //if list with index 'tt' is empty, then word is not in the dictionary
begin
getInd := -1;
exit;
end;
t := hashMap[tt];
while t<>nil do //iterate through all the nodes in the linked list and compare them with given word..
begin
if a[(t^).ind] = s then
begin
getInd := (t^).ind;
exit;
end;
t := (t^).next;
end;
getInd := -1;
end;
Code: Select all
{$R-}{$S-}{$Q-}{$B-}
program uva10029Solution;
type
str16 = string[16];
const
MAXHASH = 999979; //prime number
type
prec = ^rec;
rec = record
ind: integer;
next: prec;
end;
var
a: array [0..25000] of str16;
b: array [0..25000] of longint;
hashmap: array [0..MAXHASH] of prec;
s,s1,t,t1: str16;
i,j,k,l,m,n: longint;
ans: longint;
ch,tc: char;
left,right,middle,wm: longint;
maxval,maxind: longint;
tt,tti: longint;
tt2: prec;
function getHash (const s: str16): longint;
begin
getHash := 0;
tt := 1;
for tti:=1 to length(s) do
begin
getHash := (getHash + (tt * (ord(s[tti])-ord('a')+1)) mod MAXHASH) mod MAXHASH;
tt := (tt * 26) mod MAXHASH;
end
end;
function getInd (const s: str16): longint;
var
t: prec;
begin
tt := getHash (s);
if hashMap[tt] = nil then
begin
getInd := -1;
exit;
end;
t := hashMap[tt];
while t<>nil do
begin
if a[(t^).ind] = s then
begin
getInd := (t^).ind;
exit;
end;
t := (t^).next;
end;
getInd := -1;
end;
procedure insList (const s: str16; const i:integer);
begin
tt := getHash (s);
tt2 := new (prec);
(tt2^).ind := i;
(tt2^).next:= hashMap[tt];
hashMap[tt] := tt2;
end;
begin
ans := 0;
for i:=0 to MAXHASH do
hashMap[i] := nil;
while not eof do
begin
readln (s);
l := length(s);
inc (n);
a[n] := s;
insList(a[n],n);
if n=1 then
begin
ans := 1;
b[1] := 1;
continue;
end;
maxval := 0;
//transformations
// 1) change
t := s;
for i:=1 to l do
begin
tc := t[i];
for ch:='a' to 'z' do
begin
if ch=tc then continue;
t[i] := ch;
if (t>s) then break;
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
t[i] := tc;
end;
// 2) remove
for i:=1 to l do
begin
t := s;
delete (t,i,1);
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
// 3) add
for i:=1 to l+1 do
begin
t := s;
insert('#',t,i);
for ch:='a' to 'z' do
begin
t[i] := ch;
if t>s then break;
j := getInd(t);
if j=-1 then continue;
if b[j]>maxval then
begin
maxval := b[j];
maxind := j;
end;
end;
end;
if maxval = 0 then
b[n] := 1
else
begin
b[n] := maxval + 1;
if b[n]>ans then
ans := b[n];
end;
end;
for i:=0 to MAXHASH do
begin
while hashMap[i]<>nil do
begin
tt2 := (hashMap[i]^).next;
dispose(hashMap[i]);
hashMap[i] := tt2;
end;
end;
writeln (ans);
end.
Now I lay me down to sleep...
my profile
my profile
Re: 10029 - Edit Step Ladders
My code implements almost exactly the same algorithm, so any possible difference in runtime is in constant factors. I can suggest only a couple of things:
1) I think in a declaration like this one, parameter s will be passed by-value (But maybe I'm wrong, I haven't used pascal for long time). Try to make it a pass-by-reference parameter, with 'var' modifier.
2) In your getHash function, you do 3 divisions for each string's character, you can reduce that number to just 1. Here's how I compute hashes in my program:
3) Judge's g++ compiles C++ programs with enabled optimizations (-O2 flag), but I don't know this is so for fpc. If none of the above helps, try to rewrite and submit your program in C++.
1) I think in a declaration like this one, parameter s will be passed by-value (But maybe I'm wrong, I haven't used pascal for long time). Try to make it a pass-by-reference parameter, with 'var' modifier.
Code: Select all
function getInd (const s: str16): longint;
Code: Select all
#define HDIV 533879
int lookup(const char *s, int add = -1) {
int hash = 0;
for (int i = 0; s[i]; i++) {
hash = hash * 31 + s[i] - 'a';
if (hash >= HDIV) hash %= HDIV;
}
...
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Re: 10029 - Edit Step Ladders
HDIV is your hash map size, right? okay, thanks for the info! I will try to implement it this way..
by the way, should I use STL string or just character arrays if I decide to write in C++?
by the way, should I use STL string or just character arrays if I decide to write in C++?
Now I lay me down to sleep...
my profile
my profile
Re: 10029 - Edit Step Ladders
Yesandysoft wrote:HDIV is your hash map size, right?
Character arrays are faster.by the way, should I use STL string or just character arrays if I decide to write in C++?
-
- Experienced poster
- Posts: 109
- Joined: Sat Jun 23, 2007 9:53 pm
- Location: Brest, BELARUS
- Contact:
Re: 10029 - Edit Step Ladders
mf, man, I thank you so much, with your smart hashing it's accepted even in Pascal 
You r truly a guru like it's written below your avatar.

You r truly a guru like it's written below your avatar.
Now I lay me down to sleep...
my profile
my profile
Re: 10029 - Edit Step Ladders
Got AC By a perfect implementation of On2 LIS Algorithm
IT Doesn't need Hash or So on,pay attention what is happening in The N2 Loop

IT Doesn't need Hash or So on,pay attention what is happening in The N2 Loop


>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)
Beliefs are not facts, believe what you need to believe;)
-
- Experienced poster
- Posts: 145
- Joined: Thu Aug 14, 2003 8:42 am
- Location: Mountain View, California
- Contact:
Re: 10029 - Edit Step Ladders
I got A.C. by using the unordered_map in TR1 with 1.6 sec. Just wondering how to pass it with O(n^2) implementation. 

Have you ever...
- Wanted to work at best companies?
- Struggled with interview problems that could be solved in 15 minutes?
- Wished you could study real-world problems?
-
- New poster
- Posts: 22
- Joined: Wed May 21, 2014 10:16 am
Re: 10029 - Edit Step Ladders
this is a irritating problem
here is my code
instead of checking all possible string set
find all the edit steps of a string and apply binary search
here is my code
instead of checking all possible string set
find all the edit steps of a string and apply binary search
Code: Select all
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <map>
#include <vector>
#define max 26000
using namespace std;
int dp[max];
vector<string> v;
vector<int> adj[max];
int bin_search(string s,int low,int high)
{
if(low>high)
return 0;
int mid=(low+high)/2;
if(v[mid]==s)
return mid;
if(v[mid]>s)
return bin_search(s,low,mid-1);
else
return bin_search(s,mid+1,high);
}
int get_logest_ladder(int u)
{
int maxim=0;
if(dp[u]!=-1)
return dp[u];
for(int i=0;i<adj[u].size();i++)
{
int v=adj[u][i];
dp[v]=get_logest_ladder(v);
int k=1+dp[v];
if(k>maxim)
maxim=k;
}
dp[u]=maxim;
return dp[u];
}
int main(int argc, char const *argv[])
{
string s;
while(cin>>s)
{
v.push_back(s);
}
for(int i=0;i<v.size();i++)
{
string s1=v[i];
for(int j=0;j<s1.length();j++)
{
for(char ch='a';ch<='z';ch++)
{
string s2=s1;
s2.at(j)=ch;
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
for(int j=0;j<=s1.length();j++)
{
for(char ch='a';ch<='z';ch++)
{
string s2=s1;
s2.insert(s2.begin()+j,ch);
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
for(int j=0;j<s1.length();j++)
{
string s2=s1;
s2.erase(s2.begin()+j);
int ver=bin_search(s2,i+1,v.size()-1);
if(ver!=0)
{
cout<<v[i]<<" "<<v[ver]<<"\n";
adj[i].push_back(ver);
}
}
}
memset(dp,-1,sizeof(dp));
int maxim=0;
for(int i=0;i<v.size();i++)
{
int k=get_logest_ladder(i);
if(k>maxim)
maxim=k;
}
cout<<maxim+1<<"\n";
return 0;
}
Last edited by brianfry713 on Wed Apr 08, 2015 11:39 pm, edited 1 time in total.
Reason: Added code block
Reason: Added code block