SEATSR-Editorial

If no more than k differences should be found. In this case it is necessary to calculate only the diagonal band of width 2k+1 in matrix (Ukkonen cut-off), which reduces the time complexity to O (k min (m, n))

I think this figure is best to visualize the idea.

k step right and k step left to the main diagonal will do.

alt text

My Solution which implement this

7 Likes

I seem to have gotten most of the insights mentioned in this editorial, but my solution is still WA.

Any idea why? or possibly provide a test case where my algo would fail, so I can see where I went wrong, and what I’ve missed out?

Thanks

I used this logic, but getting wrong answer. Can somebody plz help me finding where i was wrong?

//m is length(X)+1            
//n is length(Y)+1
//long long int arr[100005][2]
//flag is 0 or 1, initialized by 0

long long int DP()
{
        if(a==0)
           return 0;
    
        diff=m-n;
        if(diff<0)
          diff=(-diff);
    
        if(diff*a>k)
            return -1;
  
        if(b==0)
         {
             if(diff*a <=k)
                return diff*a;
             else
                return -1;
         }
       
        for(i=1;i<m;i++)
	{
		for(j=1;j<n;j++)
		{
                               //calculation for replacement	
				if(i==1 && j==1)
					corner=0;
				else if(i==1)
					corner=(j-1)*a;
				else if(j==1)
					corner=(i-1)*a;
				else
					corner=arr[1-flag][j-1];
    
            			if(X[i-1]!=Y[j-1])
					corner=corner+b;	
				
                                //calculation for addition			
				if(j==1)
					left=i*a;
				else
					left=arr[flag][j-1];
    
				left=left+a;

                               //calculation for deletion
				if(i==1)
					top=j*a;
				else
					top=arr[1-flag][j];
			
				top=top+a;
			
				arr[flag][j]=Minimum(left,top,corner);
			
		}
		flag=1-flag;
	}

			return arr[1-flag][n-1];

}

Why is this problem tagged as Easy-Medium in the editorial tag? I think it should be marked at least as Medium because it requires pre-requisite knowledge of a popular dynamic programming algorithm and then we need to optimize it further.

The reason why I am pointing this out is that several users who start off with competitive programming on Codechef, start solving problems from the Easy subpart in the Practice Section. It can be demotivating for a user if he/she is unable to solve the problem even though it is in the so-called “Easy” Section.

I guess it is very common that even some rather difficult problems are marked as Medium.

Of course, difficulty is relative, it differs from person to person. However, some problems like this one are definitely not Easy.

Do correct me if I am wrong :slight_smile:

21 Likes

Could anyone point out what’s wrong with my solution? I’m getting a TLE. I used Ukkonen’s Algorithm for my approach. I’m using a single array to store the edit distances and a temporary variable to store the value of what would be d[i-1][j-1], if the O(N2) approach with the d[0…m][0…n] matrix is used. I seem to have missed something and I haven’t been able to figure it out yet.

what is delta in edtiorial

I’d like to ask:

How you generated some let say random inputs, but with known result to test your algorithm?

Because of small k I thought, that I can use this:

Both input string should be in form of

...S1...S2...S3...SN...

where S1, S2, … SN are some common substrings and “…” is some mess.

To find longest substring I wanted to use DP, which is unfortunately O(n2) (n is the length of longer string), so I decided I can try to find those in segments of 400 characters (if there is not common string result is -1).

When I did this I simply replaced S1, …, SN with characters that were not in initial strings and run “find longest common subsequence algorithm” also O(n2) algorithm, but now for string with length of ~200 characters…

Expected complexity something like 100400400 + 200*200 per test case, but I didn’t get to TLE, because it worked on my PC, but was failing for some test cases.

I’m trying to solve this problems with above idea, but I get WA, I don’t know what’s wrong with my code?
Here is my code : CodeChef: Practical coding for everyone
Could anyone give me a hint why I’m wrong?
Thank you! ^^

Author’s and Setter’s solutions please

Can anyone explain Restricted Edit Distance in some another manner ?

I’m not able to understand that how we are going to reduce the size of the array d that we are using to store edit distance.

Shouldn’t

P[i][delta] = P[i - 1][delta], if s[i] == w[i + delta] ?

1 Like

nice editorial.

Hey guys, I made a video editorial on this technique here:

https://youtu.be/7GCSA4u5ynw

It’s been a long while, but the algorithm is still great!

Cheers!

1 Like

thanks, corrected.

1 Like

Great to fellow programmers referring to research papers, @kaushik_iiitd and yes (Y) for @sereja :slight_smile:

4 Likes

higher quality PDF of the paper available here @ Algorithms for approximate string matching - ScienceDirect

1 Like

I referenced this diagram (@ http://i.stack.imgur.com/2LtnD.png) instead for my implementation (which turns out to be WA) is there a way to reconcile the two? meaning how should I setup the for-loops to iterate the correct bounds as necessary to compute the final answer?

I edited my ans with link of my solution, see if it helps.

I have to agree. I think the tags are a bit off this time.
ChefSquare = easy, SeaStr = easy-med and Qstring - med (considering O(log n) per query)

1 Like

alright, will take a look at it. thanks