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

## No comments:

## Post a Comment