PROBLEM LINK:Author: Amit Pandey 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 nondecreasing sequence and the GCD of all of them is strictly greater than 1. EXPLANATION:Subtask 1
Subtask 2 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:
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".
asked 02 Jan '16, 01:20

Weak tests again! _ Got AC by testing all numbers till sqrt(n)! :P answered 12 Jan '16, 20:55

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 nondecreasing sequence.
Please Explain this answered 11 Jan '16, 15:26
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 nondecreasing order: for(i < 1 until N){
} after that you can simply try out all primes as mentioned in editorials: p = 0 do{
}while(prime < max && p < primeCount) ans += min
(11 Jan '16, 16:48)
@s1b2312
(12 Jan '16, 17:16)

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

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. answered 11 Jan '16, 22:32

What's wrong in this solution, same approach. answered 11 Jan '16, 16:01
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)

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

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

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
Any doubt regarding approach's fallacy, correctness is most welcomed. answered 11 Jan '16, 20:50
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)

can someone bring out a case where my code might fail I dont know at what test case my code could go wrong answered 11 Jan '16, 21:59

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

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

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.
<error>  Thanks answered 18 Jan '16, 05:24

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
