JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
[ 1 2 ]    NEXT >
2.4.? Commonly used DP state domains | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
BlockEnemy

Since 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=safe
2. v=dangerous + s=safe -> v=dangerous
3. v=safe + s=dangerous -> v=dangerous
4. v=dangerous + s=dangerous -> incorrect solution
After 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<n; s++) if (matr[v][s] < 1000000000) {
    if (vis[s]) continue;                           //iterate over all sons
    DFS(s, v);                                      //run DFS recursively
    
    int nres[2];                                
    nres[0] = res[v][0] + res[s][0];                //safe case requires safe s and safe v
    nres[1] = min(res[v][0] + res[s][1], res[v][1] + res[s][0]);
    res[v][0] = nres[0];                            //dangerous case requires dangerous + safe
    res[v][1] = nres[1];
  }
  if (f >= 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
}
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
ConstructionFromMatches

We need to construct grid from matches obeying certain rules which have local effect. And the grid is 2 x n which is ideal for DP with profiles. Of course, it is better to slice the grid to 2-cell layers instead of N-cell ones. The profile consists of thicknesses of the last two vertical sticks. They are required to check sum when filling the next layer. To perform the transition, we have to iterate through all possible variants of next five sticks thicknesses and choose only variants that satisfy two equations on cell sums. If we perform it bruteforce, we will get O(N*K^7) algorithm, that's slow. It can be easily optimized if we calculate thicknesses of two sticks explicitly by using cell sum equations. This way the DP will be O(N*K^5) in time and O(N*K^2) in space. That is more than enough for the problem.
If you want a better solution, you can notice that:
1. You can use "storing two layers" optimization and reduce space complexity to O(K^2).
2. You can transform the solution to DP with broken profiles. To do it you should add intermediate "half" states (i,p,b,v). hres[i][p][b][v] means minimal cost of full construction of (2*i+1) cells - i layers and a top cell in the next layer. The DP with broken profiles will require O(N*K^4) time and O(N*K^3) space, which can be reduced with technique 1 to O(K^3).
The code for simple solution is given below. Since width of profile is well-known and very small, it is easier to write transition code as nested loops instead of recursive search.
//...?? aa      //schema of profile and transition
//...  u  p     //u and v comprise profile
//...  u  p     //a, b, c, p, q are five added sticks
//...?? bb      //system of equations is:
//...  v  q     //{u + a + p + b = top[i]
//...  v  q     //{v + b + q + c = bottom[i]
//...?? cc      //the depicted transition leads to (i+1,p,q) state
 
  memset(res, 63, sizeof(res));                    //DP base
  for (int u = 0; u<k; u++)                        //choose any two sticks
    for (int v = 0; v<k; v++)                      //put them to leftmost vertical line
      res[0][u][v] = cost[u] + cost[v];            //their cost is clear
 
  for (int i = 0; i<n; i++)
    for (int u = 0; u<k; u++)
      for (int v = 0; v<k; v++) {                  //iterate through states
        int cres = res[i][u][v];
        for (int a = 0; a<k; a++)                  //choose a and p in all possible ways
          for (int p = 0; p<k; p++) {
            int b = top[i]-4 - (u + a + p);        //b is uniquely determined by top equation
            if (b < 0 || b >= k) continue;         //though it can be bad...
            for (int q = 0; q<k; q++) {            //choose all possible q variants
              int c = bottom[i]-4 - (v + b + q);   //c is uniquely determined by bottom equation
              if (c < 0 || c >= k) continue;
 
              int nres = cres + cost[p] + cost[q]  //the new solution cost
                    + cost[a] + cost[b] + cost[c];
              if (res[i+1][p][q] > nres)           //relaxing the destination
                res[i+1][p][q] = nres;
            }
          }
      }
 
  int answer = 1000000000;                         //the last two sticks do not matter
  for (int u = 0; u<k; u++)                        //choose the best variant among them
    for (int v = 0; v<k; v++)
      if (answer > res[n][u][v])
        answer = res[n][u][v];
  if (answer >= 1000000000) answer = -1;           //do not forget "impossible" case
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
This recipe is great, in my opinion, considering there's a few interesting tutorials about dp in the web (not just knapsack and LCS but with some more content) if any. Sought for one some time ago (especially wanted to read about dp over subsets) and now I have a chance to read it. I mean it's good not only for Cookbook but for me so thank you very much.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
Thank you! This is the most useful recipe I have read so far. Perhaps it will finally help me to understand DP and move to yellow...
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For the multidimensional array, I don't understand what does Result[i1][i2][i3]...[ik] represent in terms of the Knapsack problem? Does it mean the maximum cost that we can obtain by using i1 number of items 1, i2 number of items2, ..., ik number of k-th item? If so, then it is no longer 0-1 Knapsack, but more like unbounded Knapsack. By the way, it will be great if you can use the Knapsack example for all the representation types.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For the subsets of a given set you should mention that M[x,y] is the distance between cities x and y. You should use M in the code (instead of matr). You should explain the reasoning behind R[X,a]+M[a,0]: R[x,a] is the shortest path that visits every node once starting from node 0, so R[X,a]+M[a,0] is the shortest Hamilton cycle for X.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
For substrings of a given string. Can you avoid using 'l' in the code, because it looks too similar to one. You can use L and R instead. What is "tres=?;"? What is a in this case and is it actually used in the code?
Re: 2.4.? Commonly used DP state domains (response to post by dimkadimon) | Reply
1. The Result[i1,i2,...,ik] has nothing is common with knapsack. It is array of results for general problem with multidim-like state domain. Knapsack was an example of such a problem with dim=2.

2. I added explanation for M matrix and about the way answer is got. About M and matr - it is usual thing. Mathematics is used to short variable names (1-2 letters) whereas in programming short names is bad habbit. I have a strong feeling against naming a matrix with one letter, sorry=) By the way, didn't you notice that state result is denoted as R in text but as res in code?...

3. Changed l,m,r to L,M,R. (l+1) looks really weird=) Question mark represents something that depends on the problem. It is usually neutral element i.e. 0 in combinatoric problem, +inf in minimization problem, -inf in maximization problem. I don't want to explain it here and there may be exceptions. That's why I just put question mark. Look one of examples and you'll see 10^18 in this place.

a represents additional parameters. It must be explained somewhere in the recipe=) I added a note on this to the first place it is met.

I don't like that additional parameters are represented by letter "a". Because it is english article also... I've enclosed parameter "a" in quotes in most places in text so that the do not confuse reader.
Re: 2.4.? Commonly used DP state domains (response to post by syg96) | Reply
This is a great post! Thanks for sharing it and congrats you are a smart guy!
[ 1 2 ]    NEXT >

RSS