ABA12C

Buying Apples!

Link to the question : ABA12C

HINT :

This is a problem of unbounded knapsack. 

We will maintain an array ans[ k+1 ] where the j th index stores the minimum money required to buy  j kg of apples. 

To find the optimal ans[ j ] , we need to decide whether to  select or reject an instance of weight 'i'.

If we reject all the weights then ans[ j ] = price[ j ], and if we select 'i'  then 

ans[ j ] = minimum[ ans[j - i] + price[ i ] ]  for i= 0,1....j-1.

You can look into the source code for a better understanding.

RECOMMENDED QUESTION :

Try your hands on this dp question :  Morena

  

SOLUTION :

   /* ABA12C - Buying Apples */
/* Sushant Gupta */

#include<bits/stdc++.h>
using namespace std;
int main()
{
 int t;
 scanf("%d",&t);
 while(t--)
 {
  int n,k,b;
  scanf("%d%d",&n,&k);
  b =k;
  int p[k +1];
  int i,j;
  for( i=1; i<=k; i++ )
   scanf("%d",&p[i]);
  int ans[k+1];
  for(i=1; i<=k; i++)
  {
   //if(p[i] == -1)
   // ans[i] = INT_MAX;
   //else
    ans[i] = p[i];
  }
  for(i=2; i<=k; i++)
  {
   for(j=1; j<i; j++)
   {
    if(p[i-j] == -1  || ans[j] == -1)
     continue;
    if(ans[i] == -1)
     ans[i] = ans[j] + p[i-j];
    else
    ans[i] = min(ans[i], ans[j] + p[i-j]);

   }

  }
  if(k==0)
   printf("0\n");
  else
  printf("%d\n",ans[k]);

 }
 return 0;
}

MORENA

Morenas Candy Shop ( Easy )

Link to the question : MORENA

HINT :

Think of dp solution. We check if a[i] is > or < or = a[i-1] and store its relative sign in another array, b[i]. Now just count the number of times the sign alternates.

RECOMMENDED QUESTION :

Try solving this dp question .

SOURCE CODE :

#include<stdio.h>

long long int a[1000010];

int b[1000010];

int main()

{

    int n,i;

    scanf("%d",&n);



    b[0] = 0;

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

    {

        scanf("%lld",&a[i]);

        if(i>0)

        {

            if(a[i]>a[i-1])

                b[i] = 1;

            else if(a[i] < a[i-1])

                b[i] = -1;



            else

                b[i] = 0;

        }

    }

    int c=1,sign=0;

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

    {

        if((sign == 0) && (b[i] != 0))

        {

               c++;

               sign = b[i];

        }

        else if((sign ==1) && (b[i]== -1))

        {

            c++;

            sign = b[i];

        }

        else if((sign == -1) && (b[i] == 1))

        {

            c++;

            sign = b[i];

        }

    }

    printf("%d\n",c);

    return 0;

}

BAT3

BATMAN3

Link to the question : BAT3 

HINT :

I would suggest you to try the longest increasing sub sequence problem first. You can also check the algorithm for LIS in geeksforgeeks.org. 

If you have idea of LIS, then the question must be easy for you. In this we need to find the longest decreasing subsequence but with a change that we can jump one big number if we are on the Robin's number (as given in the question). Hence, we just need to add  batman can go to next cliff its smaller than the present or batman is standing on the Robin's peak (then he can go to any peak). 

RECOMMENDED QUESTION :  

Try another dp question .

SOURCE CODE :

/* Batman3 */

/* Sushant Gupta */



#include<stdio.h>



int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,m;

        scanf("%d%d",&n,&m);

        int i,arr[n];

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

            scanf("%d",&arr[i]);

        int lis[n],j;

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

      lis[i] = 1;

         /* Compute optimized LIS values in bottom up manner */

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

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

         if ( (arr[i] < arr[j] || j==m )&& lis[i] < lis[j] + 1)

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

    int max =0;

   /* Pick maximum of all LIS values */

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

      {if ( max < lis[i] )

         max = lis[i];

       // printf("li = %d\n",lis[i]); //check

         }



      printf("%d\n",max);

    }

    return 0;

}

FARIDA

Princess Farida

Link to the question : FARIDA 

HINT :

The question asks us to take the maximum number of gold coins from the monsters such that if m_1, m_2, m_3......m_n are the monsters then  you can take gold coin from monster m_i only if you had not taken from m_(i-1).
This can be solved very easily by dp. Let us take an array b[] such that b[i] stores the maximum number of gold coins you can get from m_1 to m_i monsters. So,
b[i] = max( gold coins taken from ith monster + b[j]) where 0<j<i-1 .

RECOMMENDED QUESTION :

After solving this dp question, you would love solving this question as well.

SOURCE CODE :

/* Princess Farida */

/* Sushant Gupta */



#include<iostream>

using namespace std;

int main()

{

    int t,k=1;

    cin>>t;

    while(t--)

    {

        int n,i,j;

        cin>>n;

        long long int a[n],b[n],max=0;



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

        {

            cin>>a[i];

            b[i]= 0;

        }

        b[0]= a[0];

        b[1]= a[1];

        for(i=2;i<n;i++)

        {

            for(j=0;j<i-1;j++)

            {

                if(b[i]< b[j] + a[i])

                    b[i]= b[j] + a[i];

            }

        }

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

        {

            if(max< b[i])

                max = b[i];

        }

        cout<<"Case "<<k++<<": "<<max<<endl;

    }



    return 0;

}



  

AMZSEQ

AMZ Word

Link to the question : AMZSEQ 

HINT : 

A very good question on dynamic programming. We take an array a[] and assign a[0] = 1. Now, we can make  1 letter words in 3 ways , i.e, use any of the digit. Similarly if you solve for 2 letter words by applying a bit of permutation and combination, you will get it to be 7. Similarly, by using the relation , a[2] = 7 , in 3 letter words, you will find number of ways to be 17. Hence we conlude the conclusion that a[i]= 2* a[i-1] + a[i-2]. 

RECOMMENDED QUESTION :

Try your hands on this simple question.

SOURCE CODE: 

#include <iostream>

using namespace std;

int main()

{

long long int a[25];

int  x;

a[0] = 1;

a[1] = 3;

for(int i = 2; i < 25; i++)

a[i] = 2*a[i-1] + a[i-2];



cin >> x;

cout << a[x] << endl;



return 0;

}