LeetCode 3021: Alice and Bob Playing Flower Game

Problem:

https://leetcode.com/problems/alice-and-bob-playing-flower-game/description

Solution:

Notice that Alice wins if and only if (x+y) open paren x plus y close paren mod 2 2 ≡1 is identical to 1, in other words the sum is odd. This is true regardless of the distribution of flowers between the two lanes - minus all that matters in determining the winner is the sum.

The total space of possible pairs (x,y) open paren x comma y close paren contains n⋅m n times m points.

This space can be visualized as follows for n n = equals 3 3, m m = equals 5:

1

2

3

4

5

1

✅

✅

2

✅

✅

✅

3

✅

✅

We count 7 7 pairs out of 15 15 that represent games in which Alice wins.

We also notice a pattern → right arrow games alternate between Alice and Bob wining.

Another way to think about this problem is to enumerate each possible game in a list.

Game 1 1 → right arrow (1,1) open paren 1 comma 1 close paren

Game 2 2 → right arrow (1,2) open paren 1 comma 2 close paren ✅

Game 3 3 → right arrow (1,3) open paren 1 comma 3 close paren

Game 4 4 → right arrow (1,4) open paren 1 comma 4 close paren ✅

⋮ vertical ellipsis

Game k=n⋅m k equals n times m → right arrow (n,m) open paren n comma m close paren

Since Alice wins on the even-numbered games we can reformulate the problem to ask how many numbers in the range [1,k] open bracket 1 comma k close bracket are even?

If k k is even, the answer is simply k2 k over 2, if it is odd, it's k-12 the fraction with numerator k minus 1 and denominator 2 and this can be summarized as ⌊k2⌋ floor of k over 2

Thus, there are ⌊n⋅m2⌋ floor of the fraction with numerator n times m and denominator 2 games in which Alice wins.