Spoj Problem AIBOHP-Aibohphobia[Java Solutio] using Dynamic Programming

   Spoj Problem AIBOHP-Aibohphobia[Java Solution] using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/AIBOHP/

Hint:- Find length of LONGEST COMMON SUBSEQUENCE in orignal string and reverse of string and subtract it from length of orignal string.

Longest Common Subsequence Problem easily solved using Dynamic Programming.

Required Value=length of string - LCS(string,reverse of string)

A nice detailed tutorial to find Longest Common Sub-Sequence is

Java Program:-

 /**
 * @(#)AIBOHP.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/11
 */
import java.io.*;
import java.util.*;

class AIBOHP {

    public static void main(String args[])throws IOException{
   
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    long T=Long.parseLong(br.readLine());
   
    while(T--!=0){
    
    StringBuilder str=new StringBuilder(br.readLine());
    String ostr=str.toString();
    System.out.println(ostr.length()-LCS(ostr,str.reverse().toString()));
   
    }
   
    }
    
    public static int LCS(String x,String y){
   
    int dp[][]=new int[x.length()+1][y.length()+1];
   
    for(int i=0;i<=x.length();i++){
    for(int j=0;j<=y.length();j++){
    if(i==0||j==0){
    dp[i][j]=0;
    continue;
    }
   
    if(x.charAt(i-1)==y.charAt(j-1)){
    dp[i][j]=dp[i-1][j-1]+1;
    }else{
    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
    }
   
    }
    }
    return dp[x.length()][y.length()];
    }
      
}

Input:-

1
fft

Output:-

1

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem MIXTURES - Mixtures[Java Solution] using Dynamic Programming

     Spoj Problem MIXTURES - Mixtures[Java Solution]                                           using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/MIXTURES/

Hint:- Matrix Chain Multiplication Algorithm.

Helpful Tutorial for Matrix Chain Multiplication Problem using Dynamic Programming:-

With the help of algorithm of  Matrix Chain Multiplication,this problem can be solved similarly except we have to also store new generated color.Keep in mind that we have to minimize the generated smoke.It is an advice to try yourself to solve the problem after studying the concept of Matrix Chain Multiplication using Dynamic Programming.Here,a solution for this problem written in java is given below:-

Java Program:-

/**
 * @(#)MIXTURES.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/14
 */

import java.io.*;

class MIXTURES {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    String in;
   
    while((in=br.readLine())!=null){
   
    int N=Integer.parseInt(in);
    String str[]=br.readLine().split(" ");
    int ar[]=new int[N];
   
    for(int i=0;i<N;i++){
    ar[i]=Integer.parseInt(str[i]);
    }
   
    System.out.println(MCM(ar));
   
    }
   
    }
 
    static int MCM(int ar[]){
   
    if(ar.length==2){
    return ar[0]*ar[1];
    }
   
    int dp[][]=new int[ar.length][ar.length];
    int color[][]=new int[ar.length][ar.length];
   
    for(int i=0;i<ar.length;i++){
    color[i][i]=ar[i];
    }
   
    int mul=0;
   
    for(int l=2;l<=ar.length;l++){
   
    for(int i=0;i<=ar.length-l;i++){
   
    int j=i+l-1;
    dp[i][j]=Integer.MAX_VALUE;
    for(int k=i;k<j;k++){
    mul=dp[i][k]+dp[k+1][j]+(color[i][k]*color[k+1][j]);
    if(mul<dp[i][j]){
    dp[i][j]=mul;
    color[i][j]=(color[i][k]+color[k+1][j])%100;
    }
    }
   
    }
   
    }
    return dp[0][ar.length-1];
   
    }
 
 
}

Input:-

2
18 19
3
40 60 20

Output:-

342
2400

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem EDIST - Edit Distance[Java Solution]

   Spoj Problem EDIST - Edit Distance[Java Solution]                                           

Problem Statement:-http://www.spoj.com/problems/EDIST/

Hint:- Dynamic Programming.

Java Program:-

/**
 * @(#)EDIST.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/11/2
 */

import java.io.*;


class EDIST {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    int T=Integer.parseInt(br.readLine());
   
    while(T--!=0){
   
    String str1=br.readLine();
    String str2=br.readLine();
   
    System.out.println(solve(str1,str2));
   
    }
   
    }  
 
    public static int solve(String s1,String s2){
    int ar[][]=new int[s1.length()+1][s2.length()+1];
    for(int i=0;i<=s1.length();i++){
    ar[i][0]=i;
    }
   
    for(int i=0;i<=s2.length();i++){
    ar[0][i]=i;
    }
   
    for(int i=1;i<=s1.length();i++){
    for(int j=1;j<=s2.length();j++){
    if(s1.charAt(i-1)==s2.charAt(j-1)){
    ar[i][j]=ar[i-1][j-1];
    }else{
    ar[i][j]=Math.min(ar[i-1][j-1],Math.min(ar[i-1][j],ar[i][j-1]))+1;
    }
    }
    }
   
    return ar[s1.length()][s2.length()];
   
    }
   
}

Input:-

1
FOOD
MONEY 

Output:-

4

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj-PIGBANK Piggy Bank Problem[Java Solution]

   Spoj Problem PIGBANK- PIGGY-BANK[Java Solution]                                          using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/PIGBANK/

With the help of Dynamic Programming concept,this problem can be easily solved.Solution of this problem using Java given below.

Java Program:-

/**
 * @(#)PIGBANK.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/3/21
 */

import java.io.*;
import java.util.*;

class PIGBANK {

public static final int INF=1000000000;


    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(br.readLine());
    while(T--!=0){
    String str[]=br.readLine().split(" ");
    int E=Integer.parseInt(str[0]);
    int F=Integer.parseInt(str[1]);
   
    int N=Integer.parseInt(br.readLine());
   
    int val[]=new int[N];
    int wt[]=new int[N];
   
    int W=(F-E)+1;
    int ar[]=new int[W];
   
    for(int i=0;i<N;i++){
    str=br.readLine().split(" ");
    val[i]=Integer.parseInt(str[0]);
    wt[i]=Integer.parseInt(str[1]);
    Arrays.fill(ar,INF);
   
    }
    ar[0]=0;
   
    for(int i=1;i<=N;i++){
    for(int j=wt[i-1];j<W;j++){
    if(ar[j]>ar[j-wt[i-1]]+val[i-1]){
    ar[j]=ar[j-wt[i-1]]+val[i-1];
    }
    }
    }
   
   
    if(ar[W-1]==INF){
    System.out.println("This is impossible.");
    }else{
    System.out.println("The minimum amount of money in the piggy-bank is "+ar[W-1]+".");
    }
   
   
   
   
   
    }
   
    }
 
 
 
}

Input:-

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Output:-

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------