10853  Pablito nailed a nail
Moderator: Board moderators

 New poster
 Posts: 8
 Joined: Sat Dec 20, 2003 12:57 pm
 Location: Duke University, NC
10853  Pablito nailed a nail
Could anyone tell me an idea how to solve this problem?
My solution was based on observations of the kind "if the entire range [X, Y] are winning positions for player A when player A begins, then the range [X+Bmax, Y+Bmin] are losing positions for player B when player B begins". Swapping "winning" and "losing", and doing different player combinations, you get similar statements. Using these repeatedly, one of them will tell you what you want to know (in O(1) time).

 New poster
 Posts: 24
 Joined: Sun Oct 03, 2004 10:03 am
I not understand exactly...
Can you describe your solution in detail? What do you mean when say O(1)? Thanks!
I can try.
(Warning, this is a big spoiler for how to solve the problem)
We know that the range [1, Amax] is winning for A when A begins. Thus, the set [1+Bmax, Amax+Bmin] is winning for A when B begins, and the set [1+Bmax+Amin, 2Amax + Bmin] is winning for A when A begins, and so on. Repeating, we get that [1+t*(Amin+Bmax), Amax+t*(Amax+Bmin)] is winning for A when A begins, provided none of the ranges obtained during the process was empty. Doing the converse argument for when B is winning shows that these ranges are actually all winning positions for A, so it suffices to find t such that 1+t*(Amin+Bmax) <= L <= Amax+t*(Amax+Bmin), and such that none of the ranges encountered during the process is empty, which I leave as an exercise. If such a t exists, A wins, otherwise B wins.
O(1) means bounded by some constant. I was simply saying that the runtime does not depend on the five input parameters, L, Amin, Amax, Bmin and Bmax.
(Warning, this is a big spoiler for how to solve the problem)
We know that the range [1, Amax] is winning for A when A begins. Thus, the set [1+Bmax, Amax+Bmin] is winning for A when B begins, and the set [1+Bmax+Amin, 2Amax + Bmin] is winning for A when A begins, and so on. Repeating, we get that [1+t*(Amin+Bmax), Amax+t*(Amax+Bmin)] is winning for A when A begins, provided none of the ranges obtained during the process was empty. Doing the converse argument for when B is winning shows that these ranges are actually all winning positions for A, so it suffices to find t such that 1+t*(Amin+Bmax) <= L <= Amax+t*(Amax+Bmin), and such that none of the ranges encountered during the process is empty, which I leave as an exercise. If such a t exists, A wins, otherwise B wins.
O(1) means bounded by some constant. I was simply saying that the runtime does not depend on the five input parameters, L, Amin, Amax, Bmin and Bmax.

 New poster
 Posts: 8
 Joined: Sat Dec 20, 2003 12:57 pm
 Location: Duke University, NC
10853  Inputs & outputs for this problem
I need lot of inputs and outputs for this problem, because I don't know why I has WA
Thanks.
Thanks.

 Experienced poster
 Posts: 105
 Joined: Wed May 25, 2005 7:23 am
10853 (Pablito nailed a nail)
Hi,
I have no idea how to solve this problem. I have seen such kind of problem but have stuck up . I think that one should evaluate states from starting for both the players.
Can someone describe an algorithm and post some pseudo code so that it will be easier for me ?
Please post any links or tutorials associated with it.
Regards,
Terry
I have no idea how to solve this problem. I have seen such kind of problem but have stuck up . I think that one should evaluate states from starting for both the players.
Can someone describe an algorithm and post some pseudo code so that it will be easier for me ?
Please post any links or tutorials associated with it.
Regards,
Terry
// aL..aR is range in which, if playerA is on move, he can win
// bL..bR is range from which whatever playerB plays, he will end up in previous aL..aR area (thus keeping playerA in winning pos)
aL:=1; aR:=maxA; //start winning range for player A
// repeat next one untill you get aL<= L <=aR (then playerA can win) , or aL>L, then playerA can not win.
bL:=aL+maxB; bR:=aR+minB;
aL:=bL+minA; aR:=bR+maxA;
and of course, above can be written without any loop, with little math, so function that return true/false for given L and max/min values can be done with few +*/ operations.
// bL..bR is range from which whatever playerB plays, he will end up in previous aL..aR area (thus keeping playerA in winning pos)
aL:=1; aR:=maxA; //start winning range for player A
// repeat next one untill you get aL<= L <=aR (then playerA can win) , or aL>L, then playerA can not win.
bL:=aL+maxB; bR:=aR+minB;
aL:=bL+minA; aR:=bR+maxA;
and of course, above can be written without any loop, with little math, so function that return true/false for given L and max/min values can be done with few +*/ operations.