JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes 2.4.? Commonly used DP state domains [ 1 2 ]    NEXT >
 Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply Subtrees(vertices) of a given rooted treeThe problem involves a rooted tree. Sometimes a graph is given and its DFS search tree is used. Some sort of result can be calculated for each subtree. Since each subtree is uniquely identified by its root, we can treat DP over subtrees as DP over vertices. The result for each non-leaf vertex is determined by the results of its immediate children.The DP over subtree has a state domain in form (v,a) where v is a root of subtree and "a" may be some additional parameters. states are ordered naturally be tree order on vertices. Therefore the easiest way to iterate through states in correct order is to launch DFS from the root of tree. When DFS exits from a vertex, its result must be finally computed and stored in global memory. The code generally looks like: bool vis[N]; //visited mark for DFS res[N]; //DP result array   void DFS(int v) { //visit v-rooted subtree recursively vis[v] = true; //mark vertex as visited res[v] = ???; //initial result, which is final result in case v is leaf for (int i = 0; i sons; for (int i = 0; iKi. Since the sum of all Ki is N, you will get O(N*A) space.
 Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply Layer count + layer profileThis is the toughest type of DP state domain. It is usually used in tiling or covering problems on special graphs. The classic examples are: calculate number of ways to tile the rectangular board with dominoes (certain cells cannot be used); or put as many chess figures on the chessboard as you can so that they do not hit each other (again, some cells may be restricted).Generally speaking, all these problems can be solved with DP over subsets (use set of all cells of board). DP with profiles is an optimization which exploits special structure in this set. The board we have to cover/tile is represented as an array of layers. We try to consider layers one by one and store partial solutions after each layer. In simple rectangular board case layer is one row of the board. The profile is a subset of cells in current row which are already tiled.The state domain has form (k,p) where k is number of fully processed layers and p is so-called profile of solution. Profile is the necessary information about solution in layers that are not fully processed yet. The transitions go from (k,p) to (k+1,q) where q is some new profile. The number of transitions for each state is usually large, so they all are iterated through by recursive search, sometimes with pruning. The search has to find all the ways to increase the partial solution up to the next layer.The example code below calculates the number of way to fully cover empty cells on the given rectangular board with dominoes.int res[M+1][1<
 Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply Examples:InformFriendsWe are asked to find assignment man->fact which maximizes the number of facts with constraint that everyone must know all the facts. In the optimal assignment people can be divided into fact-groups. Each fact-group consists of people who are told the same fact. And each fact-group must be able to tell everybody else about the fact.Let's precalculate for each subset of people whether they can become a fact-group. The subset can be a fact-group if set of all thier friends united with them is the whole set. After possible fact-groups are calculated, we have to determine maximal number of non-intersecting fact-groups in the set of people. We can define state domain (s)->R where s is subset of people and R is problem answer for them. To determine the answer for state s we have to subtract one of its fact-groups. It is a subset of s and forms a fact-group. So we can iterate through all subsets of s and try them as fact-groups. n = matr.size(); int i, j, u; for (i = 0; i<(1<0; j = (j-1)&i) if (cover[j]) //iterate through all fact-group subsets if (res[i] < res[i^j] + 1) res[i] = res[i^j] + 1; //relax the result for i if (ans < res[i]) ans = res[i]; //relax the global answer } return ans; Breaking strings (ZOJ 2860)This problem is solved with DP over substrings. Let's enumerate all required breaks and two ends of string with numbers 0, 1, 2, ..., k. Then res[L,R] will be result for the substring which starts in L-th point and ends in R-th point. To get this result we should look through all possible middle points M and consider res[L][M] + res[M][R] + (x[R]-x[L]) as a result. By doing this we get a clear O(k^3) solution (which is TL).What makes this problem exceptional is the application of Knuth's optimization. This trick works only for optimization DP over substrings for which optimal middle point depends monotonously on the end points. Let mid[L,R] be the first middle point for (L,R) substring which gives optimal result. It can be proven that mid[L,R-1] <= mid[L,R] <= mid[L+1,R] - this means monotonicity of mid by L and R. If you are interested in a proof, read about optimal binary search trees in Knuth's "The Art of Computer Programming" volume 3 binary search tree section.Applying this optimization reduces time complexity from O(k^3) to O(k^2) because with fixed s (substring length) we have m_right(L) = mid[L+1][R] = m_left(L+1). That's why nested L and M loops require not more than 2k iterations overall. for (int s = 0; s<=k; s++) //s - length(size) of substring for (int L = 0; L+s<=k; L++) { //L - left point int R = L + s; //R - right point if (s < 2) { res[L][R] = 0; //DP base - nothing to break mid[L][R] = l; //mid is equal to left border continue; } int mleft = mid[L][R-1]; //Knuth's trick: getting bounds on M int mright = mid[L+1][R]; res[L][R] = 1000000000000000000LL; for (int M = mleft; M<=mright; M++) { //iterating for M in the bounds only int64 tres = res[L][M] + res[M][R] + (x[R]-x[L]); if (res[L][R] > tres) { //relax current solution res[L][R] = tres; mid[L][R] = M; } } } int64 answer = res[0][k];
 Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply BlockEnemySince tree is given in the problem statement, we should try DP on subtrees first=) Given any correct solution for the whole tree, any subtree of it is also correct. So if all pairs of occupied towns are separated, then in each subtree they are also separated. So we can try to use state domain (v)->R where v represents subtree and R represents minimal effort to solve the problem for this subtree. But we'll discover soon that connecting subtrees correctly is impossible because we need to know whether there is an occupied town connected with outside part of subtree. We call such a solution for subtree dangerous. Now we add the boolean parameter (solution is safe/dangerous) in the state domain. Let res[v][t] be the minimal effort needed to get a correct solution for v-subtree which is dangerous(if d=1)/safe(if d=0).Initially we consider edge which is going out of subtree indestructible. We will handle the destruction of outgoing edge later. In this case, the solution for leaves is easy to obtain. If v is non-occupied leaf, then it forms a safe solution, and dangerous solution is impossible to get. If it is occupied, then the solution is dangerous with no effort, and impossible to make safe. Then if the vertex v is not leaf, we add its sons one by one. When adding a son s to v-subtree, we have the following merging rules:1. v=safe + s=safe -> v=safe2. v=dangerous + s=safe -> v=dangerous3. v=safe + s=dangerous -> v=dangerous4. v=dangerous + s=dangerous -> incorrect solutionAfter merging by these rules, we receive a solution for v-subtree in case of indestructible outgoing edge. Now what changes if the outgoing edge is destructible? We can destruct it by paying additional effort. In this case a dangerous solution turns into safe one. The root of tree has no outgoing edge.The problem answer is minimal effort of safe and dangerous solutions for the root ot DFS tree. The time complexity is O(N^2) because adjacency matrix is used, but can be easily reduced to O(N) with neighbors lists.int res[MAXN][2];   void DFS(int v, int f) { //traverse v-subtree, f is father of v vis[v] = true; //mark v as visited res[v][0] = (occ[v] ? 1000000000 : 0); //result in case of leaf res[v][1] = (occ[v] ? 0 : 1000000000); for (int s = 0; s= 0 && res[v][0] > res[v][1] + matr[v][f]) //we can destroy upgoing edge (v-f) res[v][0] = res[v][1] + matr[v][f]; } ... DFS(0, -1); //run DFS from 0 (with no father) return min(res[0][0], res[0][1]); //whether root is dangerous does not matter }