## 164 - String Computer

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
cannot reconstruct solution? How do you calculate the minimum distance?

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
It is needed two-dimensional integer array, say S. After computation, S[m][n] is minimum distance, where m is length of s1 (first string) and n length of s2 (second string). Here is how I do computation:

val = (s1 == s2[j]) ? 0 : 1;
S[j] = min( S[i-1][j-1] + val, S[i-1][j]+1 , S[j-1]+1 );

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
Levenstein Distance, you understand how and why it works?

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:
Yes, I do. I'm not total newbie to DP as I seem to be.

Maxim

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
ok then,
let f as source str, t as target string,

to back track:
start from s[m][n], m= len(to), n=len(from)
if(s[m][n]==0) then done
else
compare and found where s[m][n] is from:

again set val = (s[m]==s[n]?0:1)
now, if(s[m][n]==s[m-1][n]+1),
this means you can transform from
f(0..n) to t(0..m-1) using s[m-1][n] operations, so you can do that and than insert t[m] to t(0..m-1). of course you can also first insert t[m] to f(0..n) then transform from f(0..n) to t(0..m-1), and t[m] will append at the end anyways. Set m:=m-1 after operation

similarly, if(s[m][n]==s[m][n-1]+1) refers to a delete at f[n] rather than insert at t in the previous case.

and s[m][n]==s[m-1][n-1]+val refers to a change f val = 1 and no operation when val = 0

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:
But, as I said somehow strangely the judge only accept back track in certain order, whiuch I haven't figure why yet.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Can anyone help me on the output part?

We've to output the position of "changed characters", but as the position of characters will be changed whenever Insert/Delete function is called, what shall we do?
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
"Everything should be made simple, but not always simpler"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Dominik Michniewski wrote:you must handle it by hand. If I correct remmber I use something like this:
1. if operation == DELETE do nothing
2. if operation == INSERT do pos++
3. if operation == CHANGE do pos++

Best ragards
DM
Could you explain a bit further plz?? Why DELETE == do nothing?

P.S. I've no trouble finding the "edit distance"...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:
There is a similar problem in the volumes but i can't remember.
plz help
"Everything should be made simple, but not always simpler"

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
When you delete character from input string, position which you must output doesn't change.

Anupam: yes, in volumes exists other problem in this manner - 52x or something like this ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
I don't understand...

I got ACC for problem 526, but not this one!!!! Why? Aren't them identical???? Plz help!!!
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
Finally got ACC. As yiuyuho has mentioned before, the judge only accept back track in certain order.

I used D-C-I and got WA.
Changed to C-D-I and got ACC!!!! Strange...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

youquan
New poster
Posts: 2
Joined: Sun Apr 06, 2003 4:22 pm
I think it has got to do with the limit of the strings being 20... if you track in certain order, some of them would give numbers which are beyond 20... like if you track for insert first, then you delete... then you might insert letters beyond the limit of 20 and then delete whatever you want to delete... which is probably what is causing all the WA...