Dynamic Programming (Cutting a Rod)

Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n.Determine the maximum value obtainable by cutting up the rod and selling the pieces. For example, if length of the rod is 8 and the values of different pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

And if the prices are as following, then the maximum obtainable value is 24 (by cutting in eight pieces of length 1)

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 3   5   8   9  10  17  17  20

Solution:-

public class Solution {

public static void main(String [] args)

{

int [] price = new int[]{1, 5, 8, 9, 10, 17, 17, 20};

int n = 8 ;

int [] [] dp = new int [n+1][n+1];

for(int i = 1 ; i <= n ; i++){

for(int j = 1 ; j <= n ; j++){

if(i >= j ){

dp[i][j] = Math.max(dp[i][j-1] , dp[i][i - j] + price[j-1]);

}

else{

dp[i][j] = dp[i-1][j];

}

}

}

System.out.println(dp[n][n]);

}

}

Shop Associations -Code Chef Problem

The shop are categorised as type I. The shop from which he has not brought are categorised as type II. Each shop has initially its own association. One assosciation will merge with another assosciation to form a new assosciation if the shops in both assosciations are of same type (i.e either of type I or type II) and there exists any two shops in the merging assosciations(one in each), distance between whome is 1m.help him to maximise the the sum of the prices by shops of asscosciation of type I by helping him choosing the shops to pick for buying the book. You should provide him the desired sum.

Solution:

#include<stdio.h>

#include<iostream>

using namespace std;

int max(int x, int y)

{ return (y > x)? y : x; }

int maxSubArraySum(int *a, int size)

{

   int max_so_far = a[0], i;

   int curr_max = a[0];

   for (i = 1; i < size; i++)

   {

        curr_max = max(a[i], curr_max+a[i]);

        max_so_far = max(max_so_far, curr_max);

   }

   return max_so_far;

}

int main()

{

   int T = 0;

   cin>>T;

   int *a;

   int n = 0;

   

   int max_sum = 0 ;

   for(int i = 0 ; i < T ; i++)

   {

           cin>>n;

           a = new int[n];

           for(int j = 0 ; j < n ; j++)

           {

                   cin>>a[j];

           }

       max_sum = maxSubArraySum(a, n);

   cout<<max_sum<<endl;

   delete [] a;

   }

  

   return 0;

}

Special Digit - Code Chef Problem

You have a number N and you want to calculate how many divisors of N are special.

A number is said to be special if it is possible to remove some digits from it to get a number having 3, 5 or 6 only.For exemple number 38597 is special since it is posible to remove digits 8, 9, 7 to get 35. You can remove some digits but not all digits. You can remove digits from left, right or middle.

Solution:

#include<iostream> #include<cmath> using namespace std; int check(int n) { if( n < 1 ) { return 0; } if( ((n % 10) == 3) || ((n % 10) == 5) || ((n % 10) == 6) ) { return 1; } else { n = n / 10 ; return (check(n)); } } int main() { int T = 0; long long N = 0; cin>>T; long long temp = 0 ; long long count = 0; for(int i = 0 ; i < T ; i++) { cin>>N; count = 0 ; long long j = 1; for(; j <sqrt(N); j++) { if( (N % j) == 0) { count = count + check(j) + check(N/j); } } if(j*j == N) count = count + check(j); cout<<count<<endl; } return 0; }

SubSet Sum Problem Including Negative Integers

Given a set of integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Solution:-
#include<iostream>
#include<vector>
using namespace std;

int compute(vector<long long>item , int n ,long long sum , long long osum)
{
    if(n < 0 )
    return sum==osum;
    else
    {
        if(sum == osum)
        return 1;
        
    }
    return compute(item , n-1 , sum + item[n] ,osum) || compute(item , n-1 , sum , osum);
    
}
    

int main()
{
    int T = 0 ;
    cin>>T;
    vector<long long>item;
    int ans = 0 ;
    int N = 0 ;
    long long osum;
    for(int t = 0 ; t < T ; t++)
    {
            cin>>N;
            item.clear();
            item.resize(N);
            for(long long i = 0 ; i < N ; i++)
            {
                    cin>>item[i];
            }
            cin>>osum;
            ans = compute(item ,N - 1, 0 , osum );
            if(ans == 1)
            cout<<"YES"<<endl;
            else
            cout<<"NO"<<endl;
    }
    
    return 0;

}

SubSet Sum Problem Using Dynamic Programming

Given a set of non-negative integers, and a value sum, determine if there is a subset of the given set with sum equal to given sum.

Solution:

#include<iostream>

#include<stdio.h>

using namespace std;

bool isSubsetSum(int set[], int n, int sum)

{

   

    bool subset[sum+1][n+1];

 

    // If sum is 0, then answer is true

    for (int i = 0; i <= n; i++)

      subset[0][i] = true;

 

    // If sum is not 0 and set is empty, then answer is false

    for (int i = 1; i <= sum; i++)

      subset[i][0] = false;

 

     

     for (int i = 1; i <= sum; i++)

     {

       for (int j = 1; j <= n; j++)

       {

         subset[i][j] = subset[i][j-1];

         if (i >= set[j-1])

           subset[i][j] = subset[i][j] || subset[i - set[j-1]][j-1];

       }

     }

 

    

 

     return subset[sum][n];

}

 

int main()

{

    int T = 0 ;

    cin>>T;

    int *a;

    int n = 0;

    int sum = 0 ;

    for(int t = 0 ; t < T ; t++)

    {

            cin>>n;

            a = new int[n];

            for(int i = 0 ; i < n ; i++)

            {

                    cin>>a[i];

            }

            

            cin>>sum;

  if (isSubsetSum(a , n , sum ) == true)

     cout<<"YES"<<endl;

  else

     cout<<"NO"<<endl;

     delete []a;

  }

  return 0;

}

ZigZag Sequence Problem Top Coder 03 Semi Finals 3

Level Of the Problem ;-   EASY

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

SOLUTION:

#include<iostream>

#include<vector>

using namespace std;

int main()

{

    int T = 0 ; 

    int N = 0 ;

    cin>>T;

    vector<int>num;

    vector<int> sol;

    vector<int>sign; // USED TO STORE THE SIGN OF LAST TWO ELEMENTS

    for(int t = 0 ; t < T ; t++)

    {

            cin>>N;

            num.clear();

            num.resize(N);

            sol.clear();

            sol.resize(N+1);

            sign.clear();

            sign.resize(N);

            for(int i = 0 ; i < N ; i++)

            {

                    cin>>num[i];

                    sol[i] = 1 ;

                    sign[i] = 0 ;

                    

            }

            sol[N]= 1 ;

            for(int i = 1 ; i < N ; i++)

            {

                    for(int j = 0 ; j < i ; j++)

                    {

                            if( j == 0)

                            {

                                

                                sign[i] = num[i] - num[j]; 

                                sol[i] = sol[j] + 1 ;

                            }

                            else if(  ( (sign[j] > 0) && (num[i] - num[j] < 0))  || ( (sign[j] < 0) && (num[i] - num[j] > 0) ) && ( sol[j] + 1 > sol[i]) )

                            {

                            sol[i] =  sol[j] +  1 ;

                            sign[i] = num[i] - num[j]; 

                                

                            }

                    }

            }  

            cout<<sol[N-1]<<endl;

    }

    cin.get();

    return 0;

}