CHEFB - Editorial

editorial
, , ,
1

Problem link:

[contest][1]
[practice][2]

Difficulty :

Easy

Pre-requisites :

None

Problem:

Given n numbers, you have to make all the numbers equal to one in minimum number of moves. Only operation allowed is to take a subset of numbers and divide all of them by a prime p if their gcd is divisible by p.

Explanation

Let us first solve the problem when all the numbers are of the form p ei where p is a prime number.
Note that in this case, you will try to divide the selected number by p.

What is the lower bound on minimum number of moves which will be required ?
Lower Bound on minimum number of moves required will be max(ei) for all i.

Can you prove that the above lower bound is the optimal solution ?
Yes, this is a greedy strategy in which we take all numbers in subset which are divisible by p.

Can you extend this algorithm for the original problem ?
Yes, find the sum of the maximum degree of all prime numbers in the factorisation of all numbers.
Proof is very easy and left as an exercise for the reader.

#factorisation of a number
As all numbers are less than 106, we can find all prime numbers less than 103 using sieve or simple brute force.
Then for factorising any number we will iterate over all prime factors which are less than square root of the number because there can’t be 2 factors which are greater than square root of the number.

You can also use sieve method. For knowing more about this method, please visit following nice blog entry by praveendhinwa.

Subtask:

Subtask 1:
We just have to check for primes 2 and 3 only as each number is less than or equal to 3.

Subtask 2:
O(N) factorisation will pass.

Subtask 3:
You can use one of the methods explained in the previous section.

Some Interesting Reads

Sieve Method for Factorisation

Setter and Tester Solutions:

[setter][3]
[tester][4]
[1]: http://www.codechef.com/LTIME16/problems/CHEFB
[2]: http://www.codechef.com/problems/CHEFB
[3]: http://www.codechef.com/download/Solutions/LTIME16/Setter/CHEFB.cpp
[4]: http://www.codechef.com/download/Solutions/LTIME16/Tester/CHEFB.cpp

1 Like
2

Solution links are not working properly please check

1 Like
3

My solution using sieve was TLEing for Testcase 1 and Testcase 3.

Click here to view solution.

What am I doing wrong?

P.S. - I also used fast IO for this submission, yet TLE.

4

You only need to find out primes till 10^3 your sieve finds upto 10^6

5

@anta0 has found primes till 10^6 too - http://www.codechef.com/viewsolution/4907458

Also, why should finding primes till 10^6 TLE?

6

The complexity of the SOE is O(n(logn)(loglogn)) and that gives ~ 8*10^7 for n = 10^6 which is most probably too high here.

7

@thezodiac1994 with the right implementation you can get 10^6 seive run cause O(n(logn)(loglogn)) for 10^6 given 5e6 not 8e7

8

yep same mistake I was doing, finding primes upto 10^6.

9

Can anyone tell me whats wrong in my code? I got WA for the last 2 subtasks.
http://www.codechef.com/viewsolution/4911280

My solution is as follows: Find the maximum power in the factorization of each number of every prime number. Now add all these max. powers. The function pow2(int,int) is used to calculate the maximum power of prime p that can divide a given number. The array p1[] is used to store the maximum power for all primes in the array p[].

2 Likes
10

The number <= 10^6 itself can be a prime.

3 Likes
11

Yeah. Lol. Didn’t even think of that!

12

@chalubhalu there are 78000 primes below 10^6 checking all of them for each iteration of n will give complexity 7.8*10^9. @wittyceaser @anta0 's sieve finds prime factors till 10^3 only. Finding Primes does not take much time checking the divisibility of them with each number does.

13

also complexity of SOE is nloglogn

14

@chalubhalu - An iteration test on the standard implementation gave roughly 4e6. The O notation gives 8e7 and that is correct because it is supposed to be the O notation and not Θ notation.

@wittyceaser - 4e6 shouldnt be a problem. So what might be the problem is that you are running the main loop for all the primes in the 10^6 mark. Since there are ~ 8e4 primes and you are checking each prime with each element, given Nmax=10^5 in the first and third sub tasks, your respective calculations become 8e9 - which is surely high.

The second one has Nmax=10 and hence the AC I believe.

15

For each element there will be log N operations at max since we are dividing with primes at each step. Hence, sieve() is performed in NloglogN, And approximately N*log(10^6) in worst case, which would be well under the limit. A couple of small changes gave me AC, with the same method.

16

What I want to point out is that never will we be multiplying all 8e4 primes, as the limit on a[i] is 10^6.

17

Even I cauclated primes till 10^6 using sieve but I got 50 points. http://www.codechef.com/viewplaintext/4919500

18

Can someone please tell me why my solution is giving WA for subtask 3? My code http://www.codechef.com/viewsolution/4918838

19

@wittyceaser
The point of log N factors is apt. However consider this - if all elements are primes in range ~ 10^6 (repetitions allowed)- then your loop was checking for all prime factors up to the number i.e ~ 8e4 factors would have been checked for each element in the worst case and N*8e4 has to time out regardless of log N factors - unless of course you modify the things.

20

@thezodiac1994 - Yes, I understood that mistake and hence stored the smallest prime factor for all integers upto 10^6 as precomputation, in the soln that got AC.

1 Like