Grundy numbers problem

Правка en2, от Naseem17, 2020-03-23 00:02:19

Hello Codeforces!

Is it necessary that the two players play in the same way when considering a Grundy numbers approach?

For example, in problems like this: E. Game With String, let's consider that $$$n \le 100$$$. Is the following approach correct?

Let's consider the subsegments that has only $$$.$$$ characters and their lengths. Take the second test as an example $$$X...X.X..X$$$, we have three subsegments with lengths $$$3,1$$$ and $$$2$$$.

If we considered $$$a=b$$$ then the following approach is correct:

We calculate the Grundy number for each subsegment. a player can split the subsegment with length $$$len$$$ into two subsegments with lengths $$$len1$$$ and $$$len2$$$ such that $$$len1+len2=len-a$$$, we can try each possible value for $$$len1$$$ and find the corresponding $$$len2$$$ and the value for the pair $$$len1$$$ and $$$len2$$$ is their X-OR (let's call it $$$x_i$$$) , the Grundy number for $$$len$$$ is the MEX of all $$$x_i$$$. Now if the X-OR of the Grundy numbers of all lengths of the subsegments equals to $$$0$$$ then the second player wins. The first one wins otherwise.

But what if $$$a \neq b$$$? Can I take calculate the Grundy number for each $$$len$$$ like this:

Calculate the Grundy number for each player. Let's call the Grundy number for $$$len$$$ for the first player $$$g_1[len]$$$ and for the second player $$$g_2[len]$$$. now $$$g_1[len]$$$ is equal to the MEX of all possible $$$g_2[len1] \mathbin{\oplus} g_2[len2]$$$ where $$$len1+len2=len-a$$$, and $$$g_2[len]$$$ is equal to the MEX of all possible $$$g_1[len1] \mathbin{\oplus} g_1[len2]$$$ where $$$len1+len2=len-b$$$.

Like this I calculated the Grundy number for each player. now if the X-OR of all $$$g_1[len]$$$ of all subsegments is $$$0$$$ then the second player wins, the first player wins otherwise.

Is this approach correct? And even if it's not, again, is it necessary that the two players play in the same way in all Grundy numbers approaches?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский Naseem17 2020-03-23 00:02:19 75 Tiny change: '_1[len1] \xor g_1[len2]' -> '_1[len1] \mathbin{\oplus} g_1[len2]'
en1 Английский Naseem17 2020-03-21 03:08:20 1876 Initial revision (published)