HackerEarth - Let's Begin- Dynamic Programming

Let's Begin- HackerEarth- Dynamic Programming- Easy

Solution:- 

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000010
int arr[MAX];

void cal()
{
    for(int i=0;i<MAX;i++)
        arr[i]=INT_MAX;
    arr[2]=arr[3]=arr[5]=arr[7]=1;
    int a;

    for(int i=4;i<=MAX;i++)
    {
        a=9999999;
        if(arr[i-2])
            a=arr[i-2];
        if(arr[i-3])
            a=min(a,arr[i-3]);
        if(i-5>=0 && arr[i-5])
            a=min(a,arr[i-5]);
        if(i-7>=0 && arr[i-7])
            a=min(a,arr[i-7]);

        arr[i]=min(1+a,arr[i]);
    }
}

int main()
{
    cal();
    int tc;
    cin>>tc;
    while(tc--)
    {
        int N;
        cin>>N;
        if(arr[N]<INT_MAX)
            cout<<arr[N];
        else
            cout<<"-1";
        cout<<endl;
    }
    return 0;

}

HackerEarth- Intelligent Girl- Dynamic Programming

Intelligent Girl- HackerEarth- Dynamic Programming- Easy

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 10010
int arr[MAX];

int main()
{
    string s;
    cin>>s;
    int len=s.length();
    if((s[len-1]-'0')%2==0)
        arr[len-1]=1;
    else
        arr[len]=0;
    for(int i=len-2;i>=0;i--)
    {
        if((s[i]-'0')%2==0)
            arr[i]=arr[i+1]+1;
        else
            arr[i]=arr[i+1];
    }

    for(int i=0;i<len;i++)
        cout<<arr[i]<<" ";
    return 0;


}

HackerEarth - Tower of Hanoi - Dynamic Programming

Tower of Hanoi- HackerEarth- Dynamic Programming- Easy

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<b;i++)
long long arr[220];

vector<pair<long ,long> > tower;

bool my_comp(pair<long ,long> a,pair<long ,long> b)
{
    return a.second>b.second;
}

int main()
{
    int tc;
    long long a,b,temp;
    cin>>tc;
    while(tc--)
    {
        int N;
        cin>>N;
        f(i,0,N)
        {
            cin>>a>>b;
            tower.push_back(make_pair(a,b));
        }
        sort(tower.begin(),tower.end(),my_comp);
        arr[0]=tower[0].second;
        long long g_max=arr[0];
        f(i,1,N)
        {
            long long max_val=-1;
            f(j,0,i)
            {
                if(tower[i].first<tower[j].first && tower[i].second<tower[j].second)
                    temp=tower[i].second+arr[j];
                else
                    temp=tower[i].second;
                if(temp>max_val)
                    max_val=temp;
            }
            arr[i]=max_val;
            if(arr[i]>g_max)
                g_max=arr[i];
        }
        g_max=g_max>0?g_max:0;
        cout<<g_max<<endl;
        tower.clear();
    }
    return 0;

}

HackerEarth - Studious Little Jhool - Dynamic Programming

Studious Little Jhool - HackerEarth- Dynamic Programming -Easy

Solution:-

#include<bits/stdc++.h>
using namespace std;
int arr[200],i;
void init()
{
    for(int i=0;i<200;i++)
        arr[i]=0;
}

int main()
{
    int tc;
    cin>>tc;
    while(tc--)
    {
        int n,a,b;
        cin>>n;
        init();
        arr[10]=1;
        arr[12]=1;
        for(i=13;i<=n;i++)
        {
            a=999;
            b=999;
            if(arr[i-10] || arr[i-12])
            {if(arr[i-10])
                a=arr[i-10];
            if(arr[i-12])
                b=arr[i-12];
            arr[i]=1+min(a,b);}
        }
        if(arr[n])
            cout<<arr[n];
        else
            cout<<"-1";
        cout<<endl;
    }
    return 0;
}

HackerEarth - Xsquare And Balanced Strings - (Dynamic Programming)

Xsquare And Balanced Strings (HackerEarth) (Dynamic Programming, Easy)

Solution:-

#include<bits/stdc++.h>
using namespace std;

int T,N;
string str ;
int main()
{
cin >> T ;
while(T--)
    {
cin >> str ;
N = str.length() ;
int ans = 0 ;
for(int i=0;i<N;i++)
ans = ans ^ (str[i]-'a') ;

puts(ans == 0 ? "1" : "-1") ;
    }
return 0 ;

}

HackerEarth - Choosing the Judges - (Dynamic Programming)

Choosing the Judges (HackerEarth)(Dynamic Programming)

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX_LEN 10010
#define ll long long
ll arr[MAX_LEN],dp[MAX_LEN];
ll g_max,N;

ll cal_max()
{
    dp[0]=arr[0];
    dp[1]=max(dp[0],arr[1]);

    g_max=dp[1];

    for(int i=2;i<N;i++)
    {
        dp[i]=max(dp[i-2]+arr[i],dp[i-1]);
        if(dp[i]>g_max)
            g_max=dp[i];
    }

    return g_max;
}


int main()
{
    int tc;
    cin>>tc;
    for(int j=1;j<=tc;j++)
    {
        cin>>N;
        g_max=0;
        for(int i=0;i<N;i++)
            cin>>arr[i];

        cout<<"Case "<<j<<": "<<cal_max()<<endl;
    }
    return 0;

} 

HackerEarth - Roy And Ropes - Dynamic Programming problem Solution

Roy And Ropes  (HackerEarth)

Dynamic Programming,Easy

Solution:-

#include<bits/stdc++.h>
using namespace std;;
#define MAX 1000010
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;i++)

int arr[MAX],upper[MAX],lower[MAX];

int max_val(int a,int b,int c)
{
    if(a>=b && a>=c)
        return a;
    if(b>=a && b>=c)
        return b;
    return c;
}

int main()
{
    int tc;
    int l;
    cin>>tc;
    int maxu,maxl;
    while(tc--)
    {
        maxu=maxl=INT_MIN;
        cin>>l;
        f(i,1,l-1)
        {
            cin>>upper[i];
            if(upper[i]+i>maxu)
                maxu=upper[i]+i;
        }

        f(i,1,l-1)
        {
            cin>>lower[i];
            if(lower[i]+i>maxl)
                maxl=lower[i]+i;
        }
        cout<<max_val(maxu,maxl,l)<<endl;
    }
    return 0;

}

HackerEarth- Once Upon A Time in Time-Land (Dynamic Problem Solution)

Once Upon A Time in Time-Land (HackerEarth)

Dynamic Programming, Easy,Algorithms :

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(int i=a;i<=b;i++)
#define MAX 10010
#define ll long long
ll arr[MAX];

int main()
{
    int tc;
    int N,K,i,j;
    cin>>tc;
    while(tc--)
    {
        ll max_val=INT_MIN;
        ll Answer=INT_MIN;
        cin>>N>>K;
        f(i,1,N)
        {
            cin>>arr[i];
            if(arr[i]>Answer)
                Answer=arr[i];
        }
        max_val=arr[1];
        j=2;

        f(i,K+2,N)
        {
            if(max_val>0)
            {
                arr[i]+=max_val;
                if(arr[i]>Answer)
                    Answer=arr[i];
            }
            if(arr[j]>max_val)
                max_val=arr[j];
            j++;
        }
        if(Answer<0)
        Answer=0;
        cout<<Answer<<endl;
    }
    return 0;

}

HackerEarth- Xsquare And Chocolates Bars (Dynamic Problem Solution)

XSquare And Chocolate Bars (HackerEarth)

Dynamic Programming, Easy

Solution:-

#include<bits/stdc++.h>

using namespace std;

#define MAX_LEN 1000010

int arr[MAX_LEN];

string B;

char temp;

void init(int len)

{

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

        arr[i]=0;

}

int cal_max(string B,int len)

{

    init(len);

    if(len<3)

        return len;

    int g_max=0;

    bool flag=B[0]==B[1];

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

    {

        if(!(B[i]==B[i-1] && flag))

            arr[i]=3+(i-3>=0?arr[i-3]:0);

        flag=B[i]==B[i-1];

        if(g_max<arr[i])

            g_max=arr[i];

    }

    return len-g_max;

}

int main()

{

    int tc,i,len,ans,j;

    cin>>tc;

    while(tc--)

    {

        cin>>B;

        len=B.length();

        cout<<cal_max(B,len)<<endl;

    }

    return 0;

}

HackerEarth- Xsquare And Two Arrays (Dynamic Problem Solution)

Xsquare And Two Arrays (HackerEarth)

Dynamic Programming, Easy;

Solution:-

#include<iostream>

using namespace std;

#define MAX 1000010

#define ll long long

#define f(i,a,b) for(int i=a;i<=b;i++)

#define fd(i,a,b) for(int i=a;i<=b;i+=2)

ll arrA[MAX],arrB[MAX];

ll cal_sum(int start,int left,int right)

{

    if(start==1)

    {

        if(left%2)

            return arrA[right]-arrA[left-1];

        else

            return arrB[right]-arrB[left-1];

    }

    else

    {

        if(left%2==0)

            return arrA[right]-arrA[left-1];

        else

            return arrB[right]-arrB[left-1];

    }

}

int main()

{

    int N,Q;

    cin>>N>>Q;

    int i,j;

    arrA[0]=arrB[0]=0;

    f(i,1,N)

        cin>>arrA[i];

    f(i,1,N)

        cin>>arrB[i];

    fd(i,2,N)

        swap(arrA[i],arrB[i]);

    f(i,2,N)

    {

        arrA[i]+=arrA[i-1];

        arrB[i]+=arrB[i-1];

    }

    int start,left,right;

    f(i,0,Q-1)

    {

        cin>>start>>left>>right;

        cout<<cal_sum(start,left,right)<<endl;

    }

    return 0;

}