Optimal Strategy for Coin Game

Consider a row of n coins of value v1,v2.......,vn. We play a game against an opponent by alternating turns. In each turn a player selects either the first coin or the last coin from the row, removes it permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Let V(i,j) : max value we can definitely win if its our turn and only coins with values vi...vj remain.

Base cases: Compute values of V(i,i) and V(i,i+1).

Computation of V(i,j): Let out of n coins only coins from i to j remain. Then the value of V(i,j) is maximum of the two choices: i) if we choose ith coin . ii) if we choose jth coin.
Suppose we pick ith coin. Then the opponent can pick i+1th coin or jth coin. The amount we can necessarily get after he picks his coin is the minimum of V(i+1,j-1), V(i+2,j), plus the vi we had picked earlier.

Similarly, if we had picked jth coin, we would necessarily receive min[ V(i,j-2), V(i+1,j-1)] + vj.

The max amount we can obtain overall is the maximum of the two.


Code:

#include <vector>
#include <iostream>
using namespace std;
int solve(const vector<int> &coinval)
{
const int numCoins = coinval.size();

vector<int> states;
states.resize(numCoins*numCoins);

for(int diff = 0;diff != numCoins;++diff)
       {
for(int ai = 0;ai+diff != numCoins;++ai)
               {
int bi = ai+diff;
int sidx = ai*numCoins + bi;

if(diff == 0)
                       {
states[sidx] = coinval[ai];
}
                       else if(diff == 1)
                       {
states[sidx] = max(coinval[ai], coinval[bi]);
}
                       else
                       {
int idxaa = (ai+2)*numCoins + bi;
int idxab = (ai+1)*numCoins + bi-1;
int idxba = idxab;
int idxbb = ai*numCoins + bi-2;

int a = coinval[ai] + min(states[idxaa],states[idxab]);
int b = coinval[bi] + min(states[idxba],states[idxbb]);

states[sidx] = max(a,b);
}
}
}

return states[numCoins-1];
}

int main()
{
vector<int> x;
        int n,v,i;
        cin>>n;
        for(i=0;i<n;i++){ cin>>v; x.push_back(v);}

cout << solve(x) <<endl;
 
return 0;
}

Balanced Partition Problem

Given n integers. Partition them into 2 sets of sums S1 and S2 such that |S1-S2| = minimum.

Code:


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
using namespace std;
int ar[1000];
int m[100000];
int main()
{
    int i,j,n,k,sum=0,ans=0;
    cin>>n;
    for(i=0;i<n;i++) { cin>>ar[i]; sum+=ar[i];}
   
    for(i=0; i<sum+10; i++) m[i]=0;
        m[0]=1;
       
    for(i=0; i<n; i++)
    {
         for(j=sum; j>=ar[i]; j--)
               m[j] |= m[j-ar[i]];
    }
    for(i=sum/2;i>=0;i--)
      if(m[i]==1)
         {ans=i; break;}
   
    cout<<(sum - 2*i)<<endl;
    ans=0;
    return 0;
}

Largest Sum in a Matrix

Given a mxn matrix. Print the largest sum that can be obtained from a kxk submatrix.

Code:


#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
using namespace std;
int A[100][100];
int S[100][100];
int KS[100][100];
int main()
{
    int m,n,k,i,j,maxs=0,s=0;
    cin>>m>>n>>k;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
           cin>>A[i][j];
    }
    for(i=1;i<=m;i++)
    {
       for(j=1;j<=k;j++)s+=A[i][j];
       S[i][1]=s;
       s=0;
    }
     
    for(i=1;i<=n;i++)
    {
        for(j=2;j<= n-k+1; j++)
           S[i][j]=S[i][j-1]-A[i][j-1] + A[i][j+k-1];
    }
    for(j=1;j<=n;j++)
    {
         for(i=1;i<=k;i++) s+=S[i][j];
          KS[1][j]=s;
          s=0;
    }
       
    for(i=2;i<=m-k+1;i++)
    {
        for(j=1;j<=n-k+1;j++)
        {
            KS[i][j]=KS[i-1][j]-S[i-1][j]+S[i+k-1][j];
         
        }
    }
   for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
             if(KS[i][j]>maxs) maxs=KS[i][j];
         
        }
    }
    cout<<maxs<<endl;
    return 0;
}