10029 - Edit Step Ladders

[andysoft]

and how should an efficient hashing function look like? I have idea only about one which takes many gigabytes of memory...

[mf]

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]

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;

I followed your advice on chaining, I implement it using linked list (in one direction).
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
        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.

[mf]

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]

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

[mf]

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]

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.

[Angeh]

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

[tryit1]

never mind found it.

[DD]

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.

[prashantharshi]

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