Massive Algorithms: LeetCode 810 - Chalkboard XOR Game

LeetCode 810 - Chalkboard XOR Game

We are given non-negative integers nums[i] which are written on a chalkboard. Alice and Bob take turns erasing exactly one number from the chalkboard, with Alice starting first. If erasing a number causes the bitwise XOR of all the elements of the chalkboard to become 0, then that player loses. (Also, we’ll say the bitwise XOR of one element is that element itself, and the bitwise XOR of no elements is 0.)

Also, if any player starts their turn with the bitwise XOR of all the elements of the chalkboard equal to 0, then that player wins.

Return True if and only if Alice wins the game, assuming both players play optimally.

Example:
Input: nums = [1, 1, 2]
Output: false
Explanation: 
Alice has two choices: erase 1 or erase 2. 
If she erases 1, the nums array becomes [1, 2]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 2 = 3. Now Bob can remove any element he wants, because Alice will be the one to erase the last element and she will lose. 
If Alice erases 2 first, now nums becomes [1, 1]. The bitwise XOR of all the elements of the chalkboard is 1 XOR 1 = 0. Alice will lose.

Notes:

1 <= N <= 1000.
0 <= nums[i] <= 2^16.

https://leetcode.com/problems/chalkboard-xor-game/discuss/121696/C%2B%2BJavaPython-3-lines-Easy-Solution-with-Complaint-and-Explanation

The solution can be only 3 lines and really simple.
It should be a medium problem.
Hard is kind of misleading.

Why [1, 2, 3] expect true
If xor == 0 at first for Alice, it is considered as Bob lose already!
I find this stupid idea just after contest and I think it doesn't make any sense.
It should complete this condition in the description.

Let's discuss it if we add this condition.
If xor == 0, Alice win directly.
If xor != 0 and length of numbers is even, Alice will win.

Beacause:
All numbers won't be the same. Otherwise xor will be equal to 0
If all numbers are not the same, It means there are at least 2 different numbers.
Alice can always erase a number different from current xor.
So Alice won't never lose this turn at this situation.

If we don't have the condition
Just return nums are not all 0 and length of nums is even

    public boolean xorGame(int[] nums) {
        int xor = 0;
        for (int i: nums) xor ^= i;
        return xor == 0 || nums.length % 2 == 0;
    }

https://leetcode.com/problems/chalkboard-xor-game/discuss/201950/It-is-a-good-practice-not-a-good-problem

If you know Sprague-Grundy theorem, you come up with the following algorithm almost immediately:

mem = {}
def SG(A):                      # 求状态A的SG数
   if A not in mem:
       S = sub_states(A)       # sub_states(A)将A尽可能细致地拆分成子状态
       if len(S) > 1:          # A可以拆分，用子状态的异或求其SG数
           mem[A] = reduce(operator.xor, [SG(B) for B in S])
       else:                   # A不可拆分，根据定义求其SG数
           mem[A] = mex(set(SG(B) for B in next_states(A)))
                               # next_states(A)返回A的所有次态
                               # 注意这条语句蕴含了“终局态的SG数为0”
   return mem[A]

Otherwise, you are not supposed to solve this problem, unless you are as smart as Sprague and Grundy. It is more like a good practise for anyone who know this theorem. It is not a good problem to solve from first principle.

http://guoyc.com/post/leetcode_weekly_contest_78/

把nums全部取异或得到一个xor，之后每个人轮流取一个数和xor进行异或，如果开始时xor为0则获胜。

两种情况：

xor==0，直接获胜
xor!=0，
- nums长度为偶数
  - 这种情况所有数不可能都相等，所以至少有两个数不同（否则xor为0）。所以Alice只要取一个和xor不同的数即可保证异或值不为0，因此Alice不会输。
  - 这种情况Alice必胜
- nums长度为奇数
  - 必输

https://www.cnblogs.com/grandyang/p/9445951.html

这道题介绍了一种亦或游戏，写在黑板上，（黑板一脸懵逼，跟我有个毛关系）。爱丽丝和鲍勃两个人轮流擦除一个数字，如果剩下的数字亦或值为0的话，那么当前选手就输了。反过来也可以这么说，如果某一个选手开始游戏时，当前数字的亦或值为0了，那么直接就赢了。现在给了我们一个数组，问先手的爱丽丝能否获胜。那么其实这道题是一道有技巧的题，并不是让我们按照游戏规则那样去遍历所有的情况，有海量的运算。这题有点像之前那道Nim Game，重要的是技巧！技巧！技巧！重要的事情说三遍～但我等凡夫俗子如何看的出技巧啊，看不出技巧只能看Discuss了，博主也没看出来。但实际上这道题的解法可以非常的简单，两三行就搞定了。辣么开始讲解吧：首先根据题目的描述，我们知道了某个选手在开始移除数字之前，如果数组的亦或值为0的话，选手直接获胜，那么先手爱丽丝在开始开始之前也应该检查一遍数组的亦或值，如果是0的话，直接获胜。我们再来分析亦或值不为0的情况，既然不为0，那么亦或值肯定是有一个值的，我们假设其是x。下面就是本题的精髓了，是要考虑数组个数的奇偶情况（尼玛谁能想到！），这个数组个数一旦是偶数的话，就大有文章了，现在数字个数是偶数，且亦或值不为0，说明数组中的数字不全相同，因为偶数个相同数字的亦或值为0，那么爱丽丝只要移除一个不为x的数字就行了，这样移除后数组的亦或值也不会是0，那么由于鲍勃也是个机智的boy，他也不会移除一个使得剩余数组亦或值为0的数字，but，到了最后一个数字时，鲍勃别无选择只能移除最后一个数字，此时数组为0，亦或值为0，爱丽丝获胜。那此时你可能会有疑问，为啥奇数个数字且亦或值不为0时，爱丽丝一定会输？因为即便爱丽丝先移除掉了一个数字，使得数组亦或值仍不为0，那么此时鲍勃面对的情况就是偶数个数字使得数组亦或值不为0，这跟上面推论爱丽丝一定会赢的情况一样，鲍勃也是个聪明的蓝孩纸，所以爱丽丝会输，参见代码如下：

解法一：

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        int x = 0, n = nums.size();
        for (int num : nums) x ^= num;
        return x == 0 || n % 2 == 0;
    }
};

下面这种解法就很秀了，比大军师大司马吴秀波还秀，直接用个accumulate一行搞定亦或值，博主只想吐槽这道题的难度级别，大家有见过一行解出一道Hard题吗，做梦都要笑醒了吧～

解法二：

class Solution {
public:
    bool xorGame(vector<int>& nums) {
        return nums.size() % 2 == 0 || !accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
    }
};

LeetCode 810 - Chalkboard XOR Game

Labels

Popular Posts