the-earliest-and-latest-rounds-where-players-compete

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

There is a tournament where <code>n</code> players are participating. The players are standing in a single row and are numbered from <code>1</code> to <code>n</code> based on their initial standing position (player <code>1</code> is the first player in the row, player <code>2</code> is the second player in the row, etc.).

The tournament consists of multiple rounds (starting from round number <code>1</code>). In each round, the <code>ith</code> player from the front of the row competes against the <code>ith</code> 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.

<ul>
	<li>For example, if the row consists of players <code>1, 2, 4, 6, 7</code>

	<ul>
		<li>Player <code>1</code> competes against player <code>7</code>.</li>
		<li>Player <code>2</code> competes against player <code>6</code>.</li>
		<li>Player <code>4</code> automatically advances to the next round.</li>
	</ul>
	</li>
</ul>

After each round is over, the winners are lined back up in the row based on the original ordering assigned to them initially (ascending order).

The players numbered <code>firstPlayer</code> and <code>secondPlayer</code> 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 choose the outcome of this round.

Given the integers <code>n</code>, <code>firstPlayer</code>, and <code>secondPlayer</code>, return an integer array containing two values, the earliest possible round number and the&nbsp;latest possible round number in which these two players will compete against each other, respectively.

&nbsp;
Example 1:

<pre>
Input: n = 11, firstPlayer = 2, secondPlayer = 4
Output: [3,4]
Explanation:
One possible scenario which leads to the earliest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 2, 3, 4, 5, 6, 11
Third round: 2, 3, 4
One possible scenario which leads to the latest round number:
First round: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
Second round: 1, 2, 3, 4, 5, 6
Third round: 1, 2, 4
Fourth round: 2, 4
</pre>

Example 2:

<pre>
Input: n = 5, firstPlayer = 1, secondPlayer = 5
Output: [1,1]
Explanation: The players numbered 1 and 5 compete in the first round.
There is no way to make them compete in any other round.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>2 &lt;= n &lt;= 28</code></li>
	<li><code>1 &lt;= firstPlayer &lt; secondPlayer &lt;= n</code></li>
</ul>

earliestAndLatest

The Earliest and Latest Rounds Where Players Compete

Memoization

Dynamic Programming

<code>n</code> 名运动员参与一场锦标赛，所有运动员站成一排，并根据 最开始的 站位从 <code>1</code> 到 <code>n</code> 编号（运动员 <code>1</code> 是这一排中的第一个运动员，运动员 <code>2</code> 是第二个运动员，依此类推）。

锦标赛由多个回合组成（从回合 <code>1</code> 开始）。每一回合中，这一排从前往后数的第 <code>i</code> 名运动员需要与从后往前数的第 <code>i</code> 名运动员比拼，获胜者将会进入下一回合。如果当前回合中运动员数目为奇数，那么中间那位运动员将轮空晋级下一回合。

<ul>
	<li>例如，当前回合中，运动员 <code>1, 2, 4, 6, 7</code> 站成一排

	<ul>
		<li>运动员 <code>1</code> 需要和运动员 <code>7</code> 比拼</li>
		<li>运动员 <code>2</code> 需要和运动员 <code>6</code> 比拼</li>
		<li>运动员 <code>4</code> 轮空晋级下一回合</li>
	</ul>
	</li>
</ul>

每回合结束后，获胜者将会基于最开始分配给他们的原始顺序（升序）重新排成一排。

编号为 <code>firstPlayer</code> 和 <code>secondPlayer</code> 的运动员是本场锦标赛中的最佳运动员。在他们开始比拼之前，完全可以战胜任何其他运动员。而任意两个其他运动员进行比拼时，其中任意一个都有获胜的可能，因此你可以 裁定 谁是这一回合的获胜者。

给你三个整数 <code>n</code>、<code>firstPlayer</code> 和 <code>secondPlayer</code> 。返回一个由两个值组成的整数数组，分别表示两位最佳运动员在本场锦标赛中比拼的 最早 回合数和 最晚 回合数。

 

示例 1：

<pre>输入：n = 11, firstPlayer = 2, secondPlayer = 4
输出：[3,4]
解释：
一种能够产生最早回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：2, 3, 4, 5, 6, 11
回合 3：2, 3, 4
一种能够产生最晚回合数的情景是：
回合 1：1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
回合 2：1, 2, 3, 4, 5, 6
回合 3：1, 2, 4
回合 4：2, 4
</pre>

示例 2：

<pre>输入：n = 5, firstPlayer = 1, secondPlayer = 5
输出：[1,1]
解释：两名最佳运动员 1 和 5 将会在回合 1 进行比拼。
不存在使他们在其他回合进行比拼的可能。
</pre>

 

提示：

<ul>
	<li><code>2 &lt;= n &lt;= 28</code></li>
	<li><code>1 &lt;= firstPlayer &lt; secondPlayer &lt;= n</code></li>
</ul>