{"id":7777,"date":"2020-12-06T19:35:28","date_gmt":"2020-12-07T03:35:28","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7777"},"modified":"2020-12-06T21:26:21","modified_gmt":"2020-12-07T05:26:21","slug":"leetcode-1681-minimum-incompatibility","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/dynamic-programming\/leetcode-1681-minimum-incompatibility\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1681. Minimum Incompatibility"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1681. Minimum Incompatibility - \u5237\u9898\u627e\u5de5\u4f5c EP374\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/03KwgvDgxKg?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<p>You are given an integer array&nbsp;<code>nums<\/code>\u200b\u200b\u200b and an integer&nbsp;<code>k<\/code>. You are asked to distribute this array into&nbsp;<code>k<\/code>&nbsp;subsets of&nbsp;<strong>equal size<\/strong>&nbsp;such that there are no two equal elements in the same subset.<\/p>\n\n\n\n<p>A subset&#8217;s&nbsp;<strong>incompatibility<\/strong>&nbsp;is the difference between the maximum and minimum elements in that array.<\/p>\n\n\n\n<p>Return&nbsp;<em>the&nbsp;<strong>minimum possible sum of incompatibilities<\/strong>&nbsp;of the&nbsp;<\/em><code>k<\/code>&nbsp;<em>subsets after distributing the array optimally, or return&nbsp;<\/em><code>-1<\/code><em>&nbsp;if it is not possible.<\/em><\/p>\n\n\n\n<p>A subset is a group integers that appear in the array with no particular order.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [1,2,1,4], k = 2\n<strong>Output:<\/strong> 4\n<strong>Explanation:<\/strong> The optimal distribution of subsets is [1,2] and [1,4].\nThe incompatibility is (2-1) + (4-1) = 4.\nNote that [1,1] and [2,4] would result in a smaller sum, but the first subset contains 2 equal elements.<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [6,3,8,1,3,1,2,2], k = 4\n<strong>Output:<\/strong> 6\n<strong>Explanation:<\/strong> The optimal distribution of subsets is [1,2], [2,3], [6,8], and [1,3].\nThe incompatibility is (2-1) + (3-2) + (8-6) + (3-1) = 6.\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> nums = [5,3,3,6,3,3], k = 3\n<strong>Output:<\/strong> -1\n<strong>Explanation:<\/strong> It is impossible to distribute nums into 3 subsets where no two elements are equal in the same subset.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= k &lt;= nums.length &lt;= 16<\/code><\/li><li><code>nums.length<\/code>&nbsp;is divisible by&nbsp;<code>k<\/code><\/li><li><code>1 &lt;= nums[i] &lt;= nums.length<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: TSP<\/strong><\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-1.png\" alt=\"\" class=\"wp-image-7781\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-1-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"960\" height=\"540\" src=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-2.png\" alt=\"\" class=\"wp-image-7782\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2020\/12\/1681-ep374-2-768x432.png 768w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/figure>\n\n\n\n<p>dp[s][i] := min cost to distribute a set of numbers represented as a binary mask s, the last number in the set is the i-th number.<\/p>\n\n\n\n<p>Init: <br>1.dp[*][*] = inf <br>2. dp[1 &lt;&lt;i][i] = 0, cost of selecting a single number is zero.<br><br>Transition: <br>1. dp[s | (1 &lt;&lt; j)][j] = dp[s][i] if s % (n \/ k) == 0, we start a new group, no extra cost.<br>2. dp[s | (1 &lt;&lt; j)][j] = dp[s][i] + nums[j] &#8211; nums[i] if nums[j] &gt; nums[i]. In the same group, we require the selected numbers are monotonically increasing. Each cost is nums[j] &#8211; nums[i].<br>e.g. 1, 3, 7, 20, cost is (3 &#8211; 1) + (7 &#8211; 3) + (20 &#8211; 7) = 20 &#8211; 1 = 19.<\/p>\n\n\n\n<p>Ans: min(dp[(1 &lt;&lt; n) &#8211; 1])<\/p>\n\n\n\n<p>Time complexity: O(2^n * n^2)<br>Space complexity: O(2^n * n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumIncompatibility(vector<int>& nums, int k) {\n    const int n = nums.size(); \n    const int c = n \/ k;\n    int dp[1 << 16][16];\n    memset(dp, 0x7f, sizeof(dp));\n    for (int i = 0; i < n; ++i) dp[1 << i][i] = 0;\n    for (int s = 0; s < 1 << n; ++s)\n      for (int i = 0; i < n; ++i) {\n        if ((s &#038; (1 << i)) == 0) continue;\n        for (int j = 0; j < n; ++j) {\n          if ((s &#038; (1 << j))) continue;\n          const int t = s | (1 << j);\n          if (__builtin_popcount(s) % c == 0) {\n            dp[t][j] = min(dp[t][j], dp[s][i]);\n          } else if (nums[j] > nums[i]) {           \n            dp[t][j] = min(dp[t][j], \n                           dp[s][i] + nums[j] - nums[i]);            \n          }\n        }        \n    }\n    int ans = *min_element(begin(dp[(1 << n) - 1]), \n                           end(dp[(1 << n) - 1]));\n    return ans > 1e9 ? - 1 : ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given an integer array&nbsp;nums\u200b\u200b\u200b and an integer&nbsp;k. You are asked to distribute this array into&nbsp;k&nbsp;subsets of&nbsp;equal size&nbsp;such that there are no two equal&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[46],"tags":[621,18,217,435],"class_list":["post-7777","post","type-post","status-publish","format-standard","hentry","category-dynamic-programming","tag-bitmask","tag-dp","tag-hard","tag-tsp","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7777","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7777"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7777\/revisions"}],"predecessor-version":[{"id":7784,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7777\/revisions\/7784"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7777"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7777"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7777"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}