You are not logged in. Please login at www.codechef.com to post your questions!

×

CBALLS - Editorial

0
1

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

This question is marked "community wiki".

asked 02 Jan '16, 01:20

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 10 Mar '16, 13:20

admin's gravatar image

0★admin ♦♦
19.8k350498541


Weak tests again! -_- Got AC by testing all numbers till sqrt(n)! :P

link

answered 12 Jan '16, 20:55

xariniov9's gravatar image

6★xariniov9
1.1k18
accept rate: 10%

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

link

answered 11 Jan '16, 15:26

s1b2312's gravatar image

3★s1b2312
111
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★

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?

link

answered 11 Jan '16, 16:41

akumar3's gravatar image

3★akumar3
1426
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) mukul_chandel2★

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.

link

answered 11 Jan '16, 16:56

aman935's gravatar image

3★aman935
1201
accept rate: 0%

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

link

answered 11 Jan '16, 22:32

code_hard123's gravatar image

6★code_hard123
7818
accept rate: 7%

What's wrong in this solution, same approach.

link

answered 11 Jan '16, 16:01

saurabhsuniljain's gravatar image

2★saurabhsuniljain
8115
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★

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

link

answered 11 Jan '16, 17:56

dushsingh1995's gravatar image

4★dushsingh1995
98314
accept rate: 11%

edited 11 Jan '16, 17:57

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.

link

answered 11 Jan '16, 19:08

nupurbaghel's gravatar image

4★nupurbaghel
1
accept rate: 0%

1

1

10

Answer - 0

(11 Jan '16, 19:16) dushsingh19954★

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.

link

answered 11 Jan '16, 20:50

thewizard101's gravatar image

4★thewizard101
11
accept rate: 0%

edited 11 Jan '16, 20:53

1

4

8 9 9 9

(11 Jan '16, 21:39) dushsingh19954★

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

(11 Jan '16, 22:19) thewizard1014★

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★

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

link

answered 11 Jan '16, 21:59

prak001's gravatar image

3★prak001
0
accept rate: 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.

link

answered 12 Jan '16, 00:08

tushar_63's gravatar image

2★tushar_63
5538
accept rate: 0%

edited 12 Jan '16, 00:09

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).

link

answered 12 Jan '16, 02:20

akshayv3's gravatar image

3★akshayv3
1578
accept rate: 4%

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

link

answered 12 Jan '16, 07:39

debverine's gravatar image

2★debverine
112
accept rate: 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. <error>AccessDenied<message>Access Denied</message><requestid>8802F77EEBE2F550</requestid><hostid>YHEZSFLOLlylKAg2Otsl4Iarz4Rgr/ldqRuwrH7pwc2Syh85mBpAL84Dupxx6C+pLHCW0Z5cBLA=</hostid></error>

-- Thanks

link

answered 18 Jan '16, 05:24

aswinsiva's gravatar image

3★aswinsiva
0
accept rate: 0%

The damn linked solutions don't work YET AGAIN. @Codechef: What's wrong with you guys? Do you deliberately like annoying participants??

link

answered 29 Feb '16, 04:12

esemzv's gravatar image

3★esemzv
212
accept rate: 0%

edited 29 Feb '16, 04:20

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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