10399 - Optimus Prime

[EZE]

We've thought about this question and have gotten nowhere! There have already been 4 submissions that were correct (out of 4!!!)... however, this problem seems far from trivial! Does anybody have a clue as to a good way to solve this problem?

[Nak]

I used dynamic programming to solve this problem. Perhaps not the fastest way but it worked. A situation with some c and n is a winning situation if there is a number i between 1 and n so that c+i is prime and the situation with the counter = c+i is _not_ a winning situation, if there is no such number you loose. Simply implementing this recursively is too slow, but with memoization it works.

[gvcormac]

What is the end condition for your algorithm? Primes separated by n? You'll be searching a long time, even with memoization. Did you really get AC with this approach? There's something you're not telling us.

Here's a hint: don't look to onstruct a strategy. Search for existence of a strategy.

[Nak]

Well yes, if there is no prime between c and c+n there is no such number and hence you loose. I admit I assumed c would not get bigger than 1000000. And yes i did get AC, perhaps i was just lucky

[Yarin]

Huh?? c can get as big as 1693182318746371!! For a list of all maximal prime gaps, check out

http://www.utm.edu/research/primes/notes/GapsTable.html

Of course, I don't think that will help you very much in solving the problem...

[SnapDragon]

Yes, assuming a bound of 1000000 is not a safe assumption, and you did indeed have a little luck in getting the right answers; 1000000 is provably not deep enough to be sure of the correct first move. Oh well. As Yarin pointed out, the game itself will play for far too long to calculate fully... but there are actually good reasons why you can limit the search. (My program stops only when it knows it has found an answer)

[Adrian Kuegel]

This problem is really interesting. First I used the method with simulation with primes up to 1000000, then I found the better solution by following the strategie and breaking if I knew the solution. But there remained a problem: How can I decide if there remains only one possible value that this value is not a winning position for A? I had to make special cases (for example for 172) to get accepted again.
Here are some values that could be added to the input so that no wrong solution gets Accepted (some of the values where my two solutions differ):
608 - 609
626 - 627
682 - 683
780 - 783

[SnapDragon]

You shouldn't need any special cases to test when B wins - just think of it as giving A an extra option on the first move of picking 0, and then A always wins.

I didn't give a whole lot of cases that were 500+, because I didn't want to penalize solutions that searched a bit too slowly. (I'm firmly against questions that require constant-factor improvements to run in time) It didn't occur to me that you could sneak by with a "probably correct" solution, but that's a neat approach. I don't think it would necessarily help to put in the values that your specific program got wrong, because they're pseudorandom (and very dependent on the cutoff point). And the further you go, the higher your probability of getting the right answer.

If I was smart (which, sadly, I wasn't), I would have put in the cases that require the longest searches: 829-830, 862-863, 924-925, 954-955, 996-997. Ah well.

Incidentally, the highest number I've found for which B wins is n=10889. Can anyone do better? (You may have to search past the limit of ints to find the next one)

[Adrian Kuegel]

You shouldn't need any special cases to test when B wins - just think of it as giving A an extra option on the first move of picking 0, and then A always wins.

Thanks for the hint. Before I assumed that A always wins if 172<n<=1000, now I know it from computation :-)

[Grzesiek]

Hi, I confess I don't understand what strategie you are talking
about. If I understand well the problem the game ends when
one of the players reaches the position C, such that the next
valid (prime) is C[i+1] > C+n. My first guess was to
find such a gap and go back the way which is optimal for the
winner. This seams to be not feasible in the light of enormous
values of C for required n.
I don't see any chance to know who is the winner before
approaching to the end of the game. You have found, as I see,
some method for that.
Adrian, could You please say something more how to understand:
"following the strategie and breaking if I knew the solution."

[Adrian Kuegel]

Imagine you would know where the first gap between two primes becomes
greater than n. Then as the beginning player you have the goal that you
are not in this position, but that the other player is in this position.
That means if you can make your move and you are <=n away from this
number, you can complete and get the prime number where the gap begins
(therefore you have won). This is only possible if the other player is
>n away but after his move you are <=n away.
That means that if you want to win, the second players moves must always
be with numbers > n away from each other up to the last prime where the
gap begins, and from the first prime after a number where second player
moves, the distance has to be <=n to the next number where second player
moves.
You have to make some kind of bfs starting with all possible
starting moves.
During the search you will see, that sometimes there is no next possible
prime that has all the properties described above and you can stop
searching for the actual number. Sometimes there is more than one
possible next prime that has all the properties, continue the search for
all next primes.
If only one starting number remains, you have found the answer.

[Grzesiek]

Adrian, thanks for the idea. I did follow it and finally got
accepted. However I am not sure that answers of my program
must be correct. I use primes up to 4 milions - this ensures
that for n<=1000 there is no such ambiguous situation that
more than two starting points lead to the end of range of primes.
I think that it doesn't matter if there is only one path escaping
beyond the max. prime, or there are more such paths. Even one
makes that we can not be sure - this path can as well be succesfull,
as it can terminate somewhere in the middle between our
max. prime and final position.
It looks to me that our success (acceptance) is only thanks to
the fact that our judge probably used similar alghoritm.
Can anybody prove that this alghoritm is correct?

[Adrian Kuegel]

I think that it doesn't matter if there is only one path escaping beyond the max. prime, or there are more such paths. Even one makes that we can not be sure - this path can as well be succesfull, as it can terminate somewhere in the middle between our max. prime and final position.

no, because the final position is the first one that has a gap of > n. Therefore if you begin at this gap and follow the strategie to choose the first prime with distance >n, it is clear that there must be a prime in between. Therefore there must be a path, and with our algorithm that stops if only one starting point remains it is clear that this must lead to the solution.

[SnapDragon]

Here's how I thought about it when I made the problem. For each prime p, we determine the _unique_ first move for A that will allow A to force taking p. The reason that it is unique is simple: suppose A could pick both 'x' and 'y' as his first move to force taking p, with x < y. Then when A picks x, B could pick y and force taking p himself - a contradiction. And to ensure that there is ALWAYS a forcing move, pretend "A 0" is a valid first move (this is equivalent to a win for B).

So for every prime p, there is precisely one value 0 <= x <= n such that A can force taking p if and only if his first move is x. Let's call x the "forcing move" for p.

Now we can calculate this for each p. We start with the initial range of primes up to n (obviously). Then for successive p, note that the forcing move of p is the same as the forcing move of the maximum prime q that satisfies p-q > n. A just forces taking q, then B will have to take some prime between p-n and p-1, and then A can take p.

So there is an easy way to calculate the forcing move, and now all the question really asks for is the value at the (extremely large) p that is followed by a gap of size n. Of course, that's intractable for large n. But note that once a possible value of forcing move "drops out" of all the primes in a range slightly larger than n, IT CAN NEVER COME BACK. So in fact, random fluctuations will cause the forcing moves to homogenize as p gets large - the distribution of the primes serves as an effectively random perturbing factor to ensure this shakeout will happen. Further, the more primes a specific forcing move applies to, the more likely FUTURE primes will share that forcing move. So the homogenization actually occurs fairly quickly, as anyone who has solved this problem has observed.

Also, that's why you have a good chance of getting the right answer even if you don't go as far as necessary; the forcing move that will eventually win will probably already be in the majority. In fact, even if you stopped as soon as one forcing move takes over, say, 2/3rds of the primes in a range, and printed that one, you'd probably have an extremely high probability of correctness. (I haven't looked into it, so I'm not sure if there's a substantial time gain as a result)

This makes it clear that the problem is very CHAOTIC in nature; you have a bunch of forcing moves start out equally valid, and then very slight fluctuations in the prime distribution weed them out effectively randomly. It's like horse racing over the primes. I suspect that if you plotted the distribution of the "winners" over the starting range, it would be close to uniform. And there's surely no better way to predict (with certainty) the eventual winner than to simulate it. Interestingly enough, this may mean that the algorithm for this problem IS polynomial in runtime, but while we can argue it probabilistically, there may be no way to actually PROVE it. Cool, huh?

Anyway, that's probably more info than you cared to know. Heh.

[medv]

Hi everybody!

I am trying to solve 10399 problem for two weeks already,
but can't find algorithm for large n.

For small n (when gap of composites of length n are in integers),
the game can be solved efficiently. It's like Bashe game.

If, for example, n = 10. The smallest p, for which p+1,...p+n are composites, is p = 113. Then we find the largest prime which is exactly less then p - n. It is p1 = 101. (If A will say 01, B - anything, then A will say 113 and will win). Moving back in this manner, we'll get:
113 - 103 - 89 - 73 - 59 - 47 - 31 - 19 - 7, which is optimal becauses it is less then n. (If we'll get 0, then B wins)

If n is big, we must find a lot of primes. But I know, there exist some another algorithm. CAN SMB HELP ME TO FIND IT?

Regards, Michael