Moderator: Board moderators

andysoft
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

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

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)

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

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;
``````
This is how I get index of word in the dictionary by word itself

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;
``````
Here is my entire code, but I don't think it is useful now.

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

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

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

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.

Code: Select all

``function getInd (const s: str16): longint;``
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:

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;
}
...
``````
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++.

andysoft
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++?
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

andysoft wrote:HDIV is your hash map size, right?
Yes
by the way, should I use STL string or just character arrays if I decide to write in C++?
Character arrays are faster.

andysoft
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.
Now I lay me down to sleep...
my profile

Angeh
Experienced poster
Posts: 108
Joined: Sat Aug 08, 2009 2:53 pm

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
>>>>>>>>> A2
Beliefs are not facts, believe what you need to believe;)

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 10029 - Edit Step Ladders

never mind found it.

DD
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?
If so, you need to read Elements of Programming Interviews.

prashantharshi
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

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;

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 maxim=0;
if(dp[u]!=-1)
return dp[u];
{
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";
}
}
}
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";
}
}
}
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";
}
}
}
memset(dp,-1,sizeof(dp));
int maxim=0;
for(int i=0;i<v.size();i++)
{