What is the key insight behind solving the Alice and Bob Playing Flower Game problem?

The key insight is recognizing that valid pairs (x, y) must have different parities, meaning if x is odd, y must be even, and vice versa.

How can I optimize the solution for large values of n and m?

To optimize for larger inputs, consider using modular arithmetic or precomputing the number of odd and even flowers, reducing unnecessary computations.

What does the 'circle' in the Alice and Bob Playing Flower Game problem represent?

The circle represents a circular field, meaning that the flower positions are considered cyclic, and the calculation of x and y must account for the circular nature.

Why are parities important in solving this problem?

The parities are crucial because the game condition requires that the number of flowers between Alice and Bob, in both directions, must have different parities to be valid.

What is the time complexity of the optimal solution for this problem?

The time complexity of the optimal solution depends on the approach used, but with parity analysis and modular arithmetic, it can be reduced to an efficient solution with time complexity close to O(n).

#3021

Medium

auto_awesome数学·driven

LeetCode 题解工作台

Alice 和 Bob 玩鲜花游戏

Alice 和 Bob 在一片田野上玩一个回合制游戏，他们之间有两排花。Alice 和 Bob 之间第一排有 x 朵花，第二排有 y 朵花。游戏过程如下： Alice 先行动。每一次行动中，当前玩家必须选择其中一排，然后在这边摘一朵鲜花。一次行动结束后，如果两排上都没有剩下鲜花，那么当前玩…

数学

题目描述

Alice 和 Bob 在一片田野上玩一个回合制游戏，他们之间有两排花。Alice 和 Bob 之间第一排有 x 朵花，第二排有 y 朵花。

游戏过程如下：

Alice 先行动。
每一次行动中，当前玩家必须选择其中一排，然后在这边摘一朵鲜花。
一次行动结束后，如果两排上都没有剩下鲜花，那么当前玩家抓住对手并赢得游戏的胜利。

给你两个整数 n 和 m ，你的任务是求出满足以下条件的所有 (x, y) 对：

按照上述规则，Alice 必须赢得游戏。
第一排的鲜花数目 x 必须在区间 [1,n] 之间。
第二排的鲜花数目 y 必须在区间 [1,m] 之间。

请你返回满足题目描述的数对 (x, y) 的数目。

示例 1：

输入：n = 3, m = 2
输出：3
解释：以下数对满足题目要求：(1,2) ，(3,2) ，(2,1) 。

示例 2：

输入：n = 1, m = 1
输出：0
解释：没有数对满足题目要求。

提示：

1 <= n, m <= 10⁵

lightbulb

解题思路

方法一：数学

根据题目描述，每一次行动，玩家都会选择顺时针或者逆时针方向，然后摘一朵鲜花。由于 Alice 先行动，因此当 $x + y$ 为奇数时，Alice 一定会赢得游戏。

因此，鲜花数目 $x$ 和 $y$ 满足以下条件：

$x + y$ 为奇数；
$1 \le x \le n$ ；
$1 \le y \le m$ 。

若 $x$ 为奇数， $y$ 一定为偶数。此时 $x$ 的取值个数为 $\lceil \frac{n}{2} \rceil$ ， $y$ 的取值个数为 $\lfloor \frac{m}{2} \rfloor$ ，因此满足条件的数对个数为 $\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor$ 。

若 $x$ 为偶数， $y$ 一定为奇数。此时 $x$ 的取值个数为 $\lfloor \frac{n}{2} \rfloor$ ， $y$ 的取值个数为 $\lceil \frac{m}{2} \rceil$ ，因此满足条件的数对个数为 $\lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil$ 。

因此，满足条件的数对个数为 $\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil$ ，即 $\lfloor \frac{n + 1}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m + 1}{2} \rfloor$ 。

时间复杂度 $O(1)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        a1 = (n + 1) // 2
        b1 = (m + 1) // 2
        a2 = n // 2
        b2 = m // 2
        return a1 * b2 + a2 * b1

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Problem-solving involves quick analysis of mathematical patterns.
question_mark
Candidate demonstrates proficiency in math-driven algorithms.
question_mark
Approach to parity analysis shows efficiency and optimization.

warning

常见陷阱

外企场景

error
Overlooking the parity condition can lead to incorrect pair counting.
error
Failing to optimize the counting approach could result in inefficient solutions for large inputs.
error
Not understanding the circular nature of the field might complicate boundary conditions.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider different sizes of n and m to evaluate solution performance.
arrow_right_alt
Explore edge cases such as the smallest values for n and m.
arrow_right_alt
Examine how changes in the circular structure affect the solution for n and m.

help

常见问题

外企场景

继续练习

#3024 三角形类型 #3025 人员站位的方案数 I #3027 人员站位的方案数 II