syksykCCC's blog

A Problem I Can't Solve
By syksykCCC, history, 5 years ago, In English

I have an idea, but I don't know how to solve it, so I need your help. Please tell me if you have any ways to solve it. Thanks.

Here is the problem:

Give you a tree with $$$ n $$$ nodes that have root, and there are $$$ a_i $$$ stones on the $$$ i $$$ -th node. Two players take turns operating. At any time, the player can move at least $$$ 1 $$$ stone (at most all stones) on one node to a son of it. The player who can't move will lose. Please calculate whether the first player can win.

I don't know how to solve it, so I can't tell you the scale of $$$ n $$$.

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

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

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -36 Vote: I do not like it

Edit: I've found a counter-example

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Sorry, it is just an idea, so I don't know if there are similar problems...

    Perhaps we can discuss your solution.

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

Consider each stone independently, and calculate SG(x) of them. I think it can work in O(n).

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Well I didn't notice at least 1...Sorry for my careless.

    → Reply