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 Div1 250 short solution
 Div1 250 short solution | Reply Can someone please explain the short and linear solution used by Petr and many others? Thanks
 Re: Div1 250 short solution (response to post by vasja_p) | Reply All moves toggle parity of checkers configuration, so all you need is to determine if initial position and final position (no checkers) have the same parity.
 Re: Div1 250 short solution (response to post by vasja_p) | Reply How would this problem be solved if a "jump" only went over one checker?
 Re: Div1 250 short solution (response to post by venco) | Reply I thought since the last digit always reset to 0 ".", so both init position and end position are even number, so they are always the same parity. What am I missing?Thanks.
 Re: Div1 250 short solution (response to post by jacksuyu) | Reply I think he meant parity in a different sense. If you colour every other position "black" (such that the special, last position is "white"), then every move changes the number of occupied "black" positions by +- 1, so the parity of this number switches every move. This colouring is what venco meant by "checkers configuration" (I think).
 Re: Div1 250 short solution (response to post by vasja_p) | Reply Okay, venco, you're on: 62(?) characters seems way too many for me.#include using namespace std;class EllysCheckers {public: string getWinner(string b) { int L=b.size(),p=0; for (; L>1; ) p ^= b[L-=2]; // assume ASCII return p&1?"YES":"NO"; }};[ETA: - Hah! I didn't know I could use string::size() instead of ::length(); - ASCII comment- '.' => 46][ETA2:- replaced >46 with later &1][ETA3:- moved L declaration to single int][ETA4:- moved & expanded ASCII/EBCDIC comment][ETA5:- removed EBCDIC claim; it won't work][ETA6:- ; => ,- moved comment back]
 Forums Algorithm Matches SRM 534 Div1 250 short solution Previous Thread  |  Next Thread