Test case for which this solution for SEATSR fails.

I have tried my solution against brute force for about a 1000 test case and yet couldn’t find an error. Could somebody please specify a test case for which the following solution to SEATSR fails. The code is in c++11.

//#include GRAPH
//#define DEBUG       //comment when you have to disable all debug macros.
//#define LOCAL     //uncomment for testing from local file
#define NDEBUG    //comment when all assert statements have to be disabled.
#include <iostream>
#include <cstring>
#include <sstream>
#include <fstream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <climits>
#include <ctime>
#include <algorithm>
#include <functional>
#include <stack>
#include <queue>
#include <list>
#include <deque>
#include <sys/time.h>
#include <iomanip>
#include <cstdarg>
#include <utility> //std::pair
#include <cassert>
#define fd(i,a) for(i=1;i<=a;i++)
#define fa(i,a,b) for(i=a;i<=b;i++)
#define fs(i,a,b,c) for(i=a;i<=b;i+=c)
#define tr(c,i) for(typeof(c.begin()) i = (c).begin(); i != (c).end(); i++) 
#define present(c,x) ((c).find(x) != (c).end()) 
#define all(x) x.begin(), x.end()
#define pb push_back
#define log2(x) (log(x)/log(2))
#define ARRAY_SIZE(arr) (1[&arr]-arr)      
#define lld long long int
#define MOD 1000000007
#define INF 1000000000
#define gcd __gcd
#define equals(a,b) (a.compareTo(b)==0)    //for strings only
using namespace std;

#ifdef DEBUG
#define debug(args...)            {dbg,args; cerr<<endl;}
#else
#define debug(args...)              // Just strip off all debug tokens
#endif

#ifdef GRAPH
#include "drawGraph.cpp"
#endif

struct debugger
{
    template<typename T> debugger& operator , (const T& v)
    {    
        cerr<<v<<" ";    
        return *this;    
    }

}dbg;

template<class T>
inline void inputInt(T &n )
{
	n=0;

 	T ch=getchar_unlocked();
	/*int sign=1;
  	while(( ch < '0' || ch > '9') && ch!='-')
      ch=getchar_unlocked();
	if(ch=='-')
	{
		sign=-1;
		ch=getchar_unlocked();
	}
   	while(  ch >= '0' && ch <= '9' )
       n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
		 n*=sign;*/
	while( ch < '0' || ch > '9')
      ch=getchar_unlocked();
	while(  ch >= '0' && ch <= '9' )
		n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
}

// inline void inputString(string &s)
// {
// 	char ch=getchar_unlocked();
// 	while(ch<'a' || ch >'z')ch=getchar_unlocked();
// 	s="";
// 	while(ch>='a' && ch<='z')
// 		s+=ch, ch=getchar_unlocked();
// }

inline void inputString(string &s)
{
    char ch=getchar_unlocked();
    s="";
    while(ch!='\n')
        s+=ch, ch=getchar_unlocked();
}


typedef struct{
	int operator()(const pair<int,int> &k) const{
		return (k.first*100000+k.second)%MOD;
	}
}myHash;



string s1,s2;
lld len1, len2,a,b,k;
typedef unordered_map<pair<lld,lld>, lld, myHash> MyMap;
MyMap mp, cost_map;
lld arrX[20100001];
lld arrY[20100001];

inline lld actualK(){
	return k/a+1;
}



inline void mapInsert(MyMap &m, pair<lld,lld> p, lld value){
	m.insert(make_pair(p,value));
}

inline lld numbering(){
	lld ma,mi,i,j,index=1, t= actualK();
	for(i=1;i<=len1;i++){
		ma = max((lld)1,i-t);
		mi = min(i+t,len2);
		for(j=ma;j<=mi;j++){
			arrX[index] = i;
			arrY[index] = j;
			mapInsert(mp,make_pair(i,j),index);
			index++;
		}
	}
	return index;
}

inline void init(){
	mp.clear();
	cost_map.clear();
	lld i, t = actualK();
	for(i=0;i<=t;i++)mapInsert(cost_map, make_pair(i,0), i*a);
	for(i=0;i<=t;i++)mapInsert(cost_map, make_pair(0,i), i*a);
}

inline lld cost(lld x, lld y){
	pair<lld, lld> p = make_pair(x,y);
	lld val;
	if(cost_map.find(p)!=cost_map.end())val = cost_map[p];   //present
	else if(a) val = (lld)INF;	
	else val = 0;
	return val;
}

inline pair<lld,lld> calculate_cost(lld index){
	lld i,x,y,l_cost,u_cost,m_cost;
	pair<lld,lld> ins,pop;
	for(i=1;i<index;i++){

		x = arrX[i]; y = arrY[i];
		l_cost = cost(x,y-1)+a;
		u_cost = cost(x-1,y)+a;
		m_cost = cost(x-1,y-1)+b*(s1[x-1]!=s2[y-1]);
		mapInsert(cost_map, make_pair(x,y), min(l_cost, min(u_cost, m_cost)));
		//debug(x,y,l_cost,u_cost,m_cost,cost_map[make_pair(x,y)], s1[x-1], s2[y-1]);
	}
	return make_pair(arrX[index-1],arrY[index-1]);
}

lld solve(){
	lld index,total_cost;
	init();
	index = numbering();
	pair<lld,lld> ans = calculate_cost(index);
	lld x = ans.first, y = ans.second;
	total_cost = cost(x,y)+a*(len2-y);
	//debug("sssss",x,y,total_cost,len2,k,cost(x,y),a);
	if(total_cost<=k)return total_cost;
	else return -1;
}

int main()
{
#ifdef LOCAL
    freopen("input.in","r",stdin);
#endif
	 //std::ios_base::sync_with_stdio (false);
	 lld t;
	 inputInt(t);
	 
	 while(t--){
		 inputString(s1);
		 inputString(s2);
		 //cin>>s1>>s2;
		 inputInt(a);
		 inputInt(b);
		 inputInt(k);
		 len1 = s1.length();
		 len2 = s2.length();
		 if(len2<len1)
		 {
			 swap(len1,len2);
			 swap(s1,s2);
		 }
		 if(a==0){
			 printf("0\n");
			 continue;
		 }
		 if(k==0 || (len2-len1)*a>k){
			 printf("-1\n");
			 continue;
		 }
		 printf("%lld\n",solve());
	 }
}

EDIT: What I tried was calculating a strip of length 2k+1 along the diagonal. I’m maintaining the ordered map to store values for (x,y) which lie within my area of interest i.e. the strip of length 2k+1. DP relation used is the simple O(n^2) solution of minimum edit distance with deletion/insertion cost=a and substitution cost=b. In this case, I’m looking at strip of length 2*(k/a+1)+1.
How do I get this strip? Consider the 2-d matrix for computing minimum edit distance, assume a=1.
consider dp(i,i). I could say that the minimum value of dp(i,i+k+1) and dp(i,i-k-1) is k+1. Since I’m interested in minimum edit distance values of less or equal to k, I can very well ignore considering values which lie left of dp(i,i-k-1) and right of dp(i,i+k+1). This means that I need to consider only strip of length 2k+1 along the diagonal.

Check this link:
http://ideone.com/eID7md

The code is in c++11.

It would be nice if you at least somehow describe your solution…

1 Like

Please look at the edit.