save all special node

Problem :
Consider A tree, such that root node is made black first and then its child nodes in next step and so on. In each step you can make one node as white node. Any node which is made white will prevent itself and its decendent node from becoming black.
Eg If root has two child, and it is black at start, in next step it can make its child node as black but you can prevent complete subtree of one child node by making it white.
The problem is to tell if the a given set of special nodes can be prevented from becoming black.
Constraint : any node can have atmost 2 child.

solution
a) Find a path from root to any leaf node which has no special node on the path and leaf node is not a special node. If such path exist, it possible else not
b) consider a function f(v) which is true if and only if subtree rooted at node v can be saved when v is made black and none of its child node are black.
f(V) = false, if v is special node
       = true , if v is not special node and v is leaf node
      = true, if v has atmost 1 child
     = f(u) | f(w) , u and w are child node of v

solution - Google Interview Question - 16th Feb 2011

O(n^2) solution:
f[i][j] = sum[i][j] + max(a[i]-f[i+1][j],a[j]-f[i][j-1])
f[i][i] = a[i];


#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define MAXPOT 1000
int optA[MAXPOT*MAXPOT];
int flag[MAXPOT*MAXPOT];
int optimal_a(int* coin,int first,int last,int numPots)
{
    if(flag[first * numPots + last] == 1)
    {
          return optA[first * numPots + last];
    }
    if(first == last)
    {
             optA[first * numPots + last] = coin[first];
             flag[first * numPots + last] = 1;
             return coin[first];
    }
    if(last < first)return 0;
    int val1,val2;
    val1= coin[first] - optimal_a(coin,first+1,last,numPots);
    val2= coin[last] - optimal_a(coin,first,last-1,numPots);
    return max(val1,val2);
}
int main()
{
    int numPots;
    cin>>numPots;
    int coin[numPots];
    memset((void*)flag,0,MAXPOT*MAXPOT*sizeof(int));
    for(int i = 0 ;i<numPots;i++)
            cin>>coin[i];
    cout<<optimal_a(coin,0,numPots-1,numPots)<<endl;
           
    return 0;
}

Google Interview Question 16th Feb 2011

Given N pots arranged in a line. Each pot contains some gold coins. Two players A & B start playing a game in which each player will choose a pot alternatively. The constraint is that they can choose the pots at the beginning of the line or at the end of line (The pot once picked is removed from the line). The player which has more number of coins at the game wins, assuming A starts the game. Both player make optimum choice.
Example
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 wins


Solution