Skip to content

3021. Alice and Bob Playing Flower Game

SourceWeekly Contest 382 Q3DifficultyMediumRating1581

Description

Alice and Bob are playing a turn-based game on a field, with two lanes of flowers between them. There are x flowers in the first lane between Alice and Bob, and y flowers in the second lane between them.

The game proceeds as follows:

  1. Alice takes the first turn.
  2. In each turn, a player must choose either one of the lane and pick one flower from that side.
  3. At the end of the turn, if there are no flowers left at all in either lane, the current player captures their opponent and wins the game.

Given two integers, n and m, the task is to compute the number of possible pairs (x, y) that satisfy the conditions:

  • Alice must win the game according to the described rules.
  • The number of flowers x in the first lane must be in the range [1,n].
  • The number of flowers y in the second lane must be in the range [1,m].

Return the number of possible pairs (x, y) that satisfy the conditions mentioned in the statement.

 

Example 1:

Input: n = 3, m = 2
Output: 3
Explanation: The following pairs satisfy conditions described in the statement: (1,2), (3,2), (2,1).

Example 2:

Input: n = 1, m = 1
Output: 0
Explanation: No pairs satisfy the conditions described in the statement.

 

Constraints:

  • 1 <= n, m <= 105

Solutions

Solution 1: Mathematics

Thinking

Each move picks one flower from a lane, and the first player wins iff \(x+y\) is odd. \(n,m \le 10^5\) forbids enumerating cells.

Odd–even and even–odd pairs are exactly the winning positions. The counts of odds and evens on each side multiply and add.

Integer division yields those four counts, which we cross-multiply.

According to the problem description, in each move, the player will choose to move in a clockwise or counterclockwise direction and then pick a flower. Since Alice moves first, when \(x + y\) is odd, Alice will definitely win the game.

Therefore, the number of flowers \(x\) and \(y\) meet the following conditions:

  1. \(x + y\) is odd;
  2. \(1 \le x \le n\);
  3. \(1 \le y \le m\).

If \(x\) is odd, \(y\) must be even. At this time, the number of values of \(x\) is \(\lceil \frac{n}{2} \rceil\), the number of values of \(y\) is \(\lfloor \frac{m}{2} \rfloor\), so the number of pairs that meet the conditions is \(\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor\).

If \(x\) is even, \(y\) must be odd. At this time, the number of values of \(x\) is \(\lfloor \frac{n}{2} \rfloor\), the number of values of \(y\) is \(\lceil \frac{m}{2} \rceil\), so the number of pairs that meet the conditions is \(\lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil\).

Therefore, the number of pairs that meet the conditions is \(\lceil \frac{n}{2} \rceil \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lceil \frac{m}{2} \rceil\), which is \(\lfloor \frac{n + 1}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m + 1}{2} \rfloor\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
4
5
6
7
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

1
2
3
4
5
6
7
8
9
class Solution {
    public long flowerGame(int n, int m) {
        long a1 = (n + 1) / 2;
        long b1 = (m + 1) / 2;
        long a2 = n / 2;
        long b2 = m / 2;
        return a1 * b2 + a2 * b1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
public:
    long long flowerGame(int n, int m) {
        long long a1 = (n + 1) / 2;
        long long b1 = (m + 1) / 2;
        long long a2 = n / 2;
        long long b2 = m / 2;
        return a1 * b2 + a2 * b1;
    }
};

1
2
3
4
5
func flowerGame(n int, m int) int64 {
    a1, b1 := (n+1)/2, (m+1)/2
    a2, b2 := n/2, m/2
    return int64(a1*b2 + a2*b1)
}

1
2
3
4
5
function flowerGame(n: number, m: number): number {
    const [a1, b1] = [(n + 1) >> 1, (m + 1) >> 1];
    const [a2, b2] = [n >> 1, m >> 1];
    return a1 * b2 + a2 * b1;
}

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn flower_game(n: i32, m: i32) -> i64 {
        let a1 = ((n + 1) / 2) as i64;
        let b1 = ((m + 1) / 2) as i64;
        let a2 = (n / 2) as i64;
        let b2 = (m / 2) as i64;
        a1 * b2 + a2 * b1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var flowerGame = function (n, m) {
    const [a1, b1] = [(n + 1) >> 1, (m + 1) >> 1];
    const [a2, b2] = [n >> 1, m >> 1];
    return a1 * b2 + a2 * b1;
};

Solution 2: Mathematics (Optimized)

Thinking

Expanding the cross product by the parities of \(n\) and \(m\) collapses all four cases to \(\lfloor nm/2 \rfloor\).

A single integer multiply-and-divide therefore replaces the four-term formula.

The result obtained from Solution 1 is \(\lfloor \frac{n + 1}{2} \rfloor \times \lfloor \frac{m}{2} \rfloor + \lfloor \frac{n}{2} \rfloor \times \lfloor \frac{m + 1}{2} \rfloor\).

If both \(n\) and \(m\) are odd, then the result is \(\frac{n + 1}{2} \times \frac{m - 1}{2} + \frac{n - 1}{2} \times \frac{m + 1}{2}\), which is \(\frac{n \times m - 1}{2}\).

If both \(n\) and \(m\) are even, then the result is \(\frac{n}{2} \times \frac{m}{2} + \frac{n}{2} \times \frac{m}{2}\), which is \(\frac{n \times m}{2}\).

If \(n\) is odd and \(m\) is even, then the result is \(\frac{n + 1}{2} \times \frac{m}{2} + \frac{n - 1}{2} \times \frac{m}{2}\), which is \(\frac{n \times m}{2}\).

If \(n\) is even and \(m\) is odd, then the result is \(\frac{n}{2} \times \frac{m - 1}{2} + \frac{n}{2} \times \frac{m + 1}{2}\), which is \(\frac{n \times m}{2}\).

The above four cases can be combined into \(\lfloor \frac{n \times m}{2} \rfloor\).

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

1
2
3
class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return (n * m) // 2

1
2
3
4
5
class Solution {
    public long flowerGame(int n, int m) {
        return ((long) n * m) / 2;
    }
}

1
2
3
4
5
6
class Solution {
public:
    long long flowerGame(int n, int m) {
        return ((long long) n * m) / 2;
    }
};

1
2
3
func flowerGame(n int, m int) int64 {
    return int64((n * m) / 2)
}

1
2
3
function flowerGame(n: number, m: number): number {
    return Number(((BigInt(n) * BigInt(m)) / 2n) | 0n);
}

1
2
3
4
5
impl Solution {
    pub fn flower_game(n: i32, m: i32) -> i64 {
        (n as i64 * m as i64) / 2
    }
}

1
2
3
4
5
6
7
8
/**
 * @param {number} n
 * @param {number} m
 * @return {number}
 */
var flowerGame = function (n, m) {
    return Number(((BigInt(n) * BigInt(m)) / 2n) | 0n);
};

Comments