Solving K-Palindrome problem using Edit distance algorithm

A k-palindrome is a string which transforms into a palindrome on removing at most k characters.

Given a string S, and an interger K, print “YES” if S is a k-palindrome; otherwise print “NO”.
Constraints:
S has at most 20,000 characters.
0<=k<=30

Sample Test Case#1:
Input – abxa 1
Output – YES
Sample Test Case#2:
Input – abdxa 1
Output – No

Solution:

This can be solved using Edit distance dynamic programming algorithm. Edit distance DP algorithm can be used to find the minimum operations required to convert a source string  to destination string. The operations can be either addition or deletion of characters.

The K-palindrome problem can be solved using Edit distance algorithm by checking if the minimum operation required to convert the input string to its reverse.

Let editDistance(source,destination) be the function which takes source string and destination string and returns the minimum operations required to convert the source string to destination string.

A string S is K-palindrome if editDistance(S,reverse(S))<=2*K

This is because we can transform the given string S into its reverse by deleting  K letters and then inserting K letters.

This will be more clear with an example.

Let S=madtam and K=1.

To convert it into reverse of S, i.e matdam first we have to remove the character at index 3 ( 0 based index) in S.

Now the intermediate string is madam . Then we have to insert the character t at index 2 in the intermediate string to get “matdam” which is the reverse of string s.

If you look carefully you will know that the intermediate string “madam” is the palindrome that is obtained by removing k=1 characters.

Codeforces #247 (Div.2) C.K-Tree

Problem link: http://codeforces.com/contest/431/problem/C

Simple recursion with memoization works.

Code is self explanatory

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define mod 1000000007
	typedef long long int ll;
	int k,d,n;
	ll dp[105][2];
	ll solve(int x,int f){
	if(dp[x][f]!=-1){
	return dp[x][f];
	}
	if(x>n)
	dp[x][f]=0;
	else if((x==n)&&f)
	dp[x][f]=1;
	else{
	ll ret=0;
	for(int i=1;i<=k;i++){
	if(x+i<=n){
	ret+=solve(x+i,f||(i>=d)?1:0);
	ret%=mod;
	}
	}
	dp[x][f]=ret;
	}
	return dp[x][f];
	}
	int main(){
	REP(i,105){
	dp[i][0]=-1;
	dp[i][1]=-1;
	}
	scanf("%d%d%d",&n,&k,&d);
	ll ret=0;
	for(int i=1;i<=k;i++){
	ret+=solve(i,(i>=d)?1:0);
	ret%=mod;
	}
	cout<<ret;
	}

view raw k-tree.cpp hosted with ❤ by GitHub

Spoj(SCUBADIV) – Scuba diver

problem link : http://www.spoj.com/problems/SCUBADIV/

This is similar to the classic “knapsack” dynamic programming problem.

Recurrence relation:

dp[n][O][N] = minimum total weight of cylinders required to have O and N capacity of oxygen and nitrogen (capacity of oxygen and nitrogen can exceed) provided n cylinders

dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);

where oxi[i-1] and nitro[i-1] denotes the oxygen and nitrogen capacity of ith cylinder,

w[i-1] denotes the weight of ith cylinder

Terminating conditions:

dp[0][0][0] = 0

dp[0][oxi][nitro]=INFINITY where oxi>0 and nitro>0

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	typedef long long int ll;
	const int MAX = 1024;
	const int INF = 999999999;
	int N, O, n, t, cs;
	int nitro[MAX], oxi[MAX], w[MAX];
	int dp[MAX][22][80], visited[MAX][22][80];
	int solve(int i, int co, int cn)
	{
	if(dp[i][co][cn]!=-1){
	return dp[i][co][cn];
	}
	if(co==0&&cn==0){
	dp[i][co][cn]= 0;
	}
	else if(i==0){//if we considered all cylinders and if co and cn are still not equal to zero
	//then its not possible to satisfy the required condition. Hence return INF in order to eliminate all
	//recursive paths leading to this status
	dp[i][co][cn]= INF;
	}else{
	//either select the ith cylinder or move on to i-1th cylinder
	//Be careful about the index:
	//ith cylinder oxi[i-1] capacity of oxygen and nitro[i-1] capacity of nitrogen
	dp[i][co][cn]=min(solve(i-1,co,cn),solve(i-1,max(co-oxi[i-1],0),max(cn-nitro[i-1],0))+w[i-1]);
	}
	return dp[i][co][cn];
	}
	int main()
	{
	scanf("%d", &t);
	while(t--){
	scanf("%d %d %d", &O, &N, &n);
	for(int i=0;i<n+1;i++)
	for(int j=0;j<O+1;j++)
	for(int k=0;k<N+1;k++)
	dp[i][j][k]=-1;
	for(int i = 0; i < n; i++)
	scanf("%d %d %d", &oxi[i], &nitro[i], &w[i]);
	//dp[n][O][N] gives the minimum total weight of cylinders required to have O and N capacity of oxygen
	//and nitrogen (capacity of oxygen and nitrogen can exceed)
	printf("%d\n", solve(n, O, N));
	}
	return 0;
	}

view raw SCUBADIV.cpp hosted with ❤ by GitHub

Codeforces #260(Div 1) A.Boredom

problem link: http://codeforces.com/problemset/problem/455/A

This problem can be solved using dp approach.

Whenever the contraint on n is around 10^5 you have to think in terms of single dimensional recurrence relation.

Let count[i]=number of times i occured in the input array

dp[i]=maximum points that can be obtained by considering elements upto i

There can be 2 possibilities

case 1: i is selected

If you selecting i, then you have to select all such occurences of i to maximize the points. Also element i-1 cannot be selected because it will be eliminated.

So points scored in this case= i*count[i]+dp[i-2]

case 2: i is not selected

If you are not selecting i, then you have to move over to the next element to score points which is i-1 .

So points scored in this case = dp[i-1]

So thus we get the recurrence relation dp[i]=max(dp[i-1],dp[i-2]+count[i]*i)

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	#include <stdio.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	#define MAX 100005
	typedef long long int ll;
	ll dp[MAX];
	ll count1[MAX];
	int main(){
	int n,x;
	cin>>n;
	REP(i,n){
	cin>>x;
	count1[x]++;
	}
	dp[0]=0;
	dp[1]=count1[1];
	for(int i=2;i<MAX;i++){
	dp[i]=max(dp[i-1],dp[i-2]+i*count1[i]);
	}
	cout<<dp[MAX-1];
	}

view raw Boredom.cpp hosted with ❤ by GitHub

(Hackerrank) Snakes and Ladders: The Quickest Way Up

Found this problem in graph theory section of hackerrank and had so much fun solving it 🙂

             https://www.hackerrank.com/challenges/the-quickest-way-up

Its about finding the least number of rolls of the die in which one can able to reach the destination square (Square Number 100) after having started at the base square (Square Number 1) provided one has the power to get any number (1-6) on the die when one rolls it.

 Solution :

Connect vertex i with i+1,i+2,i+3,i+4,i+5,i+6 ( denoting that from square i you can move to square i+1(when you get 1 when rolling the die),i+2(when you get 2 when rolling the die) and so on)

Similarly consider the starting and ending square of ladder , starting and ending square of the snake as vertices in the graph considered

Apply Floyd warshall algorithm and find minimum distance between square 1 to 100. 

Spoj(MIXTURES) Mixtures – Dynamic Programming

I always love solving Harry Potter theme based problems.This one http://www.spoj.com/problems/MIXTURES/ was  fun solving.

Its based on classic DP problem Matrix Chain multiplication.

Task :

Minimize the  amount of smoke that Harry can get when mixing all the mixtures together.

Solution:

If you look into the problem statement carefully you will know that harry can mix only adjacent  mixtures together. So for example m1,m2,m3 are the mixtures he can either mix m1,m2 first or m2,m3 first.

i.e you can either split the mixture set as {m1} and {m2,m3}

OR

{m1,m2} and {m3}

Let dp[a][b]=minimum smoke produced on mixing mixtures a to b

SO its all about splitting the mixtures into 2 subsets and each of that subsets into 2 sub-subsets and so on such that smoke produced(smoke generated in mixing subsets s1 ans s2 is sum(elements in s1)%100 X sum(elements in s2)%100) is minimized. Aim of the problem  boils down to minimizing the product of the 2 mixtures to be mixed.

Hence our recurrence relation is going to be

dp[a][b]=min(dp[a][k]+dp[k+1][b]+sum(a,k)*sum(k+1,b)) for all k where a<=k<b

Here sum(a,b) defines (sum of all elements from a to b )%100

Base case is dp[i][i]=0

[gist https://gist.github.com/vishnujayvel/9030639]

Spoj(FARIDA) – Princess Farida

This is an interesting and easy DP problem. I solved this in less than 5 minutes.(Trust me ! Its that easy)

Let

dp[i] –> maximum coin sum till i monsters

dp[i]=max(arr[i]+solve(i+2),solve(i+1));

Case 1:

if you choose the ith monster’s coins you cannot choose the next so you
move to the i+2th monster.

Case 2:

if you do not choose the ith monster’s coins you still have a chance to choose i+1th monster’s coins.So you move to i+1th monster

[gist https://gist.github.com/anonymous/8433780]

Spoj(RPLB) Blueberries

Yet another Knapsack based problem

	#include <vector>
	#include <list>
	#include <map>
	#include <set>
	#include <deque>
	#include <queue>
	#include <stack>
	#include <bitset>
	#include <algorithm>
	#include <functional>
	#include <numeric>
	#include <utility>
	#include <sstream>
	#include <iostream>
	#include <iomanip>
	#include <cstdio>
	#include <cmath>
	#include <cstdlib>
	#include <ctime>
	#include <cstring>
	#include <climits>
	#include <stdlib.h>
	using namespace std;
	#define REP(i,n) for(int i=0; i<n; i++)
	#define FOR(i,st,end) for(int i=st;i<end;i++)
	#define db(x) cout << (#x) << " = " << x << endl;
	#define mp make_pair
	#define pb push_back
	int n,W,wt[1001];
	int dp[1001][1001];
	int solve(int i,int w){
	if(i>n)
	return w;
	if (dp[i][w]!=-1)
	return dp[i][w];
	if((wt[i]+w)<=W)
	dp[i][w]=max(solve(i+2,w+wt[i]),solve(i+1,w));
	else
	dp[i][w]=solve(i+1,w);
	return dp[i][w];
	}
	int main(){
	int t;
	scanf("%d",&t);
	FOR(j,1,t+1){
	scanf("%d %d",&n,&W);
	FOR(i,1,n+1){
	scanf("%d",&wt[i]);
	}
	memset(dp,-1,sizeof dp);
	printf("Scenario #%d: %d\n",j,solve(1,0));
	}
	}

view raw RPLB.cpp hosted with ❤ by GitHub

Spoj(EDIST) – Edit Distance -Dynamic Programming

 

http://www.spoj.com/problems/EDIST/

Consider the string SAT .We need to convert it into SAIT

there are 3 possibilities as seen in the picture

So the recursive rule goes like this

dp[i,j]=edit distance for strings of length i and j

dp[i,j]= min(dp[i-1,j-1]+(X[i-1]!=Y[j-1]),dp[i-1,j]+1,dp[i,j-1]+1)

Here X and Y are strings with 0 based index i.e  X[i-1] denotes ith character in X

With the base conditions

dp[0,j]=j //just insertions

dp[j,0]=j //just deletions

	#include<iostream>
	#include<string.h>
	using namespace std;
	char str1[2001];
	char str2[2001];
	int dp[2001][2001];
	int main(){
	int t;
	cin>>t;
	while(t--){
	cin>>str1>>str2;
	int d1,d2,d3,i,j,len1,len2;
	len1=strlen(str1);
	len2=strlen(str2);
	for( i=0;i<=len1;i++)
	dp[i][0]=i;
	for( j=1;j<=len2;j++)
	dp[0][j]=j;
	for( i=1;i<=len1;i++){
	for( j=1;j<=len2;j++){
	d1=((str1[i-1]==str2[j-1])?0:1)+dp[i-1][j-1];//substitution-->if last character same dont do anything(0) else replace last char(1
	d2=dp[i][j-1]+1; // convert (s+ch1) to (t+ch2) by inserting in ch2. so dp (s+ch1,t)+1 +1 for ch2 insertion
	//insertion-->str2 of j-1 length is converted to
	d3=dp[i-1][j]+1;//deletion -->convert (s+ch1) to (t+ch2) by deleting ch1 from s.so dp[s,t+ch2]+1 +1 for ch1 deletion
	//finding minimum of 3
	if(d1<d2&&d1<d3)
	dp[i][j]=d1;
	else{
	if(d2<d3)
	dp[i][j]=d2;
	else
	dp[i][j]=d3;
	}
	}
	}
	cout<< dp[len1][len2];
	cout<<endl;
	}
	}

view raw EDIST.cpp hosted with ❤ by GitHub

Spoj (DSUBSEQ) – Distinct Subsequences

http://www.spoj.com/problems/DSUBSEQ/

Consider the string “ABCD”

Let dp[i] = { number of subsequences possible from string[1…i]}

Note : we are considering 1 based string array

what are all the possible subsequences

dp[0] = 1   { }

dp[1]= 2   { } ,A

dp[2] = 4  { } ,A ,B ,AB

dp[3] = 8  { } ,A ,B ,AB ,C ,AC,BC,ABC

dp[4] = 16 { } ,A ,B ,AB ,C ,AC,BC,ABC,D,AD,BD,ABD,CD,ACD,BCD ,ABCD

So do we get some kind of pattern ?

yes!

dp[i]= dp[i-1]*2

(sum of all subseq till string[1…i-1] + sum of subseq till string[1…i-1] concatenated with character string[i])

There one more case we have to consider

if we have duplicate characters in the string then our subsequence will also be duplicated

To prevent that have a last[ ] array to store position of string[i] which occured before

last[string[i]]= last occurence of string[i]

substract subsequence count occured till position (last[string[i]]-1) since it is repeated again

so the correct recursion rule is

dp[i]=dp[i-1]*2;

if(last[string[i]]>0)

dp[i]=(dp[i]-dp[last[string[i]]-1]);