{"id":8574,"date":"2021-08-11T21:21:46","date_gmt":"2021-08-12T04:21:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8574"},"modified":"2021-08-11T21:24:05","modified_gmt":"2021-08-12T04:24:05","slug":"leetcode-1900-the-earliest-and-latest-rounds-where-players-compete","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/recursion\/leetcode-1900-the-earliest-and-latest-rounds-where-players-compete\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1900. The Earliest and Latest Rounds Where Players Compete"},"content":{"rendered":"\n<p>There is a tournament where&nbsp;<code>n<\/code>&nbsp;players are participating. The players are standing in a single row and are numbered from&nbsp;<code>1<\/code>&nbsp;to&nbsp;<code>n<\/code>&nbsp;based on their&nbsp;<strong>initial<\/strong>&nbsp;standing position (player&nbsp;<code>1<\/code>&nbsp;is the first player in the row, player&nbsp;<code>2<\/code>&nbsp;is the second player in the row, etc.).<\/p>\n\n\n\n<p>The tournament consists of multiple rounds (starting from round number&nbsp;<code>1<\/code>). In each round, the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;player from the front of the row competes against the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;player from the end of the row, and the winner advances to the next round. When the number of players is odd for the current round, the player in the middle automatically advances to the next round.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>For example, if the row consists of players&nbsp;<code>1, 2, 4, 6, 7<\/code><ul><li>Player&nbsp;<code>1<\/code>&nbsp;competes against player&nbsp;<code>7<\/code>.<\/li><li>Player&nbsp;<code>2<\/code>&nbsp;competes against player&nbsp;<code>6<\/code>.<\/li><li>Player&nbsp;<code>4<\/code>&nbsp;automatically advances to the next round.<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>After each round is over, the winners are lined back up in the row based on the&nbsp;<strong>original ordering<\/strong>&nbsp;assigned to them initially (ascending order).<\/p>\n\n\n\n<p>The players numbered&nbsp;<code>firstPlayer<\/code>&nbsp;and&nbsp;<code>secondPlayer<\/code>&nbsp;are the best in the tournament. They can win against any other player before they compete against each other. If any two other players compete against each other, either of them might win, and thus you may&nbsp;<strong>choose<\/strong>&nbsp;the outcome of this round.<\/p>\n\n\n\n<p>Given the integers&nbsp;<code>n<\/code>,&nbsp;<code>firstPlayer<\/code>, and&nbsp;<code>secondPlayer<\/code>, return&nbsp;<em>an integer array containing two values, the&nbsp;<strong>earliest<\/strong>&nbsp;possible round number and the&nbsp;<strong>latest<\/strong>&nbsp;possible round number in which these two players will compete against each other, respectively<\/em>.<\/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> n = 11, firstPlayer = 2, secondPlayer = 4\n<strong>Output:<\/strong> [3,4]\n<strong>Explanation:<\/strong>\nOne possible scenario which leads to the earliest round number:\nFirst round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\nSecond round: 2, 3, 4, 5, 6, 11\nThird round: 2, 3, 4\nOne possible scenario which leads to the latest round number:\nFirst round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\nSecond round: 1, 2, 3, 4, 5, 6\nThird round: 1, 2, 4\nFourth round: 2, 4\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> n = 5, firstPlayer = 1, secondPlayer = 5\n<strong>Output:<\/strong> [1,1]\n<strong>Explanation:<\/strong> The players numbered 1 and 5 compete in the first round.\nThere is no way to make them compete in any other round.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>2 &lt;= n &lt;= 28<\/code><\/li><li><code>1 &lt;= firstPlayer &lt; secondPlayer &lt;= n<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution 1: Simulation using recursion<\/strong><\/h2>\n\n\n\n<p>All possible paths, <br>Time complexity: O(n<sup>2<\/sup>*2<sup>n<\/sup>)<br>Space complexity: O(logn)<\/p>\n\n\n\n<p>dfs(s, i, j, d) := let i battle with j at round d, given s (binary mask of dead players).<\/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  vector<int> earliestAndLatest(int n, int a, int b) {\n    vector<int> ans{INT_MAX, INT_MIN};    \n    function<void(int, int, int, int)> dfs = [&](int s, int i, int j, int d) {\n      while (i < j &#038;&#038; s >> i & 1) ++i;\n      while (i < j &#038;&#038; s >> j & 1) --j;\n      if (i >= j) {\n        return dfs(s, 1, n, d + 1);\n      } else if (i == a && j == b) {\n        ans[0] = min(ans[0], d);\n        ans[1] = max(ans[1], d);\n      } else {\n        if (i != a && i != b)\n          dfs(s | (1 << i), i + 1, j - 1, d);\n        if (j != a &#038;&#038; j != b)\n          dfs(s | (1 << j), i + 1, j - 1, d);\n      }\n    };\n    dfs(0, 1, n, 1);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>There is a tournament where&nbsp;n&nbsp;players are participating. The players are standing in a single row and are numbered from&nbsp;1&nbsp;to&nbsp;n&nbsp;based on their&nbsp;initial&nbsp;standing position (player&nbsp;1&nbsp;is the first&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[153],"tags":[621,217,17,179],"class_list":["post-8574","post","type-post","status-publish","format-standard","hentry","category-recursion","tag-bitmask","tag-hard","tag-recursion","tag-simulation","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8574","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=8574"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8574\/revisions"}],"predecessor-version":[{"id":8577,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8574\/revisions\/8577"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8574"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8574"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8574"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}