Connection Status:
Competition Arena > ReturnedKnight

ReturnedKnight

SRM 797 · 2021-01-08 · by misof

SRM 797 · 2021-01-08 · by misof · Advanced Math, Graph Theory
Class Name: ReturnedKnight
Return Type: String[]
Method Name: construct
Arg Types: (int, int)
Problem Statement

Problem Statement

Given a rectangular chessboard with some obstacles and a single chess knight, we can play a simple game. We will start by marking one empty square as the starting square and placing the knight there. From this point on, we will repeatedly choose and perform a valid move of the knight. (The move is always chosen uniformly at random from the set of moves that are valid at that moment. The random choices are mutually independent. Squares that contain obstacles cannot be the target of a move.)

The game ends when the knight returns to its starting square for the first time. The outcome of the game is the number of moves it took. If the starting square is such that the knight has no valid moves, we define that the outcome of the game is 0.


You are given a positive fraction P / Q. Your task is as follows:

  1. Take a rectangular chessboard with at most 30 rows and at most 30 columns. (You get to choose the dimensions.)
  2. Place zero or more obstacles onto the board.
  3. Mark one of the empty squares as the knight's starting square.
  4. You win if the expected outcome of the game for your chessboard equals P / Q.

Return your board formatted as a String[], using '.' for empty squares, '#' for obstacles, and 'N' for the knight's starting position. All valid solutions will be accepted. If there is no valid solution, return an empty String[].

Notes

  • A chess knight moves by two squares in one direction and then by one square in the two orthogonal directions. (Thus, on an empty infinite chessboard a knight has exactly 8 valid moves from each cell.)
  • The knight can jump over obstacles. For each move, only the square where it ends its move must be obstacle-free.

Constraints

  • P will be between 1 and 1000, inclusive.
  • Q will be between 1 and 1000, inclusive.
Examples
0)
2
1
Returns: {".######..", "##N####..", "####.##.." }

.######.. ##N####.. ####.##.. The knight has two options for its first jump. Regardless of which one it chooses, in the second jump it will have to return back where it started. Thus, each possible game on this board has outcome 2.

1)
800
100
Returns: {"N..", "...", "..." }

N.. ... ... For this board some games will end in two moves, some will end in two thousand moves. It can be shown that the average outcome of a game for this board is exactly 8. {".N.", ".#.", "..."} would also be a valid answer. In this particular situation we cannot visit the middle cell so we may put an obstacle there without changing the outcome of the game. Also, all eight possible starting cells happen to be equivalent.

2)
22
3
Returns: {"...", "..N", "..#", "..." }
3)
93
47
Returns: { }

This is clearly impossible: on any board where the outcome of the game is positive its smallest possible value is 2, and therefore its expected value is at least 2.

4)
1
1
Returns: { }

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

Coding Area

Language: C++17 · define a public class ReturnedKnight with a public method vector<string> construct(int P, int Q) · 200 test cases · 2 s / 256 MB per case

Submitting as anonymous