Trees

Problem:

Write a code to pack and unpack a binary tree.

Sol: Each node will be encapsulated in '[' and ']'.
Empty tree: []
Tree with single node: [4[][]]
Tree: 4--8  ==> [4[7[][]][8[][]]]
         |
         7
Working code

 #include <iostream>  
 #include <stdio.h>  
 #include <cstdlib>  
 #include <cstring>  
 #include <stack>  
 #include <list>  
 using namespace std;  
 struct node {  
  int data;  
  struct node* left;  
  struct node* right;  
 };  
 void print(struct node* root) {  
  cout<<"[";  
  if(root != NULL) {  
  cout<<root->data;  
  print(root->left);  
  print(root->right);  
  }  
  cout<<"]";  
  return;  
 }  
 //use stack.  
 //node: [val<left><right>]  
 stack<struct node*> tree;  
 struct node* unpack(char* str) {  
  int i=0;  
  while(str[i] != '\0') {  
  if(str[i] == '[') {  
   tree.push(NULL);  
   i++;  
  } else if (str[i] == ']') {  
   if(str[i-1] == ']') {  
   struct node* right = tree.top();tree.pop();  
   struct node* left = tree.top();tree.pop();  
   struct node* parent = tree.top();tree.pop();  
   if(parent != NULL) {  
    parent->left = left;  
    parent->right = right;  
   }  
   if(tree.size() > 1) {  
    tree.pop();  
    tree.push(parent);  
   } else  
    return parent;  
   } else if(str[i-1] == '[') {  
   if(tree.size() == 1)return NULL;  
   }  
   i++;  
  } else {  
   int j;  
   for(j=i;str[j] != '[' && str[j] != ']';j++);  
   int sum =0;int mult = 1;  
   for(int k=j-1;k >=i;k--) {  
   sum += mult * (str[k]-48);  
   mult *= 10;  
   }  
   struct node* node = (struct node*)malloc(sizeof(struct node));  
   node->left = NULL;  
   node->right = NULL;  
   node->data = sum;  
   tree.push(node);  
   i=j;  
  }  
  }  
 }  
 int main() {  
  char* str = new char[100];  
  cin>>str;  
  struct node* root = unpack(str);  
  print(root);  
  cout<<endl;  
  return 0;  
 }  

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