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]: CodeChef: Practical coding for everyone
[2]: CHEFB Problem - CodeChef
[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

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
5

Can someone please tell me why my solution is giving WA for subtask 3? My code CodeChef: Practical coding for everyone

6

can we solve it by findind d lcm and den calulating total prime factors, which approach can solve it in better runtime. plz help

7

Yes i also tried the problem by finding the lcm of all the numbers and then calculated the no. of prime factors of the lcm of all the numbers… but it gives WA … how it is wrong can anybody explain…plz ??

1 Like
8

Hi,

I have used the same approach as described in the solution, and getting correct answer for the first task. But I am getting incorrect answer for 2nd and 3rd tasks. Could someone take a look as to what would have went wrong in my approach? I have generated lot of random testcases for the 2nd task and compared solution in editorial to my solution and am getting the same answer for all the tests. I really request someone to please take a look and let me know.
http://www.codechef.com/viewsolution/4945527

Thanks

9

The following link is my code:

http://www.codechef.com/viewsolution/5480907

It’s resulting in a TLE for the last subtask. Could someone please suggest some ways to optimize this to get it accepted within the time limit? I have exactly followed the method described in the editorial, so it is my factorization technique (brute force sieve method as mentioned in editorial only :frowning: ) which is far too long I guess.

Or is trial division redundant in this problem and I have to resort to Pollard Rho method?

10

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

11

@anta0 has found primes till 10^6 too - CodeChef: Practical coding for everyone

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

12

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.

13

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

14

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

15

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

3 Likes
16

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

17

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

18

also complexity of SOE is nloglogn

19

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

20

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.