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 (1 edit)
Re: 2.4.? Commonly used DP state domains (response to post by syg96)
Examples:


InformFriends

We 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<<n); i++) {                     //for all subsets i
    int mask = 0;
    for (j = 0; j<n; j++) if (i&(1<<j)) {          //iterate through people in it
      mask |= (1<<j);
      for (u = 0; u<n; u++) if (matr[j][u]=='Y')   //accumulate the total set of informed people
        mask |= (1<<u);
    }
    cover[i] = (mask == (1<<n)-1);                 //if everyone is informed, the subset if fact-group
  }
 
  int ans = 0;
  for (i = 0; i<(1<<n); i++) {                     //go through states
    res[i] = 0;
    for (j = i; j>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)
Examples:


InformFriends

We 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<<n); i++) {                     //for all subsets i
    int mask = 0;
    for (j = 0; j<n; j++) if (i&(1<<j)) {          //iterate through people in it
      mask |= (1<<j);
      for (u = 0; u<n; u++) if (matr[j][u]=='Y')   //accumulate the total set of informed people
        mask |= (1<<u);
    }
    cover[i] = (mask == (1<<n)-1);                 //if everyone is informed, the subset if fact-group
  }
 
  int ans = 0;
  for (i = 0; i<(1<<n); i++) {                     //go through states
    res[i] = 0;
    for (j = i; j>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];