10853 - Pablito nailed a nail

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Dmytro Korzhyk
New poster
Posts: 8
Joined: Sat Dec 20, 2003 12:57 pm
Location: Duke University, NC

10853 - Pablito nailed a nail

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

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

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
New poster
Posts: 24
Joined: Sun Oct 03, 2004 10:03 am

I not understand exactly...

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

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
New poster
Posts: 8
Joined: Sat Dec 20, 2003 12:57 pm
Location: Duke University, NC

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 :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

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

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

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

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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

10853 (Pablito nailed a nail)

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

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
New poster
Posts: 11
Joined: Wed Oct 04, 2006 9:16 pm

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.

Post Reply

Return to “Volume 108 (10800-10899)”