164 - String Computer

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

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:

Post by Maxim »

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:

Post by yiuyuho »

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:

Post by Maxim »

Yes, I do. I'm not total newbie to DP as I seem to be. :-?

Still puzzled about outputting...

Maxim

yiuyuho
A great helper
Posts: 325
Joined: Thu Feb 21, 2002 2:00 am
Location: United States
Contact:

Post by yiuyuho »

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:

Post by yiuyuho »

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

Post by Observer »

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:

Post by Dominik Michniewski »

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:

Post by anupam »

the book of clrs may help you...
"Everything should be made simple, but not always simpler"

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer »

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"... :P
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:

Post by anupam »

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:

Post by Dominik Michniewski »

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

Post by Observer »

I don't understand...

I got ACC for problem 526, but not this one!!!! Why? Aren't them identical???? Plz help!!! :cry: :cry:
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

Post by Observer »

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

Post by youquan »

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

Post Reply

Return to “Volume 1 (100-199)”