Posts

Showing posts from March, 2015

DP hackerrank (stock maximize)

STock Maximize (iterative dP  and  branch & bound approach ) #include<bits/stdc++.h> using namespace std; long long int sell[1000000],a[1000000]; int main() {  int t;  cin>>t;  while(t--)  {   long long int n,i,j,k,ans=0,m=0;   cin>>n;   for(i=0;i<n;i++)    cin>>a[i];   for(i=n-1;i>=0;i--)    {     if(m<a[i]) m=a[i];     sell[i]=m;    }   for(i=0;i<n;i++)   {     if(sell[i]>a[i])    ans+=sell[i]-a[i];   }   cout<<ans<<endl;  } return 0; } -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------Branch And  Bound -----------...

DP (rectangles perimetere (spoj) ,,,Sherlock and cost (hackerrank) ) -->> 2^n DP

1) DP prblm of 2^n type ,(rectangles perimetre http://www.spoj.com/problems/MMAXPER/) #include using namespace std; int main() { int n; cin>> n; int a[n],b[n],dp[n][2],i,j,k; for(i=0;i >a[i]>>b[i]; dp[0][0]=a[0], dp[0][1]=b[0]; for(i=1;i using namespace std; int dp[100002][2]; int a[100002]; int main() { int t; cin>>t; while(t--) { int n,i,j,k; cin>>n; dp[0][0]=0; dp[0][1]=0; for(i=0;i >a[i]; for(i=1;i

Subarrays problems

Image
1)   Number of subarrays of a array whose sum is K 2)  number of sub arrays of a array whose sum is multiple of  K 3) Number of subarrays of a array whose xor is Maximum (Lalit kundu post ,Quora ) http://threads-iiith.quora.com/Tutorial-on-Trie-and-example-problems 4) number of distinct subarrays of a array http://stackoverflow.com/questions/17513359/number-of-distinct-subarrays 2) solution (number of subarrays whose sum is multiple of K) #include<bits/stdc++.h> using namespace std; int B[1000]; int main() {   int n,k;   cin>>n>>k;   int A[n];      for(int i=0;i<n;i++)         cin>>A[i]; int s,i,ans; B[0]++; s = 0; for (i = 0;i<= n-1;i++) {   s=(s + A[i])%k;   B[s]++; } ans=0; for(i = 0 ;i<= k-1;i++) { cout<<B[i]<<" ";   ans+=(B[i]*(B[i]-1))/2; } cout<<endl;...
Image
edit distance http://www.spoj.com/problems/EDIST/ #include<iostream> #include<stdio.h> #include<bits/stdc++.h> using namespace std; int dp[2001][2001]; char a[400001],b[400001]; int main() {     int t;     cin>>t;     while(t--)     { long long int i,j,l1,l2; //cout<<"enter first string "<<endl; scanf("%s",a); //cout<<"enter second string "<<endl; scanf("%s",b); //int dp[100][100]; l1=strlen(a); l2=strlen(b);  for(j=0;j<=l2;j++)    {dp[0][j]=j; } for(j=0;j<=l1;j++)    {dp[j][0]=j;} for(i=1;i<=l1;i++) {  for(j=1;j<=l2;j++)  {    if(a[i-1]==b[j-1])    dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]));    else    dp[i][j]=min(dp[i][j-1]+1,min(dp[i-1][j]+1,dp[i-1][j-1]+1));;  } } //cout<<dp[l1][l2]; cout<<dp[l1][l2]<<endl;   ...

knapsack /unbounded knapsack

Image
http://www.spoj.com/problems/KNAPSACK/    (simple knapsack) http://www.spoj.com/problems/LKS/         (large knapsack) Knapsack table filling #include<stdio.h> int maxi(int a,int b) {     if(a>b)         return a;     else         return b; } int main() {     int i,h,j,p,mm,summ=0,g,mw;     scanf("%d",&mw);     scanf("%d",&h); int w[h+1],v[h+1]; for(i=1;i<h+1;i++) { scanf("%d",&w[i]); scanf("%d",&v[i]); } v[0]=0;w[0]=0; int n[h+1][mw+1]; v[0]=0;w[0]=0; for(i=0;i<mw+1;i++)     n[0][i]=0; for(i=0;i<h+1;i++)     n[i][0]=0; for(i=1;i<h+1;i++) {     for(j=1;j<mw+1;j++)     {         p=j-w[i];         if(p<0)                    ...