{"id":6867,"date":"2020-06-03T22:18:59","date_gmt":"2020-06-04T05:18:59","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6867"},"modified":"2020-06-04T23:15:54","modified_gmt":"2020-06-05T06:15:54","slug":"leetcode-1467-probability-of-a-two-boxes-having-the-same-number-of-distinct-balls","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/searching\/leetcode-1467-probability-of-a-two-boxes-having-the-same-number-of-distinct-balls\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1467. Probability of a Two Boxes Having The Same Number of Distinct Balls - \u5237\u9898\u627e\u5de5\u4f5c EP332\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/EZS6E6swOsY?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>Given&nbsp;<code>2n<\/code>&nbsp;balls of&nbsp;<code>k<\/code>&nbsp;distinct colors. You will be given an integer array&nbsp;<code>balls<\/code>&nbsp;of size&nbsp;<code>k<\/code>&nbsp;where&nbsp;<code>balls[i]<\/code>&nbsp;is the number of balls of color&nbsp;<code>i<\/code>.&nbsp;<\/p>\n\n\n\n<p>All the balls will be&nbsp;<strong>shuffled uniformly at random<\/strong>,&nbsp;then we will distribute the first&nbsp;<code>n<\/code>&nbsp;balls to the first box and the remaining&nbsp;<code>n<\/code>&nbsp;balls to the other box (Please read the explanation of the second example carefully).<\/p>\n\n\n\n<p>Please note that the two boxes are considered different. For example, if we have two balls of colors&nbsp;<code>a<\/code>&nbsp;and&nbsp;<code>b<\/code>, and two boxes&nbsp;<code>[]<\/code>&nbsp;and&nbsp;<code>()<\/code>, then the distribution&nbsp;<code>[a] (b)<\/code>&nbsp;is considered different than the distribution&nbsp;<code>[b] (a)&nbsp;<\/code>(Please read the explanation of the first&nbsp;example carefully).<\/p>\n\n\n\n<p>We want to&nbsp;<em>calculate the probability<\/em>&nbsp;that the two boxes have the same number of distinct balls.<\/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> balls = [1,1]\n<strong>Output:<\/strong> 1.00000\n<strong>Explanation:<\/strong> Only 2 ways to divide the balls equally:\n- A ball of color 1 to box 1 and a ball of color 2 to box 2\n- A ball of color 2 to box 1 and a ball of color 1 to box 2\nIn both ways, the number of distinct colors in each box is equal. The probability is 2\/2 = 1\n<\/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> balls = [2,1,1]\n<strong>Output:<\/strong> 0.66667\n<strong>Explanation:<\/strong> We have the set of balls [1, 1, 2, 3]\nThis set of balls will be shuffled randomly and we may have one of the 12 distinct shuffles with equale probability (i.e. 1\/12):\n[1,1 \/ 2,3], [1,1 \/ 3,2], [1,2 \/ 1,3], [1,2 \/ 3,1], [1,3 \/ 1,2], [1,3 \/ 2,1], [2,1 \/ 1,3], [2,1 \/ 3,1], [2,3 \/ 1,1], [3,1 \/ 1,2], [3,1 \/ 2,1], [3,2 \/ 1,1]\nAfter that we add the first two balls to the first box and the second two balls to the second box.\nWe can see that 8 of these 12 possible random distributions have the same number of distinct colors of balls in each box.\nProbability is 8\/12 = 0.66667\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> balls = [1,2,1,2]\n<strong>Output:<\/strong> 0.60000\n<strong>Explanation:<\/strong> The set of balls is [1, 2, 2, 3, 4, 4]. It is hard to display all the 180 possible random shuffles of this set but it is easy to check that 108 of them will have the same number of distinct colors in each box.\nProbability = 108 \/ 180 = 0.6\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> balls = [3,2,1]\n<strong>Output:<\/strong> 0.30000\n<strong>Explanation:<\/strong> The set of balls is [1, 1, 1, 2, 2, 3]. It is hard to display all the 60 possible random shuffles of this set but it is easy to check that 18 of them will have the same number of distinct colors in each box.\nProbability = 18 \/ 60 = 0.3\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> balls = [6,6,6,6,6,6]\n<strong>Output:<\/strong> 0.90327\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= balls.length &lt;= 8<\/code><\/li><li><code>1 &lt;= balls[i] &lt;= 6<\/code><\/li><li><code>sum(balls)<\/code>&nbsp;is even.<\/li><li>Answers within&nbsp;<code>10^-5<\/code>&nbsp;of the actual value will be accepted as correct.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 0: Permutation<\/strong> (<strong>TLE<\/strong>)<\/h2>\n\n\n\n<p>Enumerate all permutations of the balls, count valid ones and divide that by the total.<\/p>\n\n\n\n<p>Time complexity: O((8*6)!) = O(48!) <br>After deduplication: O(48!\/(6!)^8) ~ 1.7e38<br>Space complexity: O(8*6)<\/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, TLE 4\/21 passed\nclass Solution {\npublic:\n  double getProbability(vector<int>& balls) {\n    const int k = balls.size();\n    vector<int> bs;\n    for (int i = 0; i < k; ++i)\n      for (int j = 0; j < balls[i]; ++j)\n        bs.push_back(i);\n    const int n = bs.size();\n    double total = 0.0;\n    double valid = 0.0;\n    \/\/ d : depth\n    \/\/ used : bitmap of bs's usage\n    \/\/ c1: bitmap of colors of box1\n    \/\/ c2: bitmap of colors of box1\n    function<void(int, long, int, int)> dfs = [&](int d, long used, int c1, int c2) {    \n      if (d == n) {          \n        total += 1;\n        valid += __builtin_popcount(c1) == __builtin_popcount(c2);                \n        return;\n      }\n      for (int i = 0; i < n; ++i) {\n        if (used &#038; (1L << i)) continue;\n        \/\/ Deduplication.\n        if (i > 0 && bs[i] == bs[i - 1] && !(used & (1L << (i - 1)))) continue;        \n        int tc1 = (d < n \/ 2) ? (c1 | (1 << bs[i])) : c1;\n        int tc2 = (d < n \/ 2) ? c2 : (c2 | (1 << bs[i]));\n        dfs(d + 1, used | (1L << i), tc1, tc2);\n      }\n    };\n    dfs(0, 0, 0, 0);    \n    return valid \/ total;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Combination<\/strong><\/h2>\n\n\n\n<p>For each color, put n_i balls into box1, the left t_i - n_i balls go to box2.<br>permutations = fact(n\/\/2) \/ PROD(fact(n_i)) * fact(n\/\/2) * PROD(fact(t_i - n_i))<br>E.g<br>balls = [1x2, 2x6, 3x4]<br>One possible combination:<br>box1: 1 22 333<br>box2: 1 2222 3<br>permutations = 6! \/ (1! * 2! * 3!) * 6! \/ (1! * 4! * 1!) = 1800<\/p>\n\n\n\n<p>Time complexity: O((t+1)^k) = O(7^8)<br>Space complexity: O(k + (t*k)) = O(8 + 48)<\/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  double getProbability(vector<int>& balls) {\n    const int n = accumulate(begin(balls), end(balls), 0);\n    const int k = balls.size();        \n    double total = 0.0;\n    double valid = 0.0;\n    vector<double> fact(50, 1.0);\n    for (int i = 1; i < fact.size(); ++i)\n      fact[i] = fact[i - 1] * i;\n    \/\/ d: depth\n    \/\/ b1, b2: # of balls in box1, box2\n    \/\/ c1, c2: # of distinct colors in box1, box2\n    \/\/ p1, p2: # permutations of duplicate balls in box1, box2\n    function<void(int, int, int, int, int, double, double)> dfs = [&]\n      (int d, int b1, int b2, int c1, int c2, double p1, double p2) {\n      if (b1 > n \/ 2 || b2 > n \/ 2) return;\n      if (d == k) {\n        const double count = fact[b1] \/ p1 * fact[b2] \/ p2;\n        total += count;\n        valid += count * (c1 == c2);\n        return;\n      }\n      for (int s1 = 0; s1 <= balls[d]; ++s1) {\n        const int s2 = balls[d] - s1;\n        dfs(d + 1,\n            b1 + s1, \n            b2 + s2,\n            c1 + (s1 > 0), \n            c2 + (s2 > 0), \n            p1 * fact[s1], \n            p2 * fact[s2]);\n      }\n    };\n    dfs(0, 0, 0, 0, 0, 1.0, 1.0);\n    return valid \/ total;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>vector version<\/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  double getProbability(vector<int>& balls) {\n    const int k = balls.size();                    \n    const int n = accumulate(begin(balls), end(balls), 0);\n    vector<double> fact(49, 1.0);\n    for (int i = 1; i < fact.size(); ++i)\n      fact[i] = fact[i - 1] * i;\n    auto perms = [&#038;](const vector<int>& bs, int n) -> double {\n      double p = fact[n];\n      for (int b : bs) p \/= fact[b];        \n      return p;\n    };\n    vector<int> box1, box2;\n    function<double(int)> dfs = [&](int d) -> double {\n      const int n1 = accumulate(begin(box1), end(box1), 0);\n      const int n2 = accumulate(begin(box2), end(box2), 0);\n      if (n1 > n \/ 2 || n2 > n \/ 2) return 0;\n      if (d == k)\n        return (box1.size() == box2.size()) * perms(box1, n1) * perms(box2, n2);\n      double total = 0;\n      for (int s1 = 0; s1 <= balls[d]; ++s1) {\n        const int s2 = balls[d] - s1;\n        if (s1) box1.push_back(s1);\n        if (s2) box2.push_back(s2);\n        total += dfs(d + 1);\n        if (s1) box1.pop_back();\n        if (s2) box2.pop_back();\n      }\n      return total;\n    };\n    return dfs(0) \/ perms(balls, n);\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given&nbsp;2n&nbsp;balls of&nbsp;k&nbsp;distinct colors. You will be given an integer array&nbsp;balls&nbsp;of size&nbsp;k&nbsp;where&nbsp;balls[i]&nbsp;is the number of balls of color&nbsp;i.&nbsp; All the balls will be&nbsp;shuffled uniformly at random,&nbsp;then&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[44],"tags":[122,33,18,217,121,120,42],"class_list":["post-6867","post","type-post","status-publish","format-standard","hentry","category-searching","tag-combination","tag-dfs","tag-dp","tag-hard","tag-permutation","tag-probability","tag-search","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6867","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=6867"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6867\/revisions"}],"predecessor-version":[{"id":6879,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6867\/revisions\/6879"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6867"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6867"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6867"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}