Hello codeforces

I liked solving today's contest(on pen and paper :p) and I am sharing the solutions for problems A to D. hope this might help some of you :)

quick editorial for problems A to D

problem A

given n and b. find a such that a + b is maximum possible.

b = B[0] B[1] .... B[n-1]
a = A[0] A[1] .... A[n-1]

sum[i] = A[i] + B[i]

observations:
since we want sum to be as large as possible we want:
1. sum[0] to be as large as possible(hopefully 2 otherwise 1)
2. an integer with more digits is large, so we would like to retain all digits.

to retain all digits make sure sum[i] != sum[i-1]

go for a brute force to determine a.
find A[0] with no constraint. then find A[i] such that A[i] is not equal to A[i-1] and A[i] is as large as possible(2 > 1 > 0).

problem B

we need to find num such that num has atleast 4 divisors and the divisors have atleast a space of d among them.

any number > 1 has atleast two divisors: 1 and the num itself.
our 3rd divisor(d3) should be atleast 1 + d
and our 4th divisor(d4) should be atleast 3rd_divisor + d

if 3rd and 4th divisors are prime then our number will be equal to d3*d4.
any number can be represented as a product of primes.
num = d3*d4 where both d3 and d4 are prime is the best possible choice.

why? please provide good mathematical proof else I will provide a proof after writing other solutions.

so simply select d3 as the smallest prime number greater than 1 + d and select d4 as the smallest prime number greater than d3 + d.

final answer = d3*d4

problem C

sort the array.

observations:
1. always need to select the largest element of the array. why?
2. initially I may select any element a[i] (1 <= i < 2*n) along with a[2*n] and remove them.
3. thus x = a[i] + a[2n]

let us I say I selected the integers a[2n] and a[i] in the first move to delete. so ** x** is fixed.
for the remaining array also the observation 1 holds true.

make a table of the elements you have in the array.
map<int,int> element. where element[i] = j means that i appears j times in your remaining array.

to perform an operation you will select the largest element of the array i.e. L1, now you need an element from the array equal to L2 such that L1 + L2 = x

if element[L2] != 0 then you are good. and you should do:

 element[L1]-- delete L1 
 element[L2]-- delete L2 
 x = max(element[L1], element[L2]) new value of x 

Simply try this for all possible i. that is for all possible initial element selected along with a[2n]

adding D in a while.