CBALLS - Editorial

PROBLEM LINK:

Practice
Contest

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.

SAMPLE SOLUTIONS:

Author
Tester
Editorialist

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;
    }

Please Explain this

1 Like

What’s wrong in this solution, same approach.

I was very disappointed after my solution got AC; There should have been extra constraints mentioned for this problem. I wasted a lot of time thinking for a better approach than to try out all primes less than 10,000.

There are around 1000 primes less than 10,000; so theoretically I can always create a test (subtask #2) which will time out if I try out all primes.
If this is not possible…can anyone justify this?

1 Like

Do not have time to look at solution mentioned in editorials. But an alternative is to first add balls to buckets such that the array is in non-decreasing order:

for(i <- 1 until N){

  if(arr(i) < arr(i-1)){ 

     ans += (arr(i-1) - arr(i)) 

     arr(i) = arr(i-1) 

  } 

}

after that you can simply try out all primes as mentioned in editorials:

p = 0

do{

prime = primes(p) 

var toAdd = getToAdd(arr, prime, min) 

min = Math.min(toAdd, min) 

p += 1 

}while(prime < max && p < primeCount)

ans += min

The question gets ac without the sieve also. Skipping all multiples of 2 after 2 will reduce it to be within the time limit. So, setter may have adjusted the constraints accordingly.

1 Like

Although such questions are discouraged because you are supposed to debug your code yourself but it seems you have tried a lot, here is one bug:

You are not at all considering to ensure the final sequence of buckets contains balls in increasing order.
Following test case gives output 0 as per your code:

1

3

3 2 1

Do read problem statements carefully!

Many submissions which have 0.00 time fail on this test case.

1

4

18 19 19 19

Because they have not checked for all primes

I have tried my best but unable to understand why my solution at
https://www.codechef.com/viewsolution/9124436 shows wrong answer, can i get at least one failed case please.

1

1

10

Answer - 0

even i wasted a lot of time thinking for a better solution. i thought 1229(no of primes) * 10000(n) * 10(test cases) ie O (10^8) would give TLE.

Python implementation that yields all but 1 correct answers

I got just one WA for my submission in all test cases, can anyone point out a possible test case where my code failed.

The algorithm was as follows-

  1. set the sequence in non-decreasing order.
  2. check for all 1s and make them 2, count the required balls from step 1 to 2 called “count”.
  3. Lets just call : “ans1” <- number of odds in the list.(at this point)
  4. traverse the sequence to find the most common prime. that divides most number of elements
  5. set all numbers that aren’t it’s factor to the next multiple
  6. All calculations made in 5. are called “ans2”
  7. print(min(ans1,ans2)+count)

Any doubt regarding approach’s fallacy, correctness is most welcomed.

1

4

8 9 9 9

can someone bring out a case where my code might fail
https://www.codechef.com/viewsolution/9108688

I dont know at what test case my code could go wrong

@dushsingh1995 works fine for it, required ans =1, code’s o/p =1.

testcases were damn weak. The maximum gcd in subtask2 was less than or equals to 5000.

So, the extreme brute force of O(5000 * N) easily passed.

Here’s my brute solution for which I got 100 points.

https://www.codechef.com/viewsolution/9159473

1 Like

Test case are dam weak…
Considering the worst case complexity O(10^7) *10 =O(10^8) Test case can be designed so that TLE can happen if we go with this approach.

My observation can solve in almost O(n) time.

observation:-
Ans can never be >n if sequence is non decreasing.(as we can simply make all odd terms even so that gcd will be 2).

To make the sequence non decreasing at the time of input I added the difference between last term and current term in current term and increased answer by difference.

As soon as i find the ans>n i discard that prime no. and proceed further.

here is the link of my solution.

https://www.codechef.com/viewsolution/9097438

To discard/delete a prime no. use list as deletion is 0(1) time.

Was not submitting the problem because i thought that 1229(no of primes) * 10000(n) * 10(test cases) ie O (10^8)
would give TLE.
But after seeing a lot of submissions ,I submitted and surprisingly it passed.
Still curious to know if anybody did the problem in O(N).

my solution failed in only 1 subtask #7 any idea how ? solution

@s1b2312

current_multiple = ((A[j] + i - 1)/i) * i;

This equation assigns multiple of i >= A[j] to variable current_multiple (To make non decreasing sequence).