xp2008

Thanks ! We can see the days we need is sumi<=P+1ap<3*ap+2=3*43*ap-1<3*43*6P, which is O(P).

To solve the question without knowing parity, we follow almost the same steps, except we change hypothesis of parity alternatively each time we go to next round. And it may take us one more round to find it, because we find it only when in the same parity.

I tried again like this, supposing we know the parity case, for example odd on first day By checking (1,3),(4,6),(7,9),..., we can check a range of (3k-1) in k days. Now I construct a sequence of numbers ai, such that an >= 3*sumi<nai we can easily verify that ai = 4i qualifies. The strategy now becomes, in the first a1=4 days, we check (-5,-3),(-2,0),(1,3),(4,6), which is a range of -5 -> 6 in the next a2 = 16 days, we check (-23, -21),(-20,-18),...(-2,0),(1,3),..,(22,24), which is a range of -23 -> 24 etc. Supposing groundhog is at P, while |6P|<ap = 4p Then after ( a1 + a2 + .. +ap ) days, the range we just checked is the range of last ap days, which is about -1.5*ap -> 1.5*ap, while the range of groundhog could be is -|P| - ( a1 + a2 + .. +ap ) -> |P|+( a1 + a2 + .. +ap ), on the other hand, we have |P|+( a1 + a2 + .. +ap ) - 1.5*ap = |P|+( a1 + a2 + .. +ap-1) - 0.5*ap < ap/6 +ap/3-0.5*ap = 0, which is to say, groundhog's range is included by our last searching range.

Apologise I considered it to be 2 days after when they come back to positive half axis, yeah, after fixing this 4K hole doesn't work for 4k day. Is this an open question or you know there's an answer ?

For 1st question, we can't guarantee to find it. Supposing groundhog knows your strategy, thus knows which hole you check next day, it can always avoid it because it has always 2 choices for next's hole.

If we know first day's parity then we can. Supposing it was odd, then I will check 1 3 4 6 1 -1 -2 -4 6 8 9 11 ... Which is to say, day 4k+1, I check 5K+1, 5K+3 day 4k+2, I check 5K+4, 5K+6 day 4K+3, I check -5K+1, -5K-1 day 4K+4, I check -5K-2, -5K-4 We can see my range is ( -5K-4, 5K+6 ) , while lim ( 5K - 4K) = lim (K) -> infinity, thus we could always find the groundhog in this case.