{"id":1030,"date":"2020-04-19T21:00:17","date_gmt":"2020-04-20T04:00:17","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1030"},"modified":"2020-04-24T21:43:10","modified_gmt":"2020-04-25T04:43:10","slug":"state-compression-dp","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/04\/19\/state-compression-dp\/","title":{"rendered":"State Compression DP"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning.<\/p>\n\n\n\n

OJ<\/h2>\n\n\n\n\n\n\n\n\t\n\n\t\n\t\n\t\n\t\n\t
<\/td>Trick<\/th>Difficulty<\/th>\n<\/tr>\n<\/thead>\n
LC 1349. Maximum Students Taking Exam <\/a><\/td>DP State Compression + Bit Manipulation<\/td>6 points<\/td>\n<\/tr>\n
LC 691. Stickers to Spell Word<\/a><\/td>DP State Compression <\/td>6-7 points<\/td>\n<\/tr>\n
LC 1411. Number of Ways to Paint N \u00d7 3 Grid<\/a><\/td>DP State Compression or Direct DP <\/td>6 points<\/td>\n<\/tr>\n
LC 943. Find the Shortest Superstring<\/a><\/td>DP State Compression + TSP<\/td>7 points<\/td>\n<\/tr>\n
LC 1434. Number of Ways to Wear Different Hats to Each Other<\/a><\/td>DP Knapsack + State Compression<\/td>6-7 points<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n\n\n\n\n

Details<\/h2>\n\n\n\n

LC 1349. Maximum Students Taking Exam<\/a> <\/h4>\n\n\n\n

Difficulty: 6 points.<\/p>\n\n\n\n

We could use bit manipulation and state compression DP. For each row, when a slot has a student we consider the corresponding bit to be 1, so there are at most 2^n<\/code> states for each row. Some bit manipulation tricks are as following. <\/p>\n\n\n\n

\/\/ row curr does not contain adjacent students\n\/\/ row curr does not occupy '#'\n\/\/ forbidden[i] = 101101 for 'x.xx.x'\ninline bool ok(bitset<8> const &curr, int i) {\n    return (curr & (curr >> 1)) == 0 && (i >= 0 ? (forbidden[i] & curr) == 0 : true);\n}\n\n\/\/ row curr and row prev does not contain diagonal students\ninline bool ok(bitset<8> const &curr, bitset<8> const &prev) {\n    return ((curr >> 1) & prev) == 0 && ((curr << 1) & prev) == 0;\n}<\/code><\/pre>\n\n\n\n
Then the DP state transformation is not difficult.  <\/p>\n\n\n\n
alg[i][prev] = \n   max {curr.count() + alg[i + 1][curr] if ok(curr, prev) && ok(curr, i) && ok(prev, i - 1) for curr in [0, (1 << n) - 1]}<\/code><\/pre>\n\n\n\n
Note that for the DP table related to previous state, we need to find answer by adding at least one state. However, here we know alg[0][0]<\/code> will work since the first row won’t have conflicts with previous state 0<\/code>.<\/p>\n\n\n\n
LC 1411. Number of Ways to Paint N \u00d7 3 Grid<\/a> <\/h4>\n\n\n\n
Difficulty: 6 points.<\/p>\n\n\n\n
This problem can be solved efficiently in log(n)<\/code> time, which is introduced in this post<\/a>. It is nice to mention as a follow up solution. <\/p>\n\n\n\n
The common answer will be State Compression for this kind of problem. The grid is of length 3, which means a grid has 27 states. We use a base 3 number integer to represent states, though we need to explicitly parse the physical meaning out of the integer (no base 2 tricks here).<\/p>\n\n\n\n
alg[i][prev] = sum { alg[i + 1][curr] if ok(curr, prev) && ok(prev) && ok(curr) for curr in [0, 27]<\/code><\/pre>\n\n\n\n
Note that for the DP table related to previous state, we need to find answer by adding at least one state.<\/p>\n\n\n\n
ll result = 0;\nfor (int prev = 0; prev < 27; ++prev) {\n    result += alg[1][prev];\n    result %= MOD;\n}\nreturn result;<\/code><\/pre>\n\n\n\n
LC 943. Find the Shortest Superstring<\/a><\/h4>\n\n\n\n
Difficulty: 7 points.<\/p>\n\n\n\n
The problem is hard, since it is hard to detect it is actually a TSP problem.<\/p>\n\n\n\n
Think in this way. Given a permutation of strings, if between two adjacent strings there are overlaps, we could leverage them and shorten the total length. For example, \"catg\" + \"atgcatc\"<\/code> can be \"c\" + \"atg\" + \"catc\"<\/code>. We want to maximize the overlaps. In the other way, if we think the non-overlapping chars as the cost to stick the current word to the previous one. The problem becomes find out a permutation with lowest cost, which is a TSP problem. <\/p>\n\n\n\n
Regarding the TSP problem, for any permutation, the cost starting from index j is determined by the visited indexes and the previous index i.  Visited indexes could use the State Compression technique.  <\/p>\n\n\n\n
The problem also needs to output a path. So we uses another table to store our best choices at each state. <\/p>\n\n\n\n
alg[visited][prev] = \n  min {alg[visited | 1 << j][j] + dist[prev][j] if ((1 << j) & visited == 0 && (1 << prev) & visited > 0) for j in [0, n - 1]}\n\nchoices[visited][prev] = \n  argmin {alg[visited | 1 << j][j] + dist[prev][j] if ((1 << j) & visited == 0 && (1 << prev) & visited > 0) for j in [0, n - 1]}<\/code><\/pre>\n\n\n\n
Note that for the DP table related to previous state, we need to find answer by adding at least one state.<\/p>\n\n\n\n
int min_ = INT_MAX;\nint curr = -1;\nfor (int i = 0; i < n; ++i) {\n    if (alg[1 << i][i] + A[i].size() < min_) {\n        min_ = alg[1 << i][i] + A[i].size();\n        curr = i;\n    }\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Summary State compression is a common technique in some DP problems when number of states are limited and each state consists of bits, where each bit has specific physical meaning. OJ Details LC 1349. Maximum Students Taking Exam Difficulty: 6 points. We could use bit manipulation and state compression DP. For each row, when a…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,61],"tags":[],"class_list":["post-1030","post","type-post","status-publish","format-standard","hentry","category-alg","category-dp-state-compression"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1030","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1030"}],"version-history":[{"count":10,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1030\/revisions"}],"predecessor-version":[{"id":1058,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1030\/revisions\/1058"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1030"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1030"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1030"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}