Indian Computing Olympiad

Games and strategies

Bead Necklace (originally Pearls, CEOI 2003)

There are blue dwarves and white dwarves, totally 1000 of them. The two types of dwarves are on opposite teams. One blue dwarf and one white dwarf found a bead necklace with red and black beads ending in a single pearl. Each team wants to get hold of the pearl.

To achieve this, they play a game:

Each dwarf D is given two lists, a red list R_D and a black list B_D. Both R_D and B_D are sets of dwarves (these sets may contain dwarves of either colour, but are guaranteed to be nonempty).

The necklace is given to one of the dwarves D. His moves are:

1. If the leftmost bead is the pearl, keep it and game ends.
2. If the leftmost bead is red, remove it and hand over the necklace (with leftmost bead removed) to any dwarf in the red list R_D.
3. If the leftmost bead is black, remove it and hand over the necklace (with leftmost bead removed) to any dwarf in the black list B_D.

You are given:

1. The sequence of beads in the necklace
2. The black and red lists of each dwarf
3. Who has the necklace at the beginning

Your aim is to determine whether the dwarf can ensure that the pearl eventually reaches another dwarf on his own team.

Solution

The current position of the game is completely described by The quantities (D,N) where

• D: which dwarf has the necklace
• N = b1 b2 .. bk: the sequence of beads in the necklace (without the pearl)

Call this a configuration. For each pair (D,N), label the configuration as W (winning) or L (losing). If the label is W, D can ensure that the pearl reaches his team. If the label is L, no matter what D does, the pearl reaches the other team.

We work backwards from the last bead in the necklace. If the necklace is currently a single pearl, the configuration is winning for all D.

Now, we step back once so that we have a configuration (D,bk). Depending on the identity of D and the lists he has, we know whether this is winning for the team that D belongs to.

• If D is white, bk is red and there is at least one white dwarf D' in the list R_D, then D can revmove bk and hand the necklace to D', who gets the pearl. So, this configuration is winning.

  On the other hand, if R_D has no white dwarves, D must hand over the necklace with just the pearl to some blue dwarf, so (D,bk) is labelled L.

  Similarly, if bk is black, (D,bk) is winning if there is at least one white dwarf D' in the list B_D and (D,bk) is losing if there is no white dwarf D' in the list B_D.

• Symmetrically, we can identify when (D,bk) is winning for an blue dwarf D.

In general, assume that we have calculated the status of (D,N) for N = b1 b2 ... bk. We can now calculate the status if we add an additional bead b0 to the left of N.

Suppose b0 is red and D is a blue dwarf. Then we can label (D,b0...bN) as W if either of the following hold:

• there is a blue dwarf D' on D's red list such that (D',b1..bN) is labelled W. (Then we can k keep the bead in the same team and win in next configuration.)
• there is a white dwarf D' on D's red list such that (D',b1..bN) is labelled L. (Then we hand over the bead to the other team which is guaranteed to lose in next configuration.)

Otherwise, label (D,b0...bN) as L (D cannot avoid making a move that leads to a losing position).

Make similar updates for the other three possibilities for b0 and D — (b0 is black and D is white), (b0 is black and D is blue) and (b0 is red and D is white).

In this way, we can work backwards and label the initial configurations at W or L.