When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

izlyforever's blog

By izlyforever, history, 3 years ago, In English

nihal2001 posted a blog for asking the following question:

There are $$$n$$$ stones, two players take turn to choose $$$x$$$ stones, such that $$$1 \leq x \leq n$$$ and $$$x \And n = 0$$$. The one who cannot make choose lose.

Determine who is the winner, The first one or the second?

I proved that If $$$n$$$ belongs to https://oeis.org/A295897, the second player win(can be solved in $$$O(\log n)$$$).

My Question(Multiple piles version of above question):

There are $$$n_1, \cdots, n_m$$$ stones, two players take turn to choose an index $$$i$$$ and $$$x_i$$$ stones, such that $$$1 \leq i \leq m$$$, $$$1 \leq x_i \leq n_i$$$ and $$$x_i \And n_i = 0$$$. The one who cannot make choose lose.

Who will be the winner?

This turn out to compute Sprague-Grundy function for $$$n_1 \cdots, n_m$$$. The first player win if and only if $$$sg(n_1) \wedge \cdots \wedge sg(n_m) \neq 0$$$

I know how to compute $$$sg(n)$$$ in $$$O(n^2 \log n)$$$, but I can't give it a formula or compute efficiently like $$$O(\log n)$$$ or $$$O(\log^2 n)$$$

Thanks in advance.

UPD: $$$O(n^{log_2 3} \log n)$$$ implement based on wery0's comment.

UPD2: $$$O(n^{log_2 3})$$$ implement based on wery0's talk.

  • Vote: I like it
  • +31
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

This is really an interesting question.

I don't want to let it fall on deaf ears, so I comment again(sorry).

Looking forward to talented players to help me solve this problem.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$sg(n) = MEX(\{sg(n-x): 1 \leq x \leq n, \space x\&n=0\})$$$

Let $$$F(n)$$$ = number of $$$x$$$, such that $$$1 \leq x \leq n, \space x\&n=0$$$.

Since we can count $$$MEX$$$ of $$$N$$$ numbers in $$$O(N)$$$, we can calculate $$$sg(n)$$$ in $$$O(F(n))$$$.

To find $$$sg(n)$$$ we also should calculate $$$sg$$$ for some numbers $$$\leq n$$$. Let's do it for all numbers $$$\leq n$$$. It will work in $$$\sum_{i=1}^{n} F(i)$$$. Turns out that $$$\sum_{i=1}^{n} F(i) = O(n^{log_2 3}) \approx O(n^{1.59})$$$.

So, the complexity of this solution is $$$O(n^{log_2 3})$$$. Maybe it is possible to do faster, idk.

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Thanks!

    The only thing I don't understand is how to judging all reasonable x in $$$O(F(n))$$$.

    I can only solve it in $$$O(n^{\log_2 3} \log n)$$$ after your explanation.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      if $$$m$$$ is complement of $$$n$$$, then $$$F(n)$$$ is just all the submasks of $$$m$$$ and you can loop over them with one for cycle like this:

      for(int i = m; i > 0; i = (i-1) & m)

      this works because $$$(i-1)\text{&}m $$$ is the biggest number less than $$$i$$$ that is submask of $$$m$$$.

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes, This is exactly in wery0's talk, and this trick is used my implement.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by izlyforever (previous revision, new revision, compare).