## 10853 - Pablito nailed a nail

Moderator: Board moderators

Dmytro Korzhyk
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?

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
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!

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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
New poster
Posts: 8
Joined: Sat Dec 20, 2003 12:57 pm
Location: Duke University, NC
Thanks, Per
With your hint, I found exactly the same formula, without reading the spoiler

Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:
Ahhh! I missed the non-empty condition during the contest. Thanks.
If only I had as much free time as I did in college...

vivander
New poster
Posts: 8
Joined: Sat May 21, 2005 2:13 am

### 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.

gagern
New poster
Posts: 7
Joined: Thu Mar 11, 2004 5:37 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
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 ?

Regards,
Terry

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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
New poster
Posts: 11
Joined: Wed Oct 04, 2006 9:16 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.