JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Previous Thread  |  Next Thread Forums Algorithm Matches SRM 534 Help on DIV2 - 500,
 Help on DIV2 - 500, | Reply I tried to use game solution, but it fails on the second test case. I couldn't figure out what's wrong. Here is the code:public class EllysCheckers { int N; int state[]; public String getWinner(String board) { N = board.length(); char[] bArr = board.toCharArray(); state = new int[getIndex(bArr) + 1]; /* state saves who win, 1 or 2.If 0 means undetermined */ return isWin(bArr, 1) ? "YES" : "NO"; } int getIndex(char board[]) { board[N - 1] = '.'; int v = 0; for (int i = 0; i < N; i++) { if (board[i] == 'o') { v |= 1 << (N - 1 - i); } } return v; } boolean isWin(char board[], int player) { int nextPlayer = (player + 1) % 2 + 1; int currIdx = getIndex(board); if (state[currIdx] != 0) { return state[currIdx] == player; } for (int i = 0; i <= 40; i++) { int move[] = nextMove(board, i); if (move == null) { state[currIdx] = nextPlayer; return false; } else { int type = move[0]; int idx = move[1]; boolean win = false; if (type == 0) { board[idx + 1] = 'o'; board[idx] = '.'; win = !isWin(board, nextPlayer); board[idx] = 'o'; board[idx + 1] = '.'; } else if (type == 1) { board[idx + 3] = 'o'; board[idx] = '.'; win = !isWin(board, nextPlayer); board[idx] = 'o'; board[idx + 3] = '.'; } if (win) { state[currIdx] = player; return true; } } } state[currIdx] = nextPlayer; return false; } int[] nextMove(char board[], int order) { board[N - 1] = '.'; int idx = 0; for (int i = 0; i < board.length - 1; i++) { if (board[i] == 'o' && board[i + 1] == '.') { if (order == idx) { return new int[] { 0, i }; } idx++; } } for (int i = 0; i < board.length - 3; i++) { if (board[i] == 'o' && board[i + 1] == 'o' && board[i + 2] == 'o' && board[i + 3] == '.') { if (order == idx) { return new int[] { 1, i }; } idx++; } } return null; }}
 Re: Help on DIV2 - 500, (response to post by jacksuyu) | Reply Ok, I found the error.It is this line: int nextPlayer = (player + 1) % 2 + 1;If player = 1, then nextPlayer = 1, which will have you always return true. What you should have had was int nextPlayer = (player % 2) + 1;
 Re: Help on DIV2 - 500, (response to post by Cricicle) | Reply Thank you so much!!!!
 Forums Algorithm Matches SRM 534 Help on DIV2 - 500, Previous Thread  |  Next Thread