CF Round 696 Editorial A-D

Revision en2, by kartik8800, 2021-01-19 19:53:20

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

adding C to D.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English kartik8800 2021-01-19 20:54:08 4 Tiny change: 'blem D\n\n**in more ' -> 'blem D\n\n### **in more '
en5 English kartik8800 2021-01-19 20:52:39 1433
en4 English kartik8800 2021-01-19 20:21:06 784 Tiny change: 'i+1] then if answer is yes:\n\nyou s' -> 'i+1] then answer is yes if:\n\nyou s'
en3 English kartik8800 2021-01-19 20:06:08 1166
en2 English kartik8800 2021-01-19 19:53:20 802
en1 English kartik8800 2021-01-19 19:42:52 882 Initial revision (published)