SPOJ - A very Easy Problem

SPOJ - A very Easy Problem 

Solution:-

/* You guys can use recursion/bits manipulation to come up with some other pattern. All are acceptable till they give the same number. */

137=2(2(2)+2+2(0))+2(2+2(0))+2(0)
1315=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)
73=2(2(2)+2)+2(2+2(0))+2(0)
136=2(2(2)+2+2(0))+2(2+2(0))
255=2(2(2)+2+2(0))+2(2(2)+2)+2(2(2)+2(0))+2(2(2))+2(2+2(0))+2(2)+2+2(0)
1384=2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2)+2(2(2)+2(0))+2(2+2(0))
16385=2(2(2+2(0))+2(2)+2)+2(0)

SPOJ - Happy Numbers Problem Solution

SPOJ - Happy Numbers Problem Solution

Solution:-

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

ll cal_num(ll num)
{
    int val;
    ll sum=0;
    while(num)
    {
        val=num%10;
        sum+=val*val;
        num/=10;
    }
    return sum;
}

int main()
{
    ll num;
    cin>>num;
    int count=0;
    while(1)
    {
        if(num==1)
        {
            cout<<count;
            break;
        }
        else if(num<10 && num!=7)
        {
            cout<<"-1";
            break;
        }
        num=cal_num(num);
        count++;
    }
    return 0;

}

SPOJ - Max Lines Problem Solution

SPOJ - Max Lines Problem Solution

Solution:-

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

int main()
{
    cout<<fixed;
    cout<<setprecision(2);
    int tc;
    cin>>tc;
    for(int i=1;i<=tc;i++)
    {
        double r,max_line;
        cin>>r;
        max_line=(double)(4*r*r)+0.25;
        cout<<"Case "<<i<<": "<<max_line<<endl;
    }
    return 0;

}

SPOJ - Onotole needs your help Using XOR

SPOJ - Onotole needs your help Using XOR

Solution:-

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

int main()
{
    int N,num,one_num=0;
    scanf("%d",&N);
    for(int i=0;i<N;i++)
    {
        scanf("%d",&num);
        one_num^=num;
    }
    printf("%d",one_num);
    return 0;

}

//Just a Lillte Piece of Advice, use scanf and printf instead of cin and cout as they will work fast in this scenario. (To get AC :P)

Or

if you are c++ crazy, you can turn off the sync with stdio, to make cin & cout runs faster (equal or even faster than scanf,printf)

to do that,use

std::ios::sync_with_stdio(false);

SPOJ - Bishops Problem In C++

SPOJ - Bishops Problem In C++

Solution:-

// cumbersome task to implement in C/C++, but nice feeling after AC.

Logic:-

if(grid_size==1)

    Answer=1;

else 

    Answer=(size of grid*2) -2;

#include<bits/stdc++.h>
using namespace std;
int arr[200];
int i,len,carry,num,pos;

int main()
{
    string s;
    while(getline(cin,s))
    {
        len=i=carry=num=pos=0;
        memset(arr,0,sizeof(arr));
        len=s.length();
        pos=0;
        for(i=len-1;i>=0;i--,pos++)     //copy the string to integre array in reverse order
            arr[pos]=s[i]-'0';

        carry=0;
        for(i=0;i<len;i++)                   // double the integer array
        {
            num=(arr[i]*2) + carry;
            arr[i]=num%10;
            carry=num/10;
        }
        while(carry)
        {
            arr[i]=carry%10;
            carry/=10;
            if(carry)
                i++;
        }
        pos=i;                   // subtract 2 from the array
        i=0;
        if(arr[i]>=2)
            arr[i]-=2;
        else
        {
            arr[i]+=8;
            i++;
            arr[i]--;
        }

        while(1)
        {
            if(arr[i]>=0 || i==pos)
                break;
            else
            {
                arr[i]=9;
                i++;
                arr[i]--;
            }
        }
        while(arr[pos]==0)
            pos--;
        if(pos<0)  // if the grid size was 1, than pos becomes less than zero
            cout<<1;
        for(i=pos;i>=0;i--)
            cout<<arr[i];
        cout<<endl;
    }
    return 0;

}

SPOJ - He is Offside Problem Solution without sorting

SPOJ - He is Offside Problem Solution without sorting

Solution:-

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

int attacker,defender,goalie;

int main()
{
    int a,d;
    while(1)
    {
        attacker=defender=goalie=INT_MAX;
        cin>>a>>d;
        if(a==0 && d==0)
            break;
        int temp;
        for(int i=0;i<a;i++)
        {
            cin>>temp;
            if(temp<attacker)
                attacker=temp;
        }

        for(int i=0;i<d;i++)
        {
            cin>>temp;
            if(temp<goalie)
            {
                defender=goalie;
                goalie=temp;
            }
            else if(temp<defender)
                defender=temp;
        }

        if(defender>attacker)
            cout<<"Y\n";
        else
            cout<<"N\n";
    }
    return 0;

}

SPOJ - Philosophers Stone solution using DP

SPOJ - Philosophers Stone solution using DP

Solution:-

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

int arr[MAX][MAX];

int max_val(int a,int b,int c)
{
    int p=INT_MIN;
    p=p>a?p:a;
    p=p>b?p:b;
    p=p>c?p:c;

    return p;
}

int main()
{
    int tc;
    int a,b;
    cin>>tc;
    while(tc--)
    {
        int h,w;
        cin>>h>>w;
        int max_stones=0;

        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
            {
                cin>>arr[i][j];
                if(i>0)
                {
                    a=b=INT_MIN;
                    if(j>0)
                        a=arr[i-1][j-1];
                    if(j<w-1)
                        b=arr[i-1][j+1];
                    arr[i][j]+=max_val(arr[i-1][j],a,b);
                }
                max_stones=max_stones>arr[i][j]?max_stones:arr[i][j];
            }

        cout<<max_stones<<endl;
    }
    return 0;

}

SPOJ - Aggressive Cows (AGGRCOW) Problems Solution

SPOJ -  Aggressive Cows (AGGRCOW) Problems Solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 100010
#define ll long long

ll arr[MAX];
int tc,N,C;

bool func(int mid)
{
    int cows=1,pos=arr[0];

    for(int i=1;i<N;i++)
    {
        if(arr[i]-pos>=mid)
        {
            pos=arr[i];
            cows++;
            if(cows==C)
                return 1;
        }
    }
    return 0;
}

int cal_dist()
{
    int lo,hi,mid,max_dist=-1;
    lo=0;
    hi=arr[N-1];

    while(lo<hi)
    {
        mid=lo+(hi-lo)/2;

        if(func(mid)==1)
        {
            if(mid>max_dist)
                max_dist=mid;
            lo=mid+1;
        }
        else
            hi=mid;
    }
    return max_dist;
}

int main()
{
    cin>>tc;
    while(tc--)
    {
        cin>>N>>C;
        for(int i=0;i<N;i++)
            cin>>arr[i];

        sort(arr,arr+N);

        cout<<cal_dist()<<endl;
    }
    return 0;

}

SPOJ - Longest Path in a Tree Solution

SPOJ - Longest Path in a Tree Solution

Solution:-

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

vector<int> V[Edges];

bool vis[Edges];
int dist[Edges];

void dfs(int vert,int d)
{
    vis[vert]=true;
    dist[vert]=d;

    for(int u=0;u<V[vert].size();u++)
        if(!vis[V[vert][u]])
            dfs(V[vert][u],d+1);
}

int main()
{
    int n,a,b,i;
    int start_node,max_dist;
    cin>>n;

    for(i=0;i<Edges;i++)
    {
        V[i].clear();
        vis[i]=false;
    }

    for(i=0;i<n-1;i++)
    {
        cin>>a>>b;
        V[a].push_back(b);
        V[b].push_back(a);
    }
    dist[0]=0;

    dfs(1,0);
    start_node=0;

    for(i=1;i<=n;i++)
        if(dist[i]>dist[start_node])
            start_node=i;

    memset(vis,0,sizeof(vis));

    dfs(start_node,0);
    max_dist=0;
    for(i=1;i<=n;i++)
        max_dist=max_dist>dist[i]?max_dist:dist[i];

    cout<<max_dist;
}

SPOJ - Cards Problem Solution

SPOJ - Cards Problem Solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 1000010
#define MOD 1000007

int dp[MAX];

int main()
{
    for(int i=1;i<=MAX;i++)
        dp[i]=(((((i*2)%MOD)+i-1)%MOD)+dp[i-1])%MOD;

    int tc;
    cin>>tc;
    while(tc--)
    {
        int N;
        cin>>N;
        cout<<dp[N]<<endl;
    }
    return 0;
}

SPOJ - Edit Distance Problem Solution - Famous DP problem

SPOJ - Edit Distance Problem Solution - Famous DP problem

Solution:-

#include<bits/stdc++.h>

using namespace std;

#define MAX 2010

int dp[MAX][MAX];

void init(int len)

{

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

        dp[i][0]=dp[0][i]=i;

}

int min_val(int a,int b,int c)

{

    int p=INT_MAX;

    p=p>a?a:p;

    p=p>b?b:p;

    p=p>c?c:p;

    return p;

}

int main()

{

    int tc;

    int len1,len2;

    cin>>tc;

    while(tc--)

    {

        string a,b;

        cin>>a>>b;

        len1=a.length();

        len2=b.length();

        init(max(len1,len2));

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

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

            {

                if(a[i-1]==b[j-1])

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

                else

                    dp[i][j]=1+min_val(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]);

             }

        cout<<dp[len1][len2]<<endl;

    }

    return 0;

}

SPOJ - A Game with Numbers O(1) solution

SPOJ -  A Game with Numbers O(1) solution

Solution:-

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

int main()
{
    int N;
    cin>>N;
    if(N%10==0)
        cout<<"2";
    else
        cout<<"1"<<endl<<N%10;
    return 0;

}

SPOJ - Is It A Tree Problem Solution Using Union-Find Algorithm

SPOJ - Is It A Tree Problem Solution Using Union-Find Algorithm

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define MAX 20010
#define NODES 10010

int graph[MAX][2],arr[10010];

int find_set(int val)
{
    if(arr[val]==-1)
        return val;
    return find_set(arr[val]);
}

int main()
{
    int N,M,x,y;
    cin>>N>>M;
    for(int i=0;i<M;i++)
        cin>>graph[i][0]>>graph[i][1];

    memset(arr,-1,sizeof(int)*NODES);

    bool flag=true;

    for(int i=0;i<M;i++)
    {
        x=find_set(graph[i][0]);
        y=find_set(graph[i][1]);

        if(x==y)
        {
            flag=false;
            break;
        }
        arr[x]=y;
    }

    if(flag)
        cout<<"YES";
    else
        cout<<"NO";
    return 0;

}

SPOJ - Girls And Boys Problem Solution

SPOJ - Girls And Boys Problem Solution

Solution:-

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

int main()
{
    int g,b;
    while(1)
    {
        cin>>g>>b;
        if(g==-1 && b==-1)
            break;
        else if(g==0 && b==0)
            cout<<g;
        else if(g>b)
            cout<<ceil(double(g)/(b+1));
        else
            cout<<ceil(double(b)/(g+1));

    cout<<endl;
    }

}

SPOJ - Build a Fence Problem Solution

SPOJ - Build a Fence Problem Solution

Solution :-

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

int main()
{
    double area,n;
    while(1)
    {
        cin>>n;
        if(!n)
            break;

        area=(n*n)/(2*PI);
        cout<<fixed<<setprecision(2)<<area<<endl;
    }
    return 0;

}

SPOJ - AP-Complete The Series Easy Problem Solution

SPOJ - AP-Complete The Series Easy Problem Solution

Solution:-

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

int main()
{
    int tc;
    ll third,last_third,sum;
    int n,first,common_diff;
    cin>>tc;
    while(tc--)
    {
        cin>>third>>last_third>>sum;

        n=(2*sum)/(third+last_third);

        common_diff=(last_third-third)/(n-5);

        first=third-(2*common_diff);
        cout<<n<<"\n";
        for(ll i=0;i<n;i++)
            cout<<first+i*common_diff<<" ";
        cout<<"\n";
    }
    return 0;

}

SPOJ - Street Parade Problem Solution (Using Stack)

SPOJ - Street Parade Problem Solution (Using Stack)

Solution:-

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

int arr[1010];
bool flag;

int main()
{
    int n,prev,index;
    while(1)
    {
        stack<int> s;
        cin>>n;
        if(n==0)
            break;

        for(int i=0;i<n;i++)
            cin>>arr[i];

        prev=index=0;
        flag=false;
        while(index<n)
        {
            if(arr[index]==prev+1)
            {
                prev=arr[index];
                index++;
            }
            else if(s.size() && s.top()==prev+1)
            {
                prev=s.top();
                s.pop();
            }
            else
            {
                s.push(arr[index]);
                index++;
            }
        }
        while(s.size() && s.top()==prev+1)
        {
            prev=s.top();
            s.pop();
        }
        if(!s.size())
            flag=true;

        if(flag)
            cout<<"yes\n";
        else
            cout<<"no\n";

    }
    return 0;

}

SPOJ- Counting Triangles Solution

SPOJ - Counting Triangles Problem Solution

Solution:-

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

long long up[MAX],down[MAX];

void init()
{
    up[1]=1;
    up[2]=4;
    down[2]=1;

    for(int i=3;i<=MAX;i++)
    {
        up[i]=2*up[i-1]+i-up[i-2];
        down[i]=up[i-1]-down[i-1];
    }
}

int main()
{
    init();
    int tc,num;;
    cin>>tc;
    while(tc--)
    {
        cin>>num;
        cout<<up[num]+down[num]<<endl;
    }
    return 0;
}

SPOJ- Army Strength Problem Solution

SPOJ- Army Strength Problem Solution #ad-hoc problem

Solution:-

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

int main()
{
    int tc;
    string ex;
    cin>>tc;
    getline(cin,ex);
    while(tc--)
    {
        int NG,NM,num;
        int max_NG=-1,max_NM=-1;

        cin>>NG>>NM;

        for(int i=0;i<NG;i++)
        {
            cin>>num;
            max_NG=max_NG>num?max_NG:num;
        }

        for(int i=0;i<NM;i++)
        {
            cin>>num;
            max_NM=max_NM>num?max_NM:num;
        }

        if(max_NM<=max_NG)
            cout<<"Godzilla\n";
        else
            cout<<"MechaGodzilla\n";
        getline(cin,ex);
    }
    return 0;

}

SPOJ- Ambiguous Permutations Problem Solution

SPOJ- Ambiguous Permutations Problem Solution

Solution:-

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

int arr[MAX];

bool cal_per(int n)
{
    for(int i=1;i<=n;i++)
    {
        if(i!=arr[arr[i]])
            return false;
    }
    return true;
}

int main()
{
    int n;
    while(1)
    {
        cin>>n;
        if(n==0)
            break;

        for(int i=1;i<=n;i++)
            cin>>arr[i];

        if(cal_per(n))
            cout<<"ambiguous\n";
        else
            cout<<"not ambiguous\n";
    }
    return 0;

}

SPOJ - Bytelandian Gold Coins Problem Solution

SPOJ - BYTELANDIAN GOLD COINS (Famous DP Problem) solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 100010
ll arr[MAX+5],i,N;

ll cal_max(int N)
{
    if(N<MAX)
        return arr[N];

    else if(N/2+N/3+N/4<=N)
        return N;
    else
        return cal_max(N/2)+cal_max(N/3)+cal_max(N/4);
}

int main()
{
    arr[0]=0;
    arr[1]=1;
    arr[2]=2;
    arr[3]=3;
    for(i=4;i<=MAX;i++)
        arr[i]=max(i,arr[i/2]+arr[i/3]+arr[i/4]);

    while(scanf("%lld",&N)==1)
    cout<<cal_max(N)<<endl;
    return 0;

}

SPOJ- Will It Ever Stop (WILLITST) Problem Solution

SPOJ- Will It Ever Stop (WILLITST) Problem O(1) Solution

Solution:-

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

int main()
{
    long long int num;
    cin>>num;

    if(num<=1 || !(num&num-1))
        cout<<"TAK";
    else
        cout<<"NIE";

    return 0;

}

SPOJ - Count on Cantor Problem Solution

SPOJ - Count on Cantor (CANTON) Problem Solution

Solution:-

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 5005
#define lim 10000010

ll arr[MAX];

void init()
{
    int i=1;
    while(1)
    {
        arr[i]=i+arr[i-1];
        if(arr[i]>=lim)
            break;
        i++;
    }
}

int main()
{
    init();
    ll tc,num;
    cin>>tc;
    while(tc--)
    {
        cin>>num;
        int i=0;
        while(arr[i]<num)
            i++;

        ll diff=num-arr[i-1];

        cout<<"TERM "<<num<<" IS ";

        if(i%2==0)
            cout<<diff<<"/"<<i+1-diff;
        else
            cout<<i+1-diff<<"/"<<diff;

        cout<<endl;
    }
    return 0;

}

SPOJ - STAMPS Problem Solution

SPOJ - STAMPS Problem Solution

Solution:-

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

int arr[MAX];
int num_stamps,num_friends;

bool wayToSort(int i, int j) { return i > j; }

int main()
{
    int tc,i,j=0;
    cin>>tc;
    while(tc--)
    {
        j++;
        int index;
        cin>>num_stamps>>num_friends;

        for(i=0;i<num_friends;i++)
            cin>>arr[i];

        sort(arr,arr+num_friends,wayToSort);

        long long int sum=0;
        bool flag=false;

        for(i=0;i<num_friends;i++)
        {
            if(sum>=num_stamps)
            {
                flag=true;
                index=i;
                break;
            }
            sum+=arr[i];
        }

        if(sum>=num_stamps)
        {
            flag=true;
            index=i;
        }

        cout<<"Scenario #"<<j<<":\n";

        if(flag)
            cout<<index<<endl<<endl;
        else
            cout<<"impossible"<<endl<<endl;
    }
    return 0;

}

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;

}