10853 - Pablito nailed a nail
Posted: Sat May 21, 2005 3:31 pm
Could anyone tell me an idea how to solve this problem?
Page 1 of 1
Posted: Sat May 21, 2005 4:53 pm
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).
I not understand exactly...
Posted: Sat May 21, 2005 11:39 pm
Can you describe your solution in detail? What do you mean when say O(1)? Thanks!
Posted: Sun May 22, 2005 1:51 pm
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.
Posted: Mon May 23, 2005 11:44 am
Thanks, Per
With your hint, I found exactly the same formula, without reading the spoiler
With your hint, I found exactly the same formula, without reading the spoiler
Posted: Wed May 25, 2005 7:22 am
Ahhh! I missed the non-empty condition during the contest. Thanks.
10853 - Inputs & outputs for this problem
Posted: Thu May 26, 2005 9:38 am
I need lot of inputs and outputs for this problem, because I don't know why I has WA
Thanks.
Thanks.
Posted: Thu Sep 01, 2005 3:25 pm
I had a lot of WA today, too. Did you try with unsigned (C, C++) or long (Java)? This solved the problem for me.
10853 (Pablito nailed a nail)
Posted: Wed Sep 14, 2005 8:15 pm
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
Posted: Mon Sep 18, 2006 1:14 am
if A wins for any lengths in [a,b], then A would win for any lengths in [a+Bmax+Amin, b+Bmin+Amax] provided that a+Bmax<=b+Bmin.
If you have a dp solution to this problem, then it is easy to see that it works.
It's too large to dp 2^30, so we need a faster solution that does O(1) computation.
If you have a dp solution to this problem, then it is easy to see that it works.
It's too large to dp 2^30, so we need a faster solution that does O(1) computation.
Posted: Thu Oct 05, 2006 11:25 pm
// 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.