Pathetic_loser's blog

To any kind Chinese contestant,help in understanding Editorial written in Chinese
By Pathetic_loser, 10 years ago, In English

Hi

If you know Chinese, could you be very kind and translate the part from "1003 Revenge of Nim II" from http://bestcoder.hdu.edu.cn/ ? :) Google translation is really hard to understand for me.

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

»
10 years ago, # |
  Vote: I like it -35 Vote: I do not like it

xD

→ Reply
»
10 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think CF should add Chinese to languages, too

→ Reply
»
10 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

//My English is not good, so the translation may not be perfect, but I think that you can understand it. 1003 Revenge of Nim II //Let's call the one who first play X, the other one Y. Nim's game's room for Y's cheat is to move some piles of objects(not all of them), Is it guarantee that X will lose? Nim's game's requirement of X will lose is XORSUM(a[i])=0. Y's goal is to find a non-empty set which XORSUM(a[i])=0. Let's think the a[i] here a line which each bit is 0 or 1. All the numbers form a matrix. The operation of this matrix is XOR. If this matrix satisfies Rank-mat=Row-Num-mat, then its any subsets' XORSum is unique, and the non-empty subset's XORSUM is not zero, or the Rank of the matrix will be smaller than RowNum. What about Rank-mat<RowNum-Mat? Then for any subsets which satisfies Rank-Submat<RowNum-Subset, the other row can get through the XOR of some of the rows of the matrix. Then there will be an subset A that XORSum(a[i]|a[i] belongs to subset A)=0.

Complexity: O(maxb^3)|maxb=log(maxa), about 40. Degree of difficulty: 2.0/5

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

    Thank you :) The solution was unusual for me and deciphering the broken pieces from google translate was turning out to be really painful.

    → Reply