Блог пользователя iamneerajhari

Game Where Players Remove Two Consecutive Similar Numbers From a List
Автор iamneerajhari, история, 13 месяцев назад, По-английски

Recently, I encountered the following problem for which the given solution was straightforward but no proof was provided for a crucial claim made in the solution.

Alice and Bob plays a game where a list of numbers is given. Here are the rules of the game:

  1. Alice starts, and the players take turns.
  2. On a turn, a player can remove two consecutive similar numbers from the list.
  3. If a player cannot make a valid move, they lose, and the other player wins.

Determine who wins the game if both the players play optimally.

Solution: In the solution given across various websites, we start from the left end of the list and use a stack to keep track of the numbers. If you encounter a number that is similar to the one at the top of the stack, both get deleted. Otherwise, add the number to the stack. The outcome of the game depends on whether the total number of moves (i.e. the number of deletion steps) is even or odd.

Claim: "The total number of moves required for the game to end (i.e. the number of deletion steps) is independent of the order in which we make the deletions."

In order for the solution to work, the above claim should stand. In all of the websites, the above claim was made without giving any proof for it. Could somebody give a reason as to why this claim stands?

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
13 месяцев назад, # |
  Проголосовать: нравится -25 Проголосовать: не нравится

Since it's consecutive, you need to use <stack> to process the array.

void solve() // sample code generated with AI fr :skull:
{
    for (auto element : arr)
    {
        if (st.empty() || st.top() != element) // if no consecucitive push it 
        {
            st.push(element);
        }
        else
        {
            st.pop(); //else they're same count it and pop that top element
            cnt++;
        }
        if (cnt & 1) // if cnt is odd
            cout<<"ALICE\n";
        else if (!(cnt & 1))
            cout<<"BOB\n"; //else if even its bob winning the game
        else
            cout<<"I won ez\n"; // else its me stealing all the cards and running away
    }
}
→ Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

→ Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    .

    → Ответить
  • »
    »
    13 месяцев назад, # ^ |
    ← Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

    I can think of a few points:

    • if there is a valid move (two equal and adjacent elements), you can extend the number of possible moves by 1, and then delete those two elements.

    • no decision to make a valid move can hurt you if you do it right away (it won't prevent you from doing a future move)

    • so doing as many valid moves as you can cannot hurt, and once you run out of valid moves, no past decisions could give you new valid moves and you cannot do anything in that moment. so you will be stuck with that final array.

    so actually, we need to prove the second point,

    → Ответить
    • »
      »
      »
      13 месяцев назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

      Yes, the second point is what we need to prove. Here, it is equivalent to saying that all set of moves lead to the same outcome.

      → Ответить
»
13 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Surprisingly fiddly to prove it properly — maybe I'm missing something simpler. It is true that the moves make no difference to the final state — it is predetermined.

I'll give a handwavy idea of the proof, because it's too long if rigorous.

Consider an induction on the length of the string. Then consider some arbitrary string $$$S$$$ and adding an arbitrary symbol $$$a$$$. If you play on $$$Sa$$$ and at some point the added $$$a$$$ is matched in a pair, you can pretend that this move wasn't made and then make it at the very end of the game, without changing what the final state would be in both variations. This works, because the pair is at the very end (you can't make this argument for a middle pair).

It follows that all final states can be achieved with the last $$$a$$$ being matched either never, or at the very last move. Then you just apply the induction — since you've already proven $$$S$$$ has a unique final state, then applying all moves that don't involve the last $$$a$$$ will just reduce $$$S$$$ to some $$$F(S)$$$, and if $$$F(S)$$$ ends on $$$a$$$ — there is exactly one forced move left, if it doesn't end on $$$a$$$ — then there are no moves. In either case based on the string $$$S$$$ you have a deterministic final state.

→ Ответить