Why "++++-++++++" is a win.


  • -1
    Y

    Update:

    Thanks bravejia for pointing out one case which was missing in my original post.

    the winning strategy is that after flip, two strings are still both can-win-or-lose strings. Basically, starting player can choose not to make decision in his first turn.

    Take "++++-++++++" as an example again:

    A: ++++---++++

    This will leave B with two both can-win-or-lose strings. And there will be no further subset can-win-or-lose strings.


    Orignal Post:

    I think "++++-++++++" is a lose. And here is why.

    Both ++++ and ++++++ are can-win-or-lose strings. A can-win-or-lose string is a case where first player can choose if he wants to win or lose.
    For example, in case of ++++, first player can choose flip middle two to win, or to flip first two to lose.

    So in case of two can-win-or-lose strings, or even number of can-win-or-lose strings, second player can always adjust his strategy based on first player's move.

    Take "++++-++++++" as an example,

    If A choose to win "++++", B can win by winning"++++++".

    A: +--+-++++++

    B: +--+-++--++

    If A choose to lose "++++", B can win by losing"++++++".

    A: --++-++++++

    B: --++-+--+++

    B can have same strategy If A choose to flip second can-win-or-lose strings first.

    So "++++-++++++" is a lose. Feel free to correct me if I am wrong.


  • 2
    B

    If I was the starting player, I'll flip this ++++-++++++ into this ++++---++++. I'll win no matter what. Let me know if this make sense.


  • 0
    Y

    I see. I missed this case where after flip, two strings are still both can-win-or-lose strings. Basically, starting player can choose not to make decision in this case. Thanks for your input.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.