Connection Status:
Competition Arena > GameOfTokens

GameOfTokens

2017 TCO Final · 2017-03-31 · by cgy4ever

2017 TCO Final · 2017-03-31 · by cgy4ever · Dynamic Programming
Class Name: GameOfTokens
Return Type: int
Method Name: count
Arg Types: (string)
Problem Statement

Problem Statement

Alice and Bob are playing a game called "Game of Tokens". The game is played on a 1 by n board. Each cell of the board can contain at most one token at any time. There are two types of tokens: 'A' tokens and 'B' tokens. A board state can therefore be described by a string of length n consisting of the characters 'A', 'B', and '.', with the period denoting an empty cell.

The rules of the game are as follows:
  • The players take alternating turns. Alice plays first.
  • When it is Alice's turn, she must choose one of the 'A' tokens and move it one cell to the left. Note that the destination cell must be empty.
  • When it is Bob's turn, he must choose one of the 'B' tokens and move it one cell to the left. Note that the destination cell must be empty.
  • The first player who is unable to make a valid move loses the game.
You are given a String pattern with n characters. Each character in pattern is one of 'A', 'B', '.', and '?', with the question mark denoting a wildcard. We say that a board matches the pattern given in pattern if it can be obtained from pattern by replacing each question mark by one of the other three characters. (Hence, if pattern contains k question marks, there are exactly 3^k boards that match the pattern.)

Among all boards that match pattern, let X be the number of boards for which Alice has a winning strategy. Compute and return the value X modulo (10^9 + 7).

Constraints

  • pattern will contain between 1 and 50 characters, inclusive.
  • Each character in pattern will be one of {'.', 'A', 'B', '?'}.
Examples
0)
".AB"
Returns: 0

Obviously, the only board that matches the given pattern is ".AB" itself. For this board there is only one way for the game to play out: Alice must move the only A token to the left. The board becomes "A.B". Bob must move the only B token to the left. The board becomes "AB.". Alice cannot make a valid move, so she loses the game. Thus, the board ".AB" is a losing position for Alice.

1)
"???B"
Returns: 1

Among all 27 boards that match pattern, the only board that is a winning position for Alice is ".AAB".

2)
"???????...BBB"
Returns: 0
3)
"?.A?.B??.??B?"
Returns: 517
4)
"????????????????????"
Returns: 612621096

Don't forget mod.

Submissions are judged against all 106 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GameOfTokens with a public method int count(string pattern) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous