FUZZYLIN - Editorial

editorial
, , , , , ,
18

@ssrivastava990 Bro i think your GCD calculation time complexity is O(n^2) , that’s what giving you TLE

I’ll tell you my method, you basically need to reduce that O(n^2)

The question can be divided into two parts

Task 1. For all possible subarrays, find their GCD and no of times the occur i.e frequency

Task 2. like @l_returns said, use sieve method for queries. I’ll explain my answer in detail.

My Solution which i’m refering

Line No 162 to 165 => Variable Declaration

Line No 166 to 169 => I build my sparse table, that can give me GCD of any range in log(n) time

Line No 170=> I create a map which would map a GCD with its frequency

Line No 171 to 182 => THIS IS WHERE I CALCULATE GCD WITH THEIR FREQUENCY

Basically GCD if calculated from a index, will either decrease or stay constant. Hence it’s monotonic in nature, so i can use binary search.

Line No 142 to 154 => MY Binary Search function that returns the index of the position where GCD decreases

I start with any index and call it my original GCD. Now I binary search the index where it decreases. Now i use my original index and that index to calculate the increase in the frequency of that GCD, by using the difference in index.

So in nlog(n) time i calculated all possible GCD with their frequency.

So Task 1 Complete Yay!

Now coming to task #2, it’s easy

Line No 186=> I call a function, fillDp();

Line No 197 to 202 => I’m using the sieve method here, i take any GCD (say X) and i add its frequency to all multiples of that GCD, simple! You can learn more about Sieve method from internet

So for all query ‘q’ , we simply outout the dp[q].

Task 2 accomplished ! and time for AC :stuck_out_tongue:

Let me know if any part of solution is unclear?

1 Like
19

Can someone please help me understand this
“(Remember there are only at max O(log(A[i]))” this phrase. I had thought this idea thoroughly during the contest but i was thinking it as in start i will have 1 subarray, then 2 subarrays, then 3 subarrays and so on till n-1 subarrays.
Some of them will have same gcd values but how this sum reduces to nlogn from n^2
For making the gcd frequency array how we won’t take order n^2 time?

20

It’ means that If you have a array say
[n1,n2,n3,n4.....nn]

and you start to take total GCD from a number say n2 , then the total GCD will only decrease
and it can decrease to a maximum of log(n2) distinct values.

Now you understand? :smile:

1 Like
21

How can we show the correctness of this proposition? That log(n2) part

22

I didn’t really proof that :rofl:…but i knew that the changed GCD can only be equal to n2 or a divisior of n2, so it came to me somehow

23

I had a similar approach but got a tle could you help.
https://www.codechef.com/viewsolution/26366721

24

@kartikey_25 Whats the complexity of your count function? I mean what’s the time complexity per query?

25

The editorial said:

Assuming 1-based indexing. Let’s say we are making an array t[] of length i, where t[j] = GCD(A[i], A[i - 1], ... A[i - j + 1]). In other words, t[j] equals GCD of the last j elements in the prefix ending at A[i]. How many distinct values can there be in t[]?

We have
t[1] = A[i],
t[j] = GCD(t[j - 1], A[i - j + 1]) = \frac{t[j - 1]}{k} with k being a factor of t[j-1].

This shows that t[] is decreasing and since at each succession there is a division, there are at most O(log(A[i])) distinct values in t[].

1 Like
26

Haven’t checked that. If it’s O(n^2*log(n)) then change it to O(n*log^3(n)) at least or O(n*log^2(n))

27

The space complexity can be optimized to O(n + log n)

28

@ssrivastava990 Consider the following case:
N = 10^5 and each A[i] = 3
Your solution is O(n^2).

29

So plz tell me how can I store all gcd frequency of all subarray less than o( n^2)

30

@ssrivastava990 by using binary search for every i from 0 to n-1

31

bhai…just tell me why did you used sparse table and how did you used that binary search…bhai hindi me hi samjha :joy: zada samajh me aaega.what i did was for every subarray i used to find the gcd and then mark it in the seive so finding gcd for each subarray took o(n^2logn) time how did you reduced it using sparse table and binary search that i want to know… @s5960r

32

The third line contains in Explanation contains " if and only if" . Is that correct or Should that be only “if”

33

what’s the purpose of binary search here?

34

This problem is almost same to this problem on Codeforces
problem.

2 Likes
35

To find every point where the GCD changes value.

36

Can someone tell me how to prove this?

37

I can prove it in two ways

1)

Smallest factor of any number is 2.
We can divide a number till it is not “1”.
Dividing by a number \gt 2 will make it “1” faster than dividing it by 2.
Because \frac {x}{2} \gt \frac{x}{k} where k \gt 2
Hence worst case is when number is power of 2.
2^x = a[i]
x=log_2(a[i])
Hence we can divide a number at most log_2(number) times even in worst case.

2)

Let a[i] = p_1^{k_1} * p_2^{k_2} * ... *p_N^{k_N}
Where p_1,p_2,…,p_N are prime factors of a[i] and k_1,k_2,…,k_N are integers greater than 0.
and p_1<p_2<p_3 <.... <pN

a[i] = p_1^{k_1} * p_2^{k_2} * ... *p_N^{k_N}
\hspace{ 6mm} \ge p_1^{k_1+k_2+...+k_N}

We can divide it for at most k_1+ k_2+...+k_N times.
Therefore,
log_2(a[i]) \ge log_{p_1}(a[i]) \ge k_1+ k_2+...+k_N , since p_1 \ge 2 .
Hence proved.

1 Like