A Chessboard Game
A Chessboard Game
+ 11 comments Editorial seemed very overly complex. This is easily solved by:
public static String findWinner(int x, int y){ x=x%4; y=y%4; if((y==0)||(y==3)||(x==0)||(x==3)) return "First"; return "Second"; }
+ 2 comments I drowed a table 15x15 starting from 0,0 to 14,14. It represents what player1 does. It looks like this :
W -> win ; L -> lose "LLWWLLWWLLWWLLW", "LLWWLLWWLLWWLLW", "WWWWWWWWWWWWWWW", "WWWWWWWWWWWWWWW", "LLWWLLWWLLWWLLW", "LLWWLLWWLLWWLLW", "WWWWWWWWWWWWWWW", "WWWWWWWWWWWWWWW", "LLWWLLWWLLWWLLW", "LLWWLLWWLLWWLLW", "WWWWWWWWWWWWWWW", "WWWWWWWWWWWWWWW", "LLWWLLWWLLWWLLW", "LLWWLLWWLLWWLLW", "WWWWWWWWWWWWWWW", ; you should drow it by walking on its diagonals like that : 0,0 -> 0,1 -> 1,0 -> 0,2 -> 1,1 -> 2,0 -> ... till end. i hardcodated it becouse i was lasy to implement it. i solve it like a DP problem :D
+ 2 comments My C solution with O(1) time complexity
#include<stdio.h> int main() { int t,x,y; scanf("%d",&t); while(t--) { scanf("%d%d",&x,&y); x=x%4; y=y%4; if((x==0) || (x==3) || (y==0) || (y==3)) printf("First\n"); else printf("Second\n"); } return 0; }
+ 0 comments A lot of posts show a gimmick solution based on the fact that a pattern was found. What if there was not such an easy to observe pattern? Here is a proper recursive solution in Javascript:
const moves = [[-2, 1], [-2, -1], [1, -2], [-1, -2]]; function whoWins(x, y, player) { if (x < 1 || y < 1) // The last player did not have a legal move return player; // Only one path needs to return a win for the current player since he will play optimally return (moves.some((val) => { return whoWins(x + val[0], y + val[1], (player + 1) % 2) === player; })) ? player : (player + 1) % 2; } // Complete the chessboardGame function below. function chessboardGame(x, y) { return whoWins(x, y, 0) === 0 ? "First" : "Second"; }
+ 0 comments The editorial for this problem is both needlessly complex and provides a sub-optimal recursive solution for this problem in O(n^2) when it can be solved far more simply in O(1)
Start by mapping out the win states for the first and second players. Starting at the top left, the second player (S) wins in the square of 4 spaces by default, since first player (F) has no moves. From there propogate outwards and mark each square with the approprite win state.
0 1 2 3 4 5 6 7... 0 S S F F S S F F 1 S S F F S S F F 2 F F F F F F F F 3 F F F F F F F F 4 S S F F S S F F 5 S S F F S S F F 6 F F F F F F F F 7 F F F F F F F F* . . # *if board were 8x8, this corner would be S .
The pattern becomes clear, if we shift the indicies down by 1 (start at 0), then the second player only wins if the coin starts at a space where (x//2)%2==0 and (y//2)%2==0, otherwise the first player wins. The code is relatively trival. (Note that there is one corner case that could arise at the bottom right corner of the board depending on the size of the board, but in the 15x15 case this is not an issue).
t = int(input()) for _ in range(t): x, y = list(map(lambda x: int(x)-1, input().split())) print('Second' if x//2 % 2 == 0 and y//2 % 2 == 0 else 'First')
Sort 59 Discussions, By:
Please Login in order to post a comment