JOIN
 Revision History
 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 My Post History  |  My Watches  |  User Settings Forums TopCoder Cookbook Algorithm Competitions - New Recipes Re: 2.4.? Commonly used DP state domains Revision History (2 edits)
 Re: 2.4.? Commonly used DP state domains (response to post by syg96) 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) 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) 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.