ErrantKnight

SRM 412 · 2008-07-30 · by Eryx

SRM 412 · 2008-07-30 · by Eryx · Dynamic Programming

Show categories

Class Name: ErrantKnight

Return Type: String

Method Name: whoWins

Arg Types: (vector<int>, vector<int>)

Problem Statement

The game of Errant Knights is played on an infinite chessboard using two knights, white and black. The players alternate turns and the white player starts the game. Each player makes a normal chess knight's move with his knight, but there is a restriction that each move must make the Euclidean distance between the two knights smaller. A player can make more than one move in a single turn, but then each move must go in the same direction.

For example, if the black knight is at coordinates (0, 0) and the white knight is at (9, 5), then the white knight can move to (7, 4), (5, 3), (3, 2), (1, 1), (-1, 0). Further moving in this direction is not allowed because (-3, -1) is further from (0, 0) than (-1, 0). Of course, the white knight could also start his turn by moving in one of several other directions, and then possibly making more moves in that direction.

The game ends when one of the knights wins by capturing the other one (by moving to its position), or when it is impossible to make another move (because the knights are orthogonally next to each other and each move would increase the distance). In the second case, the player who should make the next move loses.

Several games of Errant Knight will be played. The starting position of the white knight in the i-th game is (x[i], y[i]). The black knight will start each game at (0, 0). Both players play optimally. Return a String where the i-th character is 'B' if the black knight wins the i-th game or 'W' if the white knight wins.

Notes

A chess knight can move in 8 directions. From (0, 0), a knight could move to (2, 1), (2, -1), (1, 2), (-1, 2), (1, -2), (-1, -2), (-2, 1), (-2, -1).

Constraints

x and y will contain between 1 and 50 elements, inclusive.
x and y will contain the same number of elements.
Each element of x will be between -4000 and 4000, inclusive.
Each element of y will be between -4000 and 4000, inclusive.
For each i, x[i] and y[i] cannot both be equal to 0.

Examples

{1,1,2,2,9,3}
{0,1,0,1,5,3}
Returns: "BWWWWB"

In the first game, there is no possible move for White from (1,0), so Black wins. In the second game, White moves from (1,1) to (0,-1). Black has no legal move from there, so White wins. In the third game, White moves from (2,0) to (0,1). Again, Black has no legal move, and White wins. In the fourth game, White moves from (2,1) to (0,0), and captures the Black knight. White wins. In the fifth game, White makes five moves from the same direction, moving from (9,5) to (-1,0). White wins. In the sixth game, White can make a sequence of moves which lead to one of the following squares: (2,1), (1,-1), (1,2), (-1,1), (4,1), (1,4). After each of these moves Black can win.

{1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,1,2,3,4,5,6,7,7}
{0,0,0,0,0,0,0,1,1,1,1,1,1,1,2,2,2,2,2,2,2,3,3,3,3,3,3,3,4,4,4,4,4,4,4,5,5,5,5,5,5,5,6,6,6,6,6,6,6,7}
Returns: "BWBBBBBWWWWWWWWWWWWWWWWBWWWWWWWBWWWWWWWBWWWWWWWWWB"

{-20,-19,-18,-17,-16,-15,-14,-13,-12,-11,-10,-9,-8,-7,-6,-5,-4,-3,-2,-1,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: "BBBBBWBBWBBWBBBBBBWBBWBBBBBBWBBWBBWBBBBB"

x and y can be negative. [Should this be in examples?]

{-42,-2335,-3170,0,2963,1706,-3282,-1962,0,-828,-392,3903,0,-1422,3719,0,0,1870,-1668,0,-704,-3323,1674,3142,-254,-1548,-663,-38,-724,0,-317,0,0,0,3265,-3447,3891,0,-3007,-394,3630,0,2757,967,-1932,945,-627,0,0,-2930}
{42,0,0,-3479,0,1706,3282,1962,-2996,0,0,3903,-293,0,-3719,-1448,2772,0,1668,-1036,704,-3323,0,-3142,0,0,-663,38,-724,3530,317,2191,289,-1041,0,-3447,3891,-371,-3007,0,-3630,85,0,0,0,-945,627,1538,119,-2930}
Returns: "BBBBBWBBBBBBBWBBBBWBWBWWBBBWWBBBBWBBBBBBBBWBBBBBBW"

random orthogonal or diagonal placements

{833,639,2702,1976,3670,1021,-1079,2270,-1226,1097,3984,-2840,2353,3653,31,-653,-3061,1965,3104,-1995,3456,-250,2944,-3795,-3782,2422,-497,-3589,-3100,-1240,-2592,-379,1546,-408,-398,-1710,-2627,596,-655,-334,-3720,-3947,-1585,2900,-1875,-272,-3355,-2195,2309,2811}
{3112,1655,-2071,-1694,2384,742,-930,1829,3572,-3490,1289,-1366,-3236,3573,51,-2850,1722,-570,2188,-664,286,-1618,-3092,-2243,-1414,-3057,1029,1165,-3413,-2345,2359,535,2483,41,-3653,2833,-981,-3982,3197,-3519,734,-2001,-65,-212,-3533,2892,2481,-1579,2617,-2487}
Returns: "WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWW"

completely random placements

{4000,3999,3998,3997,3996,3995,3994,3993,3992,3991,3990,3989,3988,3987,3986,3985,3984,3983,3982,3981,3980,3979,3978,3977,3976,3975,3974,3973,3972,3971,3970,3969,3968,3967,3966,3965,3964,3963,3962,3961,3960,3959,3958,3957,3956,3955,3954,3953,3952,3951}
{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}
Returns: "BWBBWBBWBBBBBWBBBBBWBBWBBWBBBBBWBBBBBWBBBBBWBBBBBW"

large orthogonal case

{4000,3999,3998,3997,3996,3995,3994,3993,3992,3991,3990,3989,3988,3987,3986,3985,3984,3983,3982,3981,3980,3979,3978,3977,3976,3975,3974,3973,3972,3971,3970,3969,3968,3967,3966,3965,3964,3963,3962,3961,3960,3959,3958,3957,3956,3955,3954,3953,3952,3951}
{4000,3999,3998,3997,3996,3995,3994,3993,3992,3991,3990,3989,3988,3987,3986,3985,3984,3983,3982,3981,3980,3979,3978,3977,3976,3975,3974,3973,3972,3971,3970,3969,3968,3967,3966,3965,3964,3963,3962,3961,3960,3959,3958,3957,3956,3955,3954,3953,3952,3951}
Returns: "WBWBBBWBWBBBWBWBWBWBWBBBWBWBWBWBWBBBWBWBWBWBWBBBWB"

large diagonal case

{-10}
{0}
Returns: "B"

Note that x[i] and y[i] can be negative.

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

Coding Area

Language: C++17 · define a public class ErrantKnight with a public method string whoWins(vector<int> x, vector<int> y) · 75 test cases · 2 s / 256 MB per case