PWNCHESS - Editorial

general
, , , ,
1

Problem Link:

Practice

Contest

Setter: Alei Reyes

Tester: Triveni Mahatha

Editorialist: Alei Reyes

Difficulty:

MEDIUM

Prerequisites:

Basic understanding of combinatorial game theory is helpful but not necessary.

Problem:

Given a 1 x N length chess board and few white and black pawns placed on it. All white pawns are initially left of all black pawns. White can only move right and black can only move left. In each move only one pawn moves exactly one step. If both players plays optimally determine the winner (white plays first).

Explanation:

Let L and R be the columns of the rightmost white pawn, and the leftmost black pawn respectively. Let’s call these two pieces “central pawns”. There are two cases:

  • There is at least one cell between L and R.

The optimal game in this case is to keep moving the central pawns until there is exactly one cell between them (let’s call this cell C the “center” ).
Then both players can move any of their non-central pawns, until one of player is forced to move his central pawn and fall in a chain of captures, leading inevitably to the defeat.

Note that according to this strategy, Whites and Blacks try to place their pieces side by side at the left and right of the center.

Let’s denote by SW the sum of distances of the white pawns to their target position (not occupied, nearest cell to the center). And by SB the corresponding sum of distances for Blacks.

White wins iff SW is strictly greater than SB. This is because once Whites place his central pawn one unit to the left of the center, he can wait as long as necessary forcing Blacks to move his central pawn to the center. Then Whites capture, rinse and repeat. Similarly by a symmetric argument can be proved that this condition is sufficient.

   L  C  R
     W.W.[.].BB
  • L and R are adjacent

This one is a bit tricky. At first glance it seems that is always convenient to capture the black pawn, but the following example proves it wrong. For example, consider -

  W.WBBB

In this case it is better to move pawn at column 1 to column 2 instead of capturing the pawn at 4. However, it is also possible to find configurations where it is optimal to capture. So we have to check two possibilities.

  • If Whites does not capture the pawn in his first move, then he will never capture it in the future (Otherwise it would be optimal to capture in the first move itself), that means that Blacks will capture pawn L, the game is equivalent to a game where pawn at position L does not exists as black will anyways pass through it. Therefore the problem is reduced to the first case.

  • On the other hand, if Whites decides to capture, then in the next move blacks can again capture or not. And there will be no more immediate captures since the new central pawns will be separated by at least once cell. Again the problem is reduced to the first case.

Note that to find **C** or compute **SW** and **SB** takes linear time. And the case 2 above takes place only constant times. So, overall complexity is linear.

SOLUTION:

Setter

Tester

Time Complexity:

O(N), per test case.

Space Complexity:

O(N)

1 Like
2

Setter Solution is not available.

1 Like