Just programming

                                                 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(...

                                                   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) ...

                             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<...

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++)  { ...

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)   ...

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[...

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])   { ...

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        ...

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++) ...

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 ; }

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 ...

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;

           https://en.wikipedia.org/wiki/Diophantine_equation             Diophantine equation is  ax + by = c give an integer solution only if  gcd(a,b) divides c . down vote Solving Linear Diophantine equations ax + by = c  and  gcd(a, b)  divides  c . Divide a, b and c by gcd(a,b). Now gcd(a,b) == 1 Find solution to aU + bV = 1 using  Extended Euclidean algorithm Multiply equation by c. Now you have a(Uc) + b (Vc) = c 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 in...

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; ...

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; }

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; }

                                            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 ...

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[...