10853 - Pablito nailed a nail

Dmytro Korzhyk · Post by **Dmytro Korzhyk** » Sat May 21, 2005 3:31 pm

Could anyone tell me an idea how to solve this problem?

Per · Post by **Per** » 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).

Victor Barinov · Post by **Victor Barinov** » Sat May 21, 2005 11:39 pm

Can you describe your solution in detail? What do you mean when say O(1)? Thanks!

Per · Post by **Per** » 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.

Dmytro Korzhyk · Post by **Dmytro Korzhyk** » Mon May 23, 2005 11:44 am

Thanks, Per
With your hint, I found exactly the same formula, without reading the spoiler

Abednego · Post by **Abednego** » Wed May 25, 2005 7:22 am

Ahhh! I missed the non-empty condition during the contest. Thanks.

vivander · Post by **vivander** » 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.

gagern · Post by **gagern** » 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.

temper_3243 · Post by **temper_3243** » 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

sclo · Post by **sclo** » 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.

lost · Post by **lost** » 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.

OJ Board

10853 - Pablito nailed a nail

10853 - Pablito nailed a nail

I not understand exactly...

10853 - Inputs & outputs for this problem

10853 (Pablito nailed a nail)