CBALLS - Editorial

editorial
, , , ,
6

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

7

I have tried my best but unable to understand why my solution at
CodeChef: Practical coding for everyone shows wrong answer, can i get at least one failed case please.

8

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.

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

10

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
11

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.

12

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

13

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

14

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

4 Likes
15

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

16

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

17

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

18

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!

19

1

1

10

Answer - 0

20

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.

21

1

4

8 9 9 9

22

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

23

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

24

How do you find out “the most common prime. that divides most number of elements” ? Paste your code link also

26

in the editorialist solution,he has written in the if condition that…
if(required_no < arr[i])
{
…;
}
where the required_no is the previous index element and for the array to be non decreasing one,the required_no should obviously be lesser than the next element…Can someone please clarify the issue??