Wednesday 30 September 2015

Game theory (dp +game theory )


                                                ww.spoj.com/problems/TRT/

         

TRT - Treats for the Cows



In this problem ,we have to maximize the result . at each chance the value becomes
(chance_number*value).we can pick either





#include<bits/stdc++.h>

using namespace std;

int dp[2005][2005];

int a[10000];

int cal(int a[],int st,int en,int cur)
{
 if(st>en)
    return 0;

 if(dp[st][en]!=-1)
    return dp[st][en];

 if(st==en)
 {
     dp[st][en]=a[st]*cur;
     return dp[st][en];
 }

 else
 {

 int ans1=a[st]*cur;
 ans1+=cal(a,st+1,en,cur+1);

 int ans2=a[en]*cur;
 ans2+=cal(a,st,en-1,cur+1);

 dp[st][en]=max(ans1,ans2);
 return max(ans1,ans2);

 }
}



int main()
{
 int n,i,j;
 cin>>n;

  for(i=0;i<2005;i++)
     for(j=0;j<2005;j++)
       dp[i][j]=-1;

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

  int k=cal(a,1,n,1);
  cout<<k<<endl;
return 0;
}

Game theory (Optimal game strategy)


                                                   http://www.spoj.com/problems/TWENDS/

TWENDS - Two Ends



 In this problem 1st player  plays  optimally and second player plays greedly.
 We have to pick either from first end or second end.


#include<bits/stdc++.h>

using namespace std;

long long int  dp[2002][2002];
long long int  a[50000];


long long int send(long long int  a[],long long int  st ,long long int  end)
{
  if(st>end)
   return 0;

    if(dp[st][end]!=-1)
    {
       // dp[st][end]=a[st];
        return dp[st][end];
    }

   if(st==end)
   {
     dp[st][end]=a[st];
     return a[st];
   }

   if(st+1==end)
   {
       dp[st][end]=max(a[st],a[end]);
       return max(a[st],a[end]);
   }

else{
    long long int ans1=a[st];
    if(a[st+1]>=a[end])
    {
        ans1+=send(a,st+2,end);
    }
    else
    {
        ans1+=send(a,st+1,end-1);
    }

    long long int  ans2=a[end];
    if(a[st]>=a[end-1])
    {
        ans2+=send(a,st+1,end-1);
    }
    else
    {
        ans2+=send(a,st,end-2);
    }

   dp[st][end]=max(ans1,ans2);
}


   return dp[st][end];
}







int main()
{
 for(int t=1;;t++)
 {
  for(int i=0;i<2002;i++)
    for(int j=0;j<2002;j++)
     dp[i][j]=-1;

  long long int  n,i,j;
  cin>>n;

  if(n==0) break;


  long long int  tot=0;

  for(i=1;i<=n;i++)
   {
       cin>>a[i];
       tot+=a[i];
   }

  long long int  kk=send(a,1,n);

 // cout<<abs(tot-kk-kk)<<endl;
  cout<<"In game "<<t<<", the greedy strategy might lose by as many as "<<abs(tot-kk-kk)<<" points."<<endl;

   /* for(i=1;i<=n;i++){
    for(j=1;j<=n;j++)
      cout<<dp[i][j]<<" ";
       cout<<endl;*/



 }
return 0;
}

Tuesday 29 September 2015

new idea for add in the range [a,b] ( no segment tree )


                             A. Greg and Array

http://codeforces.com/problemset/problem/295/A



If it is told to add in the range [a,b] with c . we just add array[a]+=c  and array[b+1]-=c;
After that we just need to do cumulative sum. It  will give the final array :)





#include<bits/stdc++.h>

using namespace std;

long long int a[500005],b[500005];
long long int op[500005],k[100005][3];



int main()
{
long long int n,i,j,l,ut,ui,p,q,ad;

cin>>n>>ut>>ui;

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

for(i=1;i<=ut;i++)
{
 cin>>k[i][0]>>k[i][1]>>k[i][2];
}


for(i=1;i<=n+1;i++)
    op[i]=0;

for(i=1;i<=ui;i++)
{
 cin>>p>>q;
 op[p]++;
 op[q+1]--;
}

for(i=2;i<=ut;i++) op[i]+=op[i-1];

/*for(i=1;i<=n;i++)
    cout<<op[i]<<" ";
     cout<<endl;*/



for(i=1;i<=n+1;i++) b[i]=0;

for(i=1;i<=ut;i++)
{
   b[k[i][0]]+=op[i]*k[i][2];
   b[k[i][1]+1]-=(op[i]*k[i][2]);
}


for(i=2;i<=n;i++)
{
 b[i]+=b[i-1];
 //a[i]+=a[i-1];
}

for(i=1;i<=n;i++)
    a[i]+=b[i];

for(i=1;i<=n;i++)
    cout<<a[i]<<" ";
     cout<<endl;

return 0;
}



Cut tree in two halfs (dfs implementation )


Cut the tree (dfs application)


https://www.hackerrank.com/challenges/cut-the-tree

In  this question , we should cut the tree such that the difference between two halfs would be smallest
as possible .

firstly ,total weight is added as sum. after that:-
It is implemented using recursive dfs. Here each child gives his lower weight to their parents.


#include<bits/stdc++.h>

using namespace std;

int sum=0;
int a[10000000],vis[1000000];
int ans=INT_MAX;
vector<int> v[1000000];


int  dfs(int node)
{
  vis[node]=1;

  int curr=a[node];

 for(int i=0;i<v[node].size();i++)
 {
     if(vis[v[node][i]]==0)
     curr+=dfs(v[node][i]);
 }


 ans=min(ans,abs(sum-curr-curr));
 //cout<<curr<<" "<<ans<<endl;

 return curr;

 vis[node]=0;
}






int main()
{
 int n,i,j,k,l,p,q;
 cin>>n;

 for(i=1;i<=n;i++)
 {
  cin>>a[i];
  sum+=a[i];
 }

  for(i=1;i<n;i++)
  {
   cin>>p>>q;
   v[p].push_back(q);
   v[q].push_back(p);
  }

 int kk=dfs(1);
 cout<<ans<<endl;

return 0;
}

Monday 28 September 2015

Counting removing edges to make it forest of even nodes. (dfs applin)



https://www.hackerrank.com/challenges/even-tree

Even Tree (dfs application )

In this question we have to count what is the maximum number of forests (of even nodes)
 that can be made by removal of minimum edges.


Here child returns its parent the no. of nodes ,if the number of nodes(including parent itself ) is even
then ans=ans+1;


#include<bits/stdc++.h>

using namespace std;

int ans=0,visited[100000];

vector<int> v[100000];

int dfs(int nod)
{
    visited[nod]=1;


   int  total=1;                  ///self count

   if(v[nod].size()==1 && nod!=1)
    return 1;                /// the leaf child gives 1 to parent

  for(int i=0;i<v[nod].size();i++)
  {
     if(visited[v[nod][i]]==0)
      total+=dfs(v[nod][i]);
  }

  if(total%2==0)
        ans++;


  visited[nod]=0;

  return total;
}



int main()
{
 int n,e,i,j,k,a,b,l;
 cin>>n>>e;


 for(i=1;i<=e;i++)
 {
  cin>>a>>b;
  v[a].push_back(b);
  v[b].push_back(a);
 }

 int kk=dfs(1);

 cout<<ans-1<<endl;

return 0;
}

MST_( Kruskal algo.) using Union find



Jack goes to Rapture (MST+dfs)


https://www.hackerrank.com/challenges/jack-goes-to-rapture

In this question , we have to say the minimum among ( all the paths's maximum edge cost ).

Firstly, we have to apply Kruskal algorithm to find the Minimum spanning tree. After that we find the maximum cost edge in the path from 1 (source)  to n (destination).





#include<bits/stdc++.h>

using namespace std;

vector<pair<int,int> > mst[100000];

int visited[100000];

int parent[1000000];

int rankk[1000000];

int ans=INT_MIN;



void dfs(int nod,int last,int curr)
{
    visited[nod]=1;

    if(nod==last)
    {
       ans=max(ans,curr);
       return;
    }

  for(int i=0;i<mst[nod].size();i++)
  {
     if(visited[mst[nod][i].first]==0)
      dfs(mst[nod][i].first,last,max(curr,mst[nod][i].second));
  }

  visited[nod]=0;
}





int find(int node)
{
   if(parent[node]==node)
        return node;
   else
      return find(parent[node]);
}



void merge(int node1,int node2)
{
 int x=find(node1);
 int y=find(node2);

 if(rankk[x]>rankk[y])
    parent[y]=x;
 else
 {
     parent[x]=y;
     if(rankk[x]==rankk[y])
        rankk[y]++;
 }
}




int main()
{
 int n,e,i,j,k,l,a,b,c;

 cin>>n>>k;

 vector<pair<int, pair<int,int > > > v;

 for(i=0;i<k;i++)
 {
   cin>>a>>b>>c;
   v.push_back({c,{b,a}});
 }

 sort(v.begin(),v.end());


 for(i=1;i<=n;i++)
 {
    parent[i]=i;
    rankk[i]=0;
 }

 for(i=0;i<k;i++)
 {
   if(find(v[i].second.first)!=find(v[i].second.second))
    {
     merge(v[i].second.first,find(v[i].second.second));
     mst[v[i].second.first].push_back({v[i].second.second,v[i].first});
     mst[v[i].second.second].push_back({v[i].second.first,v[i].first});
    }
 }


/// Mst is ready , now we just have to apply the dfs.

dfs(1,n,0);
if(ans==INT_MIN)
    cout<<"NO PATH EXISTS"<<endl;
else
    cout<<ans<<endl;

return 0;
}

Sunday 27 September 2015

Union Find Appln For finding disconnected group with max no of nodes inside


Problem :- https://www.hackerrank.com/challenges/kundu-and-tree

Edotorial :  https://www.hackerrank.com/challenges/kundu-and-tree/editorial


In this question, Rank will store the Number of nodes under it's Group. So, Obviously ,in the beginning Rank will be one (Represent single member ).




#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int abcd[100010];
int parent[100010];
typedef long long int lli;
#define mod 1000000007
long long int B[100009],C[100009],D[100009];
#define MOD 1000000007


int find(int node)
{
int k;
     if(parent[node]==node)
     {
       return node;
     }
      else
     k=find(parent[node]);
     return k;
}



void  merge(int a, int  b)
{
  int x=find(a);
  int y=find(b);
  if(abcd[x]>abcd[y])
  {

      parent[y]=x;
      abcd[x]+=abcd[y];
      abcd[y]=0;
 
  }
  else
  {
       parent[x]=y;
       abcd[y]+=abcd[x];
       abcd[x]=0;        
  }
}


int main()
{
 int n;
 cin>>n;

 for(int i=0;i<=n+1;i++)
 {
    parent[i]=i;
    abcd[i]=1;
 }

 for(int i=0;i<n-1;i++)
 {
     int  a,b;
char c;
cin>>a>>b>>c;

 if(c=='r') continue;
 else
 {
  if(find(a)!=find(b))
   {
    merge(a,b);
                   }
 }
 }


  vector<lli>count1;
  for(int i=0;i<=n;i++) count1.push_back(0);
  for(int i=1;i<=n;i++)
   {
    if(abcd[i]!=0)
     {
      count1[i]=(abcd[i]);// size of all  sets
      }
   }


**********By the below Method we converted the complexity of O(n^3) to O(n)************

//*/**** jadu way to calculate product of all possible triplets in 4*o(n)*/

   B[n-1] = count1[n];
    int i;
    for(i=n-2;i>=0;i--) B[i] = (B[i+1] + count1[i+1])%MOD;

    for(i=1;i<n-1;i++) C[i] = (count1[i+1]*B[i+1])%MOD;

    D[n-2] = C[n-2];
    for(i=n-3;i>=1;i--) D[i] = (D[i+1] + C[i])%MOD;
lli sum=0;
    for(i=0;i<n-2;i++) sum = (sum + count1[i+1]*D[i+1])%MOD;
    cout<< ( MOD + sum )%MOD<<endl;
    /*** jadu end*/////////////
 return 0;
}

Union_find_application_ (finding minimum cost's component among all disconnected components)


In this question ,firstly there are n disconnected components ,with different costs.
One -by -one, these disconnected componets are getting attached. we have to find the smallest cost
component after each attachment.

 https://www.hackerrank.com/contests/morgan-stanley-2015/challenges/min-con-com



#include<bits/stdc++.h>

using namespace std;

multiset<int> s;
multiset<int>::iterator it;

int cost[500005];
int parent[500005];
int rankk[500005];


int find(int nod)
{
   if(parent[nod]==nod)
        return nod;
   else
     return find(parent[nod]);
}




void merge(int nod1,int nod2)
{
    int p1=find(nod1);
    int p2=find(nod2);

    if(rankk[p1]>rankk[p2])
    {
        parent[p2]=p1;                   ///those rankk is more ,will become parent

        it=s.find(cost[p2]);
        s.erase(it);
        it=s.find(cost[p1]);
        s.erase(it);
        cost[p1]+=cost[p2];
        s.insert(cost[p1]);

         cost[p2]=-1;                      /// '-1' will tell that this is removed
    }
    else
    {
        parent[p1]=p2;
        if(rankk[p1]==rankk[p1])
            rankk[p1]++;

        it=s.find(cost[p2]);
        s.erase(it);
        it=s.find(cost[p1]);
        s.erase(it);             /// cost of p1 and p2 will be erased and new sum cost will be inserted
        cost[p2]+=cost[p1];
        s.insert(cost[p2]);

        cost[p1]=-1;
    }
}





int main()
{
 int n,k,i,j,l,p,q;
 cin>>n>>k;

 for(i=1;i<=n;i++)
 {
    cin>>cost[i];
    s.insert(cost[i]);      /// this set will give minimum available cost at each moment (this will be the answer in this ques.)
 }


 for(i=1;i<=n;i++)
 {
  parent[i]=i;
  rankk[i]=0;
 }

 for(i=1;i<=k;i++)
 {
   cin>>p>>q;

   if(find(p)!=find(q))
    {
      merge(p,q);
    }
 
    it=s.begin();
    cout<<(*it)<<endl;
 }
return 0;
}



Friday 25 September 2015

Subarray_Maximum_sum %M

Related Question:-

https://www.hackerrank.com/contests/101hack21/challenges/maximise-sum



If  an array contains only positive elements and it is told to find maximum sum of array % M, Then this method can be used.

    ( In case of negative elements ,we use Kadane's algo. But, here it is only positive elements).





#include<bits/stdc++.h>

using namespace std;
long long int A[100001];

int main()
{

      int t;
      cin>>t;
      while(t--)
      {

      long long int n,m,i,j,k,l,sum = 0 , ans = 0 ;
      cin>>n>>m;

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

        set<long long int> S ;
        S.insert(0) ;
        set<long long int>::iterator it ;

         for(i=1;i<=n;i++)
         {
            sum += A[i] ;
            sum %= m ;
            it = S.upper_bound(sum) ;
            if(it != S.end())
                ans = max(ans,sum-(*it)+m) ;
            else
                ans = max(ans,sum) ;
            S.insert(sum);
          }
          cout<<ans<<endl;

      }
  return 0;
}

A. Dreamoon and Stairs : minimum steps to reach : recursion solution.



http://codeforces.com/contest/476/problem/A


#include<bits/stdc++.h>

using namespace std;
int dp[10001][5055];

int  fun(int cu,int n,int m,int st)
{

  if(st%m==0 && cu==n)
  {
    //  cout<<st<<endl;
      return st;
  }


  if(cu>n || st>n || st>5050 )
   return 999999;
int &ret=dp[cu][st];
if(ret)
    return ret;
 int k1=fun(cu+1,n,m,st+1);

 int k2=fun(cu+2,n,m,st+1);
 return ret=min(k1,k2);

}




int main()
{
 int n,m,i,j,k,l;
 cin>>n>>m;

 //if(n>m*2)
   // cout<<-1<<endl;

 k=fun(0,n,m,0);

  if(k==999999)
    cout<<-1<<endl;
  else
    cout<<k<<endl;

return 0;
}

B. Dreamoon and WiFi :calculate no. of ways : recursive solution (branch and bound )


http://codeforces.com/contest/476/problem/B

#include<bits/stdc++.h>
using namespace std;
string s1,s2;
int val=0,n;
int dp[15][15];
int solve(int s,int l,int f)
{
    int &ret=dp[s][l];
    if(s==l)
    {
        if(f==val)
            return 1;
        else
            return 0;
    }
   
    int ct=0;                                   ///number of ways in starting is 0
    if(s2[s]=='+')
        ct+=solve(s+1,l,f+1);
    if(s2[s]=='-')
        ct+=solve(s+1,l,f-1);
    if(s2[s]=='?')
        ct+=solve(s+1,l,f+1)+solve(s+1,l,f-1);
    return ret=ct;                              /// In the last return this value

}
int main()
{
    int i,j,k,l;
    double ans;
    cin>>s1>>s2;
    n=s1.size();
    for(i=0;i<n;i++)
    {
        if(s1[i]=='+')
            val++;
        else
            val--;
    }
    double xx=1;
    for(i=0;i<n;i++)
    {
       if(s2[i]=='?')
       xx*=2.0;

    }
    k=solve(0,s2.size(),0);
    //cout<<k<<endl;
    ans=double(k);
    if(k==0)
        printf("%.10lf\n",ans);
    else
        printf("%.10lf\n",(double)ans/xx);

    return 0;
}

Thursday 24 September 2015

Equation solving in Programming

ans=(k*g)/(g1*g2);  (If the answer is an integer).


In these types of Equation solving program ,try to avoid multiplication .

Always do division to find the answer ,Otherwise there is a very possibilty of getting WA .

So, in 1st step:       g1=g1/g;

          2nd step :     ans=k/g1;

          3rd step :      ans=ans/g2;

Diophantine equation




           https://en.wikipedia.org/wiki/Diophantine_equation

            Diophantine equation is ax + by = c
give an integer solution only if gcd(a,b) divides c.




Solving Linear Diophantine equations

ax + by = c and gcd(a, b) divides c.
  1. Divide a, b and c by gcd(a,b).
  2. Now gcd(a,b) == 1
  3. Find solution to aU + bV = 1 using Extended Euclidean algorithm
  4. Multiply equation by c. Now you have a(Uc) + b (Vc) = c
  5. You found solution x = U*c and y = V * c

problem realted :https://www.codechef.com/APRIL12/problems/DUMPLING/

EXPLANATION

Given two integers A and B, let us try to figure out all the reachable integers. Consider
jumping X units to the right as adding X and jumping X units to the left as subtracting X.
Working out an example always helps.
If A = 4 and B = 6, observe that we can only reach every integer in
 the set { ..., -8, -6, -4, -2, 0, 2, 4, 6, 8, ... }
If A = 3 and B = 5, observe that we can only reach every integer in
 the set { ..., -3, -2, -1, 0, 1, 2, 3, ... }
If you try out other simple examples, soon you will be able to notice that given A and B,
one can only reach integers that are multiples of the greatest common divisor (gcd) of A and B.
 Another way of looking at this is that every integer P that satisfies, Ax + By = P, is reachable.
 Here x and y are arbitrary integers. [ x=2 means that the chef jumps 2A units to the
right, x=-5 means he jumps 5A units to the left]. It can be proved that P is a multiple of
the gcd of A and B.
Thus, Chef Shifu can reach multiples of the gcd of A and B. Let X = gcd(A,B). Chef Po can
reach multiples of the gcd of C and D. Let Y = gcd(C,D). Thus, every multiple of X which is also
 a multiple of Y can always be reached by both the chefs. If we find the least common multiple
of X and Y, say L, then every multiple of L can be reached by both.
Coming back to the solution - count all the positive reachable integers in the interval (0,K].
 This is simply K/L. The number of negative reachable integers must be same due to symmetry.
 And don't forget to add the center point too. So the answer is 2 * (K/L) + 1. Here, the only
problem was that L may not fit into a 64-bit integer but the final answer would always fit
 into a 64-bit signed integer. This could be handled by a simple repeated division.
From the definition of the least common multiple, we have L = (X * Y)/gcd(X,Y) , this is same
 as, S = X/gcd(X,Y) , L = S*Y
T = K/L = K/(S * Y), this is same as, R = K/S , T = R/Y
Thus, all the intermediate results could fit into 64-bit integers. Or you could learn to use your
 favorite library that handles large integers :)


ANSWER:


#include<iostream>
#include<cstdio>
#include<cassert>
#define SI(x) scanf("%d",&x)
typedef long long LL;
using namespace std;

#define MXT 50000
LL a,b,c,d;
LL ans,k;
int t;

LL gcd(LL a,LL b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}

LL lcm(LL a,LL b)
{
    LL ret = 1ll*a*b;
    LL g = gcd(a,b);
    ret/=(1ll*g);
    return ret;
}

int main()
{
    SI(t);
    while(t-- >0)
    {
        scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
        scanf("%lld",&k);

        LL g1 = gcd(a,b);
        LL g2 = gcd(c,d);
        LL g = gcd(g1,g2);
        
        g1/=g;

        ans = (k/g1);
        ans = ans/g2;
        ans = 2ll*ans + 1;
        
        printf("%lld\n",ans);
    }
    return 0;  
}

Wednesday 2 September 2015

(Repetitive numbers allowed "for loop recursion " )Print all possible strings of length k that can be formed from a set of n characters

Input: 
set[] = {'a', 'b'}, k = 3

Output:
aaa
aab
aba
abb
baa
bab
bba
bbb


Input: 
set[] = {'a', 'b', 'c', 'd'}, k = 1
Output:
a
b
c
d

This is a "branch and bound" type of Recursion in which we have to choose whether to "take a no." or  "not to take" that number . Here Repetition is allowed ,therefore a "for loop" is needed.





#include<bits/stdc++.h>

using namespace std;
set<vector<char> > s;
void gen(char a[],int n,int k,int cnt,vector<char> v,int j)
{
    if(cnt==k)
    {
     s.insert(v);
    }

    if(j>=n)
        return;

    for(int i=0;i<n;i++)
    {
        gen(a,n,k,cnt,v,j+1);
        v.push_back(a[i]);
        gen(a,n,k,cnt+1,v,j+1);
        v.pop_back();
    }
}


int main()
{
 char a[]={'a','b','c','d'};
 int n,k;
 cin>>n>>k;
 vector<char> v;
 gen(a,n,k,0,v,0);

set<vector<char> > ::iterator i;
 for(i=s.begin();i!=s.end();i++)
 {
     v=*i;
     for(int j=0;j<v.size();j++)
        cout<<v[j]<<" ";
         cout<<endl;
 }


 return  0;
}

NON Repeatitive ::: -- Print all increasing sequences of length k from first n natural numbers (Recursive)


http://www.geeksforgeeks.org/print-increasing-sequences-length-k-first-n-natural-numbers/

Geeksforgeeks.

Input: k = 2, n = 3
Output: 1 2
        1 3
        2 3 

Input: k = 5, n = 5
Output: 1 2 3 4 5

Input: k = 3, n = 5
Output: 1 2 3
        1 2 4
        1 2 5
        1 3 4
        1 3 5
        1 4 5
        2 3 4
        2 3 5
        2 4 5
        3 4 5
This is a Branch and Bound type of Problem. In which you have to decide whether to "take a 
number"  or  "not to take"  a number. After that make a recursive call again.
#include<bits/stdc++.h>

using namespace std;

int fi(int dest,int steps,int cu)
{
 if(cu==dest)
    return steps;
 if(abs(cu)>dest)
    return INT_MAX;
  return min(fi(dest,steps+1,steps+cu+1),fi(dest,steps+1,cu-steps-1));
}

int main()
{
int dest,i,j;
cin>>dest;
cout<<fi(dest,0,0)<<endl;
return 0;
}






Minimum Steps to reach a destination (Recursive method )

http://www.geeksforgeeks.org/minimum-steps-to-reach-a-destination/

GeeksforGeeks.

It is a ""branch and bound"" type of recursive problem, in which we have two options of going either left or Right in a number line.

 And the target is to reach a particular point.

Starting Point is Zero.




#include<bits/stdc++.h>

using namespace std;

int fi(int dest,int steps,int cu)
{
 if(cu==dest)
    return steps;
 if(abs(cu)>dest)
    return INT_MAX;
  return min(fi(dest,steps+1,steps+cu+1),fi(dest,steps+1,cu-steps-1));
}

int main()
{
int dest,i,j;
cin>>dest;
cout<<fi(dest,0,0)<<endl;
return 0;
}



Spoj Problem--> Coins Recursive method.

                                            http://www.spoj.com/problems/COINS/

COINS - Bytelandian gold coins


A Coin at a Moment can be changed to three coins (n/2) ,(n/3) , (n/4). Here Map is used to save the 
result in a current state ( dp ) , The saved result can be used next time it is used,



#include<bits/stdc++.h>

using namespace std;

map<long long int,long long int > dp;

long long int brk(long long int n)
{
    if(dp[n])
        return dp[n];

    if(n<12)
        return n;

   long long int ct=0;

  if(n>=12)
    {
      ct+=brk(n/2);
      ct+=brk(n/3);
      ct+=brk(n/4);
    }
  return dp[n]=ct;
}


int main()
{

 long long int n;
 while(scanf("%lld",&n)!=EOF)
 {

  cout<<brk(n)<<endl;
  dp.clear();

 }
return 0;
}

Program to find total number of Paths between two points in a graph.( Recursive method )


If the "source" Pointer will become "destination" (after the cursion calls ) the path array will get printed.



#include<bits/stdc++.h>

using namespace std;

int fin(vector<int> a[],int src,int dest,vector<int> path,int visited[])
{
    path.push_back(src);

    if(src==dest)
    {
      for(int i=0;i<path.size();i++)
             cout<<path[i]<<" ";
               cout<<endl;
               return 1;
    }

    visited[src]=1;
    int ct=0;

    for(int i=0;i<a[src].size();i++)
        if(visited[a[src][i]]==0)
            ct+=fin(a,a[src][i],dest,path,visited);

     visited[src]=0;
     return ct;
}



int main()
{
 vector<int> v[4];

 v[0].push_back(1);
 v[0].push_back(2);
 v[0].push_back(3);
 v[1].push_back(2);
 v[1].push_back(3);
 v[3].push_back(2);

  int visited[10];  for(int i=0;i<10;i++) visited[i]=0;

 vector<int> path;
 cout<<fin(v,0,2,path,visited)<<endl;

return 0;
}

Uploading and Running Lambda function in AWS

Main.go package main import ( "fmt" "encoding/json" "log" "github.com/aws/aws-lambda-g...