Friday, 25 January 2013

Pots of Gold

Given N pots of gold placed in a line. The number of coins contained in pot i is represented by A[i]. Two player start playing the game. In each turn a player will pick the pot either from the beginning or from the end of the line. The selected pot will be removed from the line. Assuming both player play optimally write algorithm to decide who will win. A and B are players, assume A starts first.

Solution O(n^2) sol.
Compute
P[i][j] = max {A[i] - P[i+1][j], A[j] - P[i][j-1]} + S[i][j] for all i<j
P[i][i] = A[i]
P[0][N-1] will be coin gathered by A (player playing first)
S[0][N-1] - P[0][N-1] would be coins gathered by B (player playing second).

Test case

N=4 (5,20, 4,1) --> A wins
N=5 (5,5, 20, 1, 1) --> B wins

N=5  (5 5 20 8 14) --> A wins

N=5  (5 5 20 1 14) --> B win

Working Code





 #include <stdio.h>  
 #include <iostream>  
 #define max(a,b) a>b?a:b  
 using namespace std;  
 int main() {  
  int n,s;  
  cin>>n;  
  int a[n];  
  int sum[n][n];  
  for(int i=0;i<n;i++) {  
  cin>>a[i];  
  for(int j=0;j<i;j++) {  
   sum[i][j] = sum[i][j-1] + a[i];  
  }  
  sum[i][i] = a[i];  
  }  
  s = sum[0][n-1];  
  for(int i=n-2;i>=0;i--) {  
  for(int j=i+1;j<n;j++) {  
   sum[i][j] += max(a[i]-sum[i+1][j],a[j]-sum[i][j-1]);  
  }  
  }  
  if(sum[0][n-1] > s - sum[0][n-1])cout<<"A wins"<<endl;  
  else cout<<"B wins"<<endl;  
  return 0;  
 }  

No comments:

Post a Comment