TC SRM453.5 D1 450 (PlanarGraphShop)

Category: Dynamic Programming, Graph Theory
URL: http://www.topcoder.com/stat?c=problem_statement&pm=10412

This problem asks us to determine the minimum number of simple planar graphs we need to exact use of N gold coins. Each planar graph has an associated cost function based on the number of vertices and edges the graph has, more specifically: cost = (number of vertices)^3 + (number of edges)^2. We should immediately see a knapsack-like algorithm which strongly suggests using dynamic programming. The main problem lies with determining what number of vertices and edges constitutes a valid simple planar graph.

Luckily there is a simple theorem which we can use as an upper bound calculation to determine whether a pairing of (#V,#E) is a valid pair. For graphs that has at least 3 vertices: if e > 3v - 6 then this will imply nonplanarity. Hence, we can deduce that all e <= 3v - 6 has a simple planar graph representation. For graphs that has less than 3 vertices we can simply hand calculate the combinations. Once we know what our valid pairings are we can construct a set of feasible cost moves based on our cost function by iterating through all possible pairings of # vertices and # edges. We then apply a simple DP algorithm to calculate the minimum number of planar graphs needed.

An implementation is shown below:

class PlanarGraphShop {
public:
   int bestCount(int);
};

int dp[50001];
vector<int> moves;

#define INF 1 << 20

int func(int N) {
   if (N == 0) return 0;
   if (N < 0) return INF;
   if (dp[N] != -1) return dp[N];
   int res = INF;
   for (int i = 0; i < moves.size() && moves[i] <= N; i++) 
      res <?= 1 + func(N - moves[i]);
   return dp[N] = res;
}

int PlanarGraphShop::bestCount(int N) {
   set<int> costs;
   costs.insert(1); costs.insert(8); costs.insert(9);
   for (int v = 1; v < 37; v++) 
      for (int e = 0; e <= 3 * v - 6; e++)
         costs.insert(v*v*v + e*e);
   moves = vector<int>(costs.begin(),costs.end());
   memset(dp,-1,sizeof(dp));
   return func(N);
}