Maximize value of coins from k stacks, of n coins each

Question

You are given k stacks, of n coins each.  The value of i-th coin in j-th stack is given by v[i][j].

You play a game against an opponent by alternating turns. In each turn, a player selects one of the top coins (the coin at the highest location of the stack), removes it permanently, and receives the value of the coin. In each move, each person removes one coin only, and can not remove a coin that is not at the top of its stack.

Design an algorithm to maximize the money value you can win if you move first.

Answer 1

Notation:

Let MCV (H₁, H₂, H₃, …, H_k) denote the maximum coin value that we can obtain from the given k stacks coins. H_i means the height of the i-th stack. Further, let S (H₁, H₂, H₃, …, H_k) denote the sum of the values for all coins in the k stacks.

Recursive Formulation:

We observe that once the first player pockets one of the top coins in these k stacks, the opponent realizes the maximum value from the remaining coins.  Therefore, the value realized by the first player is the sum of all k stacks minus the value realized by the opponent.  Therefore, we can write MCV (H₁, H₂, H₃, …, H_k) as:

∀ H_i > 0 {1≤ i ≤k}

MCV (H₁, H₂, H₃, …, H_k) = max {S (H₁, H₂, H₃, …, H_k) - MCV (H₁-1, H₂, H₃, …, H_k), MCV (H₁, H₂-1, H₃, …, H_k), MCV (H₁-1, H₂, H₃-1, …, H_k),…, MCV (H₁-1, H₂, H₃, …, H_k-1) }

This can further be written as:

MCV (H₁, H₂, H₃, …, H_k) = S (H₁, H₂, H₃, …, H_k) – min {MCV (H₁-1, H₂, H₃, …, H_k), MCV (H₁, H₂-1, H₃, …, H_k), MCV (H₁, H₂, H₃-1, …, H_k),…, MCV (H₁, H₂, H₃, …, H_k-1) }

The base case of the recurrence can be set as MCV (0, 0, …,0) = 0, S (0, 0, …,0) = 0.

Algorithm:

The challenge is that we cannot build a k dimensions array like MCV [H₁] [ H₂] [ H₃] …[H_k]. So we transform the k dimensions to one dimension.

//Initailize

int kn=(int) (Math.pow((n+1),k));

int MCV[]=new int[kn];

int S[]=new int[kn];

//Base case

MCV[0]=0;
S[0]=0;

for (int i=1;i<kn;i++){
  int[] h=new int[k];//h[] are the height of k stacks
  for (int j=0;j<k;j++){
    int division=(int)Math.pow((n+1),j);
    int mod=i/division;
    h[j]=mod%(n+1);
  }

  for(int j=0;j<k;j++){
    if(h[j]>0){
       S[i]=S[i-(int)Math.pow((n+1),j)]+v[j][h[j]];
       break;}
    }

  int min=Integer.MAX_VALUE;
  for(int j=0;j<k;j++){
    if(h[j]>0){
       if(MCV[i-(int)Math.pow((n+1),j)]<min){
          min=MCV[i-(int)Math.pow((n+1),j)];
        }
     }

  }

  MCV[i]=S[i]-min;

}

Time Complexity:

O(n) is kn*k, kn is Math.pow((n+1),k). So, O(n) = k*n^k

Answer 2

Notation: Let MCV(V, i, j) denote the maximum coin value that we can obtain given the list of coins V[i..j] .  Further, let S(V,i,j) denote the sum of the values of all the coins in V[i..j] .
Recursive Formulation: We observe that once the first player pockets the first or the last coin, the opponent realizes the maximum value from the remaining list. Therefore, the value realized by the first player is the sum of the list minus the value realized by the opponent.  Therefore, we can write MCV(V,i,j) as:
MCV(V,i,j)=  ma x {S(V,i,j) – MCV(V – v i ), S(V,i,j) MCV(V – v j )}
This can further be written as: MCV(V,i,j)=S(V,i,j) – mi n {MCV(V – v i ), MCV(V – v j ) }
The base case of the recurrence can be set as MCV(φ) = 0 , or equivalently that the value that can be realized by a single element list is the value of that element.
Algorithm: This algorithm works like many other algorithms that need to “grow” the range of the array.  Specifically, the iterations can work as follows:
Notation: Let MCV(V, i, j) denote the maximum coin value that we can obtain given the list of coins V[i..j] .  Further, let S(V,i,j) denote the sum of the values of all the coins in V[i..j] .
Recursive Formulation: We observe that once the first player pockets the first or the last coin, the opponent realizes the maximum value from the remaining list. Therefore, the value realized by the first player is the sum of the list minus the value realized by the opponent.  Therefore, we can write MCV(V,i,j) as:
MCV(V,i,j)=  ma x {S(V,i,j) – MCV(V – v i ), S(V,i,j) MCV(V – v j )}
This can further be written as: MCV(V,i,j)=S(V,i,j) – mi n {MCV(V – v i ), MCV(V – v j ) }
The base case of the recurrence can be set as MCV(φ) = 0 , or equivalently that the value that can be realized by a single element list is the value of that element.
Algorithm: This algorithm works like many other algorithms that need to “grow” the range of the array.  Specifically, the iterations can work as follows:
double[][] S = new double[n][n];

double[][] MCV = new double[n][n];

// Initialize S[i,i] = V[i]

// Initialize MCV[i,i] = V[i]

for i=0 to n-2

for j=i+1 to n-1

S[i,j]=S[i,j-1]+V[j]

for k=1 to n-1

for i=0 to n-2

MCV[i,i+k] = S[i,i+k] - min{MCV[i+1,i+k], MCV[i,i+k-1]}