Sorting is based on the points currently and all the ones with the same score are listed randomly. I will add another sort key on the score to make it better sorted :)

tourist won't be considered in this and further stages as he has already qualified. :)

Fixed :)

Given X, we can easily check whether the answer can be a multiple of X: just take all numbers modulo X and create the pairs greedily.

All X you need to check are the divisors of A[0]+A[y] for some y.

Another solution:

• Generate all divisors d of all possible A[i] + A[j]. Keep the list of (i, j) pairs that are multiples of d where 0 <  = i < j < n.
• Search for the maximal d where the graph constructed from its list of (i, j) pairs has a maximum matching (or minimum edge cover) of size n / 2.

References:

• Solution in SRM by user: jy_25
• Edge Cover

As I see it, the idea is to carefully choose the algorithm with which the largest sum will be computed. It is more or less evident that you will need to compute the probability distribution of the maximal achievable sum and the question is how to do it without introducing conditional probabilities along the way. For example, if you use partial sums, every flip of a coin influences a suffix of the array of partial sums. Therefore, assigning one variable per partial sum does not work (at least not in the straightforward way) because the variables start depending on each other and the computation even of their distributions becomes complicated, let alone of the distributions of more complicated variables such as max(s[r]) - min(s[l]), l ≤ r. Assigning a variable to every segment does not work for the same reason.

Here is what works instead. Start with the first number and add the numbers greedily while the sum stays nonnegative. If it ever becomes negative, remember the largest sum and discard all the numbers you have seen so far. Repeat until the array is empty. After processing several numbers (and before consuming the number whose turn it is now) all you have to keep track of is the sum of the not yet discarded part and the current maximal sum.

In the randomized version you can now assign a variable to each of these numbers... only to obtain nonindependent variables again. Luckily, this time there are only two of them regardless of the size of the initial array, so you can keep track of their joint probability distribution. Let p[i][s][m] be the probability that after the execution of our algorithm on the first i numbers the current sum is s and the maximal sum we have seen is m. Flipping a coin to set the sign of the number i we can compute p[i + 1][s'][m'] for all possible s' and m'. To be more precise, for an array of size n you now have 2·(n + 1) variables S_i, M_i and the joint distribution of (S_i + 1, M_i + 1) depends only on the joint distribution of (S_i, M_i) and the probability of writing a minus before the number i. This allows you to compute the joint distribution of (S_n, M_n) from which you can extract the distribution of M_n that you have been seeking all along.