JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
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 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
How would this problem be solved if a "jump" only went over one checker?
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 <string>
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
]
RSS