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]

problem D(hint)

most crucial observation:

a[1] has only 1 neighbor and same for a[n]. try solving with this in mind.
so a[1] has to be reduced to 0 with complete help from a[2] no matter what(unless we use super power)

let us not use the super power.

after reducing a[1] with help from a[2], remaining portion of a[2] is now in a similar position: only 1 neighbor i.e. a[3]

try using superpower to swap a[i] and a[i+1] then answer is yes if:

you should be able to solve the array[1:i-2] and array[i+3:n] with only help from a[i-1] and a[i+2](precompute these values for all i). after this check if you can solve for array {some portion of a[i-1], a[i+1], a[i], some portion of a[i+2]}

i will shortly add a more detailed editorial for problem D

in more detail

first check if subarray A[1:i] can be solved without the use of superpower.(1 <= i < N)

cool, how to check?
A[1:1] can be solved if and only if A[1] is less than or equal to A[2] otherwise A[1:1] cannot be solved.
A[1:2] can be solved if A[1:1] can be solved and (A[2] — A[1]) <= A[3]
If I choose to solve A[1:1] without superpower it leaves an effect on A[2]. it reduces the value of A[2] to A[2] — A[1].
let me call this reduced_left[2] or reduced_left[i].

A[1:i] can be solved if A[1:i-1] can be solved and reduced[i-1] <= A[i]

reduced_left[i + 1]: in order to solve A[1:i] what was the value of A[i+1] reduced to.

second check if subarray A[i:N] can be solved without the use of superpower.(2 <= i <= N)

A[N:N] can be solved if and only if A[N] is less than or equal to A[N-1] otherwise A[N:N] cannot be solved.
on similar lines you will get a definition of reduced_left[i].

now answer is yes if A[1:N] is solvable assuming A[N+1] = A[0] = 0 (without use of superpower)

answer is also yes if I can swap A[i] and A[i+1] such that:
i. A[1:i-2] can be solved without superpower.
ii. A[i+3:N] can be solved without superpower.
iii. the array { reduced_left[i-1], A[i+1], A[i], reduced_right[i+2] } can be solved without superpower

try this for all i from 1 to N-1.

5. otherwise answer is no.

hope this helped.