For given array X[1..m] and Y[1..n] , find number of pairs such that x^y > y^x

Reference: http://www.geeksforgeeks.org/find-number-pairs-xy-yx/

Solution: a) Brute force O(m*n)
b) if y > x then x^y > y ^ x (with some exceptions which should not be counted) (rule a)
    if y <= x then x^y <= y^x (with some exceptions which should be counted) (rule b)

To find exceptions, try different values of x
Case x = 0: {Nothing should be counted}
    clearly for no value of y, 0 (0^y) will be greater then 1 (y^0), hence if x = 0 no such pair exist.
Case x = 1: {0s in y should be counted}
    Case y = 0: Exception of rule b
    Case y = 1: fine.
    Case y>1 : Exceptions of rule a
Case x = 2:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: fine
    Case y = 3: exception of rule a
    Case y = 4: exception of rule a
    Case y > 4: fine
Case x = 3:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y = 2: Exception of rule b
    Case y = 3: fine
    Case y >= 4: fine
Case x > 4:
    Case y = 0: Exception of rule b
    Case y = 1: Exception of rule b
    Case y > x: fine

Thus sort Y and count number of 0s,1s,2s,3s,4s O(mlogm + m) let it be y0,y1,y2,y3,y4
count = 0
for each X:
  if(x ==0){
  } else if(x==1) {
     count += y0;
  } else if (x==2) {
     count += y0 + y1;
     //binary search in y to fine least value greater than x, let it be i
      count += (n-i - y3-y4);
  } else if (x==3) {
     count += y0 + y1 + y2;
     //binary search in y to fine least value greater than x, let it be i
     count += (n-i);
  } else {
      count += y0 + y1;
       //binary search in y to fine least value greater than x, let it be i
       count += (n-i);
  }
   
   
   

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