PROBLEM LINK:
Author: Amit Pandey
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy
PREREQUISITES:
Primes, Sieve of Eratosthenes
PROBLEM:
Given is an array A of numbers. We need to increase each number by a certain amount such that the numbers form a non-decreasing sequence and the GCD of all of them is strictly greater than 1.
EXPLANATION:
Subtask 1
For this subtask, we have been given that the elements in the array are positive integers smaller than or equal to 10^3. Also, the size of the array is at max 10^3. We just need to increase each element such that the array forms a non-decreasing subsequence and at the same time has GCD greater than 1. We can try each number between 1 and 10^3 as a potential GCD and change the array elements to its multiples in non-decreasing order. Here is the pseudocode of the algorithm:
let ans = infinity //variable which will store global minima
for i = 1 to 10^4
{
let current_multiple = 0
//current_multiple stores that multiple of i which the element
//under consideration must be increased to. it is initially set to 0
let temp_ans = 0
//temp_ans stores the total increase if multiples of i are used
for j = 1 to N
{
if(A[j] > current_multiple)
{
//if A[j] is greater than the current multiple of i
//then we need to take a bigger multiple. This is because we need
//a non-decreasing sequence.
current_multiple = ((A[j] + i - 1)/i) * i;
}
//accumulating the change
temp_ans += current_multiple - A[j];
}
//calculating minimum over all possible primes
ans = minimum(ans, temp_ans);
}
return ans;
Subtask 2
For this subtask, we have to make an important observation. We have been given that the elements in the array are positive integers smaller than or equal to 10^4. Also, the size of the array is at max 10^4. The \mathcal{O}(N^2) algorithm will time out.
The crucial observation is that for the numbers to have GCD greater than 1, all of them should be divisible by at least one common prime. That gives us a big reduction: we only have to check for each prime smaller than 10^4 that which prime’s multiples yield the best possible result. Since there are only 1229 primes smaller than 10^4, this method works within time limits for the given constraints. The only change from the above pseudocode is that we skip all composite i. Marking all primes under 10^4 can be done as preprocessing using Sieve of Eratosthenes. Check editorialist’s program for implementation. Here is the pseudocode of the algorithm:
prime[i] = 1 if i is prime else 0 //marked using sieve
let ans = infinity //variable which will store global minima
for i = 1 to 10^4
{
if (prime[i] != 1)
skip and go on to next i;
let current_multiple = 0
//current_multiple stores that multiple of i which the element
//under consideration must be increased to. it is initially set to 0
let temp_ans = 0
//temp_ans stores the total increase if multiples of i are used
for j = 1 to N
{
if(A[j] > current_multiple)
{
//if A[j] is greater than the current multiple of i
//then we need to take a bigger multiple. This is because we need
//a non-decreasing sequence.
current_multiple = ((A[j] + i - 1)/i) * i;
}
//accumulating the change
temp_ans += current_multiple - A[j];
}
//calculating minimum over all possible primes
ans = minimum(ans, temp_ans);
}
return ans;
The editorialist’s program follows the editorial. Please see for implementation details.
OPTIMAL COMPLEXITY:
\mathcal{O}(NP) per test case where P is the number of primes less than equal to 10^4.