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 :)↵
↵
<b>quick editorial for problems A to D</b>↵
↵
problem A↵
=========↵
↵
given n and b. find a such that a + b is maximum possible. ↵
↵
b = B[0] B[1] .... B[n-1]<br>↵
a = A[0] A[1] .... A[n-1]↵
↵
sum[i] = A[i] + B[i]↵
↵
**observations**:<br>↵
since we want sum to be as large as possible we want:<br>↵
1. sum[0] to be as large as possible(hopefully 2 otherwise 1)<br>↵
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. <br>↵
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.<br>↵
our 3rd divisor(d3) should be atleast 1 + d<br>↵
and our 4th divisor(d4) should be atleast 3rd_divisor + d<br>↵
↵
if 3rd and 4th divisors are prime then our number will be equal to d3*d4.<br>↵
any number can be represented as a product of primes.<br>↵
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:<br>↵
1. always need to select the largest element of the array. why? <br>↵
2. initially I may select any element a[i] (1 <= i < 2*n) along with a[2*n] and remove them.<br>↵
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.<br>↵
for the remaining array also the observation 1 holds true.↵
↵
make a table of the elements you have in the array. <br>↵
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:<br>↵
<pre>↵
element[L1]-- delete L1 <br>↵
element[L2]-- delete L2 <br>↵
x = max(element[L1], element[L2]) new value of x↵
</pre>↵
if element[L2] was already 0 then it is impossible to delete all elements if I initially select a[i] along with a[2n]↵
↵
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.<br>↵
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**<br>↵
↵
**first check if subarray A[1:i] can be solved without the use of superpower.(1 <= i < N)**<br>↵
↵
cool, how to check?<br>↵
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.<br>↵
A[1:2] can be solved if A[1:1] can be solved and (A[2] — A[1]) <= A[3] <br>↵
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].<br>↵
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)**<br>↵
↵
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.<br>↵
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:**<br>↵
i. A[1:i-2] can be solved without superpower.<br>↵
ii. A[i+3:N] can be solved without superpower.<br>↵
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.
↵
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 :)↵
↵
<b>quick editorial for problems A to D</b>↵
↵
problem A↵
=========↵
↵
given n and b. find a such that a + b is maximum possible. ↵
↵
b = B[0] B[1] .... B[n-1]<br>↵
a = A[0] A[1] .... A[n-1]↵
↵
sum[i] = A[i] + B[i]↵
↵
**observations**:<br>↵
since we want sum to be as large as possible we want:<br>↵
1. sum[0] to be as large as possible(hopefully 2 otherwise 1)<br>↵
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. <br>↵
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.<br>↵
our 3rd divisor(d3) should be atleast 1 + d<br>↵
and our 4th divisor(d4) should be atleast 3rd_divisor + d<br>↵
↵
if 3rd and 4th divisors are prime then our number will be equal to d3*d4.<br>↵
any number can be represented as a product of primes.<br>↵
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:<br>↵
1. always need to select the largest element of the array. why? <br>↵
2. initially I may select any element a[i] (1 <= i < 2*n) along with a[2*n] and remove them.<br>↵
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.<br>↵
for the remaining array also the observation 1 holds true.↵
↵
make a table of the elements you have in the array. <br>↵
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:<br>↵
<pre>↵
element[L1]-- delete L1 <br>↵
element[L2]-- delete L2 <br>↵
x = max(element[L1], element[L2]) new value of x↵
</pre>↵
if element[L2] was already 0 then it is impossible to delete all elements if I initially select a[i] along with a[2n]↵
↵
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.<br>↵
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**<br>↵
↵
**first check if subarray A[1:i] can be solved without the use of superpower.(1 <= i < N)**<br>↵
↵
cool, how to check?<br>↵
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.<br>↵
A[1:2] can be solved if A[1:1] can be solved and (A[2] — A[1]) <= A[3] <br>↵
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].<br>↵
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)**<br>↵
↵
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.<br>↵
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:**<br>↵
i. A[1:i-2] can be solved without superpower.<br>↵
ii. A[i+3:N] can be solved without superpower.<br>↵
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.
