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