JOIN
Get Time
forums  Revision History
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 tree

The 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<nbr[v].size(); i++) {     //iterate through all sons s
      int s = nbr[v][i];                        
      if (!vis[s]) {                            //if vertex is not visited yet, then it's a son in DFS tree
        DFS(s);                                 //visit it recursively
        res[v] = DPInduction(res[v], res[s]);   //recalculate result for current vertex
      }
    }
  }
  ...
  memset(vis, false, sizeof(vis));              //mark all vertices as not visited
  DFS(0);                                       //run DFS from the root = vertex 0
  answer = DPAnswer(res[0]);                    //get problem answer from result of root

Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.

The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and "a" is additional info.
Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a].
Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
  bool vis[N];
  gres[N][A];
  intres[N+1][A];
  
  void DFS(int v) {
    vis[v] = true;
 
    vector<int> sons;
    for (int i = 0; i<nbr[v].size(); i++) {    //first pass: visit all sons and store their indices
      int s = nbr[v][i];
      if (!vis[s]) {
        DFS(s);
        sons.push_back(s);
      }
    }
 
    int SK = sons.size();                      //clear the internal results array
    for (int k = 0; k<=SK; k++)
      memset(intres[k], ?, sizeof(intres[k]));
 
    for (int a = 0; a<A; a++)                  //second pass: run internal DP over array of sons
      intres[0][a] = InternalDPBase(v, a);
    for (int k = 0; k<SK; k++)                 //k = number of sons considered so far
      for (int a = 0; a<A; a++)                //a = additional parameter for them
        for (int b = 0; b<A; b++) {            //b = additional parameter for the son being added
          int na = DPTransition(v, a, b);
          int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
          intres[k+1][na] = DPMerge(intres[k+1][na], nres);
        }
    for (int a = 0; a<A; a++)                  //copy answer of internal DP to result for vertex
      gres[v][a] = intres[SK][a];
  }
  ...
  memset(vis, false, sizeof(vis));              //series of DFS
  for (int v = 0; v<N; v++) if (!vis[v]) {
    DFS(v);
    ???                                         //handle results for connected component
  }
  ???                                           //get the answer in some way

It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A.
Let Ki denote number of sons of vertex i. Though each Ki may be as large as N-1, their sum is always equal to N-1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for i-th vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity.
To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N.
Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. 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 tree

The 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<nbr[v].size(); i++) {     //iterate through all sons s
      int s = nbr[v][i];                        
      if (!vis[s]) {                            //if vertex is not visited yet, then it's a son in DFS tree
        DFS(s);                                 //visit it recursively
        res[v] = DPInduction(res[v], res[s]);   //recalculate result for current vertex
      }
    }
  }
  ...
  memset(vis, false, sizeof(vis));              //mark all vertices as not visited
  DFS(0);                                       //run DFS from the root = vertex 0
  answer = DPAnswer(res[0]);                    //get problem answer from result of root

Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.

The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and a is additional info.
Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a].
Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
  bool vis[N];
  gres[N][A];
  intres[N+1][A];
  
  void DFS(int v) {
    vis[v] = true;
 
    vector<int> sons;
    for (int i = 0; i<nbr[v].size(); i++) {    //first pass: visit all sons and store their indices
      int s = nbr[v][i];
      if (!vis[s]) {
        DFS(s);
        sons.push_back(s);
      }
    }
 
    int SK = sons.size();                      //clear the internal results array
    for (int k = 0; k<=SK; k++)
      memset(intres[k], ?, sizeof(intres[k]));
 
    for (int a = 0; a<A; a++)                  //second pass: run internal DP over array of sons
      intres[0][a] = InternalDPBase(v, a);
    for (int k = 0; k<SK; k++)                 //k = number of sons considered so far
      for (int a = 0; a<A; a++)                //a = additional parameter for them
        for (int b = 0; b<A; b++) {            //b = additional parameter for the son being added
          int na = DPTransition(v, a, b);
          int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
          intres[k+1][na] = DPMerge(intres[k+1][na], nres);
        }
    for (int a = 0; a<A; a++)                  //copy answer of internal DP to result for vertex
      gres[v][a] = intres[SK][a];
  }
  ...
  memset(vis, false, sizeof(vis));              //series of DFS
  for (int v = 0; v<N; v++) if (!vis[v]) {
    DFS(v);
    ???                                         //handle results for connected component
  }
  ???                                           //get the answer in some way

It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A.
Let Ki denote number of sons of vertex i. Though each Ki may be as large as N-1, their sum is always equal to N-1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for i-th vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity.
To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N.
Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. 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 tree

The 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<nbr[v].size(); i++) {     //iterate through all sons s
      int s = nbr[v][i];                        
      if (!vis[s]) {                            //if vertex is not visited yet, then it's a son in DFS tree
        DFS(s);                                 //visit it recursively
        res[v] = DPInduction(res[v], res[s]);   //recalculate result for current vertex
      }
    }
  }
  ...
  memset(vis, false, sizeof(vis));              //mark all vertices as not visited
  DFS(0);                                       //run DFS from the root = vertex 0
  answer = DPAnswer(res[0]);                    //get problem answer from result of root

Sometimes the graph of problem is not connected (e.g. a forest). In this case run a series of DFS over the whole graph. The results for roots of individual trees are then combined in some way. Usually simple summation/maximum or a simple formula is enough but in tough cases this "merging problem" can turn out to require another DP solution.

The DPInduction is very simple in case when there are no additional parameters. But very often state domain includes the additional parameters and becomes complicated. DPInduction turns out to be another(internal) DP in this case. Its state domain is (k,a) where k is number of sons of vertex considered so far and a is additional info.
Be careful about the storage of results of this internal DP. If you are solving optimization problem and you are required to recover the solution (not only answer) then you have to save results of this DP for solution recovering. In this case you'll have an array globalres[v,a] and an array internalres[v,k,a].
Topcoder problems rarely require solution, so storage of internal DP results is not necessary. It is easier not to store them globally. In the code below internal results for a vertex are initialized after all the sons are traversed recursively and are discarded after DFS exits a vertex. This case is represented in the code below:
  bool vis[N];
  gres[N][A];
  intres[N+1][A];
  
  void DFS(int v) {
    vis[v] = true;
 
    vector<int> sons;
    for (int i = 0; i<nbr[v].size(); i++) {    //first pass: visit all sons and store their indices
      int s = nbr[v][i];
      if (!vis[s]) {
        DFS(s);
        sons.push_back(s);
      }
    }
 
    int SK = sons.size();                      //clear the internal results array
    for (int k = 0; k<=SK; k++)
      memset(intres[k], ?, sizeof(intres[k]));
 
    for (int a = 0; a<A; a++)                  //second pass: run internal DP over array of sons
      intres[0][a] = InternalDPBase(v, a);
    for (int k = 0; k<SK; k++)                 //k = number of sons considered so far
      for (int a = 0; a<A; a++)                //a = additional parameter for them
        for (int b = 0; b<A; b++) {            //b = additional parameter for the son being added
          int na = DPTransition(v, a, b);
          int nres = DPInduction(intres[k][a], gres[sons[k]][b]);
          intres[k+1][na] = DPMerge(intres[k+1][na], nres);
        }
    for (int a = 0; a<A; a++)                  //copy answer of internal DP to result for vertex
      gres[v][a] = intres[SK][a];
  }
  ...
  memset(vis, false, sizeof(vis));              //series of DFS
  for (int v = 0; v<N; v++) if (!vis[v]) {
    DFS(v);
    ???                                         //handle results for connected component
  }
  ???                                           //get the answer in some way

It is very important to understand how time/space complexity is calculated for DP over subtrees. For example, the code just above requires O(N*A^2) time. Though dumb analysis says it is O(N^2*A^2): {N vertices} x {SK<=N sons for each} x A x A.
Let Ki denote number of sons of vertex i. Though each Ki may be as large as N-1, their sum is always equal to N-1 in a rooted tree. This fact is the key to further analysis. Suppose that DFS code for i-th vertex runs in not more than Ki*t time. Since DFS is applied only once to each vertex, the overall time will be TC(N) = sum(Ki*t) <= N*t. Consider t=A^2 for the case above and you'll get O(N*A^2) time complexity.
To benefit from this acceleration, be sure not to iterate through all vertices of graph in DFS. For example above, running memset for the whole intres array in DFS will raise the time complexity. Time of individual DFS run will become O(N*A + Ki*A^2) instead of O(Ki*A^2). The overall time complexity will become O(N^2*A + N*A^2) which is great regress in case if A is much smaller that N.
Using the same approach you may achieve O(N*A) space complexity in case you are asked to recover solution. We have already said that to recover solution you have to store globally the array internalres[v,k,a]. If you allocate memory for this array dynamically, then you can ignore completely states with k>Ki. Since the sum of all Ki is N, you will get O(N*A) space.