×

# CBALLS - Editorial

Author: Amit Pandey
Tester: Antoniuk Vasyl and Misha Chorniy
Editorialist: Pushkar Mishra

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:

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;


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:

This question is marked "community wiki".

1.3k156581
accept rate: 4%

19.8k350498541

 4 Weak tests again! -_- Got AC by testing all numbers till sqrt(n)! :P answered 12 Jan '16, 20:55 1.1k●1●8 accept rate: 10%
 1 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 answered 11 Jan '16, 15:26 3★s1b2312 11●1 accept rate: 0% 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 (11 Jan '16, 16:48) akumar33★ @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). (12 Jan '16, 17:16) konfused4★
 1 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? answered 11 Jan '16, 16:41 3★akumar3 142●6 accept rate: 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. (11 Jan '16, 20:26)
 1 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. answered 11 Jan '16, 16:56 3★aman935 120●1 accept rate: 0%
 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 answered 11 Jan '16, 22:32 781●8 accept rate: 7%
 0 What's wrong in this solution, same approach. answered 11 Jan '16, 16:01 81●1●5 accept rate: 0% 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! (11 Jan '16, 17:00) akumar33★
 0 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 answered 11 Jan '16, 17:56 983●14 accept rate: 11%
 0 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. answered 11 Jan '16, 19:08 1 accept rate: 0% 1 1 10 Answer - 0 (11 Jan '16, 19:16)
 0 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- set the sequence in non-decreasing order. check for all 1s and make them 2, count the required balls from step 1 to 2 called "count". Lets just call : "ans1" <- number of odds in the list.(at this point) traverse the sequence to find the most common prime. that divides most number of elements set all numbers that aren't it's factor to the next multiple All calculations made in 5. are called "ans2" print(min(ans1,ans2)+count) Any doubt regarding approach's fallacy, correctness is most welcomed. answered 11 Jan '16, 20:50 1●1 accept rate: 0% 1 4 8 9 9 9 (11 Jan '16, 21:39) @dushsingh1995 works fine for it, required ans =1, code's o/p =1. (11 Jan '16, 22:19) How do you find out "the most common prime. that divides most number of elements" ? Paste your code link also (12 Jan '16, 19:01) vsp46★
 0 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 answered 11 Jan '16, 21:59 3★prak001 0 accept rate: 0%
 0 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. answered 12 Jan '16, 00:08 55●3●8 accept rate: 0%
 0 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). answered 12 Jan '16, 02:20 3★akshayv3 157●8 accept rate: 4%
 0 my solution failed in only 1 subtask #7 any idea how ? solution answered 12 Jan '16, 07:39 11●2 accept rate: 0%
 0 Can anyone see the author's sample code ? I am seeing the following: This XML file does not appear to have any style information associated with it. The document tree is shown below. AccessDeniedAccess Denied8802F77EEBE2F550YHEZSFLOLlylKAg2Otsl4Iarz4Rgr/ldqRuwrH7pwc2Syh85mBpAL84Dupxx6C+pLHCW0Z5cBLA= -- Thanks answered 18 Jan '16, 05:24 0 accept rate: 0%
 0 The damn linked solutions don't work YET AGAIN. @Codechef: What's wrong with you guys? Do you deliberately like annoying participants?? answered 29 Feb '16, 04:12 3★esemzv 21●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×303
×106
×51

question asked: 02 Jan '16, 01:20

question was seen: 4,896 times

last updated: 10 Mar '16, 13:20