SRM 577 div2

I solved all 3, and placed 7th in div2.

p1000 is worth some thoughts. Given an int arr[] with 50 elements, each no more than 10^5, find number of elements to insert so that no two adjacent numbers have gcd > 1 when sorted.

First attempt: is one insertion always enough?
The problem setter is friendly and give case 1 showing the claim is false.

Second attempt: is two insertion always enough?
The answer is yes, and here is why. (UPDATE, apparently the proof is very difficult and I do not know one, although you can write a program to check the claim for the range of numbers, 1 to 10^5)

Let a and b be two adjacent numbers, and first we run all numbers from a+1 to b-1 to see if one of them is coprime with both a and b, if yes we are done and need to insert only one element. Otherwise we claim that a+1 and b-1 suffices to make a, a+1, b-1, b adjacent coprime. Note that since gcd(a,b) > 1, we must have b-a >= 2, and since no number from a+1 to b-1 is coprime with both a and b, we actually have a+1 < b-1.

Now comes the proof that a, a+1, b-1, b are adjacent coprime.
Since we know that every number from a+1 to b-1 have some gcd > 1 with either a or b. We can group them according to this:

class b shares gcd > 1 with b and class a shares gcd > 1 with a, and every number from a+1 to b-1 must fall into one of the two classes. Note also that gcd(a, a+1) = 1, as is gcd(b, b-1) = 1

class b: a+1, b-2, ...
class a: b-1, a+2, ...


Not finished, but checking all a,b=1 to 10^4 works with a+1, b-1

The intended solution, according to mystic, is also cryptic. The observation is that if B - A is at least 504 = 72 * 6, then you can find one prime between A and B and B is not divisible by that prime. This is based on the observation that for numbers less than 10^5, prime gaps are no more than 72. Then you can work on the case B < A + 504 and this is much more manageable.