Can someone provide me a decent editorial of simpleOne problem of this “May LoC Competitive Programming Marathon”?
3 Likes
I solved it using binary search + sparse table (i think segment tree might also work)
considering all sub arrays starting at a[i]…
from now on gcd(i,j) is gcd of sub array from i to j
obviously gcd(i,i)=a[i]
one basic observation is that gcd(i,j) will decrease for fixed i and increasing j (j>=i).
it is also easy to see that gcd(i,j) will change maximum log2(a[i]) times…( this is quite obvious if u think about it…so i am not proving it ).
lets start with j=i gcd(i,j)=a[i] lets use binary search to find maximum j such that gcd(i,max_j) remains equal to a[i]…once we have found that then number of sub arrays with gcd equal to a[i] += j_max-j+1
let j_max+1=j_prev
now gcd(i,j_prev) will not be equal to a[i] let it be some x…so now we binary search for max j such that gcd(i,max_j)remains x. number of subarrays with gcd equal to x += j_max-j_previous+1
since gcd changes at most log2(a[i]) times, for every element we have to do binary search at most log2(a[i]) times… gcd query in binary search can be done using seg tree O(logn) or sparse table O(1).
I maintained number of subarrays with gcd equal to x with a map
now u have all possible gcds with their counts…(this fits in memory…again easy to see why)
make an array with a[i]=count of i th smallest gcd
then answering queries will be easy using binary search. u will have to take presum of the array you built and get the index of the gcd then simply print it.
the complexity is nlognlog(a[i])
3 Likes
The first thing to observe is that the number of unique gcd values among all subarrays is very less. If g is the gcd of a number x with an adjacent number y : y < x, and we want g to be different from x and y, the largest it can be is x/3 when y is 2x/3. When taking the gcd of g and the next number, it will be scaled down again. Thus it is rapidly decreasing. This gives us a possibility of storing only unique gcd values since calculating and storing all gcd values is impossible.
Let gcd(i, j) be the gcd of the subarray from index i to j. For the evaluation of this, one can use any range query structure such as segment tree or sparse table.
Notice that gcd(i,i) \ge gcd(i,i+1) \ge gcd(i,i+2) ... \ge gcd(i,N)
We know that there will be very few unique values in this sequence. Hence it will be in the form of
g_1, g_1,...g_1,\; g_2, g_2,...g_2,\; g_3,g_3...g_3,.....,\; g_k,g_k, where g_1, g_2, g_3,..,g_k are the unique gcd values and g_1 > g_2 > g_3 >... > g_k.
We can see that g_1 = gcd(i, i) = A[i], and because the sequence is non-increasing, we can binary search it for upper bound of g_1. This gives the number of times g_1 appears in the sequence. Then we can simply set g_2 to the next value that comes after the upper bound of g_1, and repeat this until the end of the array is reached. These counts can be maintained as key-value pairs in a map data structure.
A tricky case arises when A[i]=0. This is because the sequence above will no longer be non-increasing. To resolve this we can see that if we have a chain of 0 from j_1 to j_2 of length l, all of its l(l+1)/2 subarrays will have gcd 0. Additionally, for each of the indices j_1 \le i \le j_2, gcd(i, k) will be the same as gcd(j_2+1, k) for all k > j_2. So we can solve for the first non-zero value after the zero-chain and compensate for the chain there using its length l.
Once we have all the key-value pairs of gcd and their counts, we can make a prefix sum array from the counts, and then for each query X use binary search to locate which gcd value needs to be fetched and printed.
That’s the whole method, and here is my
[1]. It is quite lengthy, so if someone has a better algorithm I would like to know :)
[1]: https://www.codechef.com/viewsolution/13908676
3 Likes
Good job! but your approach is too hard to digest.
Please use proper latex format for mathematics. I still could not catch you what you are trying to elaborate!
1 Like
@bansal1232, I was thinking the same considering the number of solutions, but it seems the reason for that is just weak test cases. Many solutions such as this and this have used an optimization of the naive approach, such as calculating gcd until it becomes 1. This is a huge oversight on the part of the problem setter, as it is very easy to think of test cases where such solutions will time out (such as an array of 2s only).
@bansal1232
well yes me and @meooow have used the same approach…except i did not handle a[i]=0 separately (i can prove that we dont have to)
this was my first answer here…so not super experienced at answering stuff…i will keep the formatting in mind…
I also found a simple and elegant solution here, which is much better than mine. Take a look at the Solve() function, it is easy to understand, but I can explain if need be.
@spj_29, how is it working for a[i]=0? Now that I think of it, one way would be to run a binary search assuming an increasing sequence to detect the last 0, and consider a non-increasing sequence as usual thereafter.
1 Like
@meooow exactly…
if a[i]=0 ,
initially we will compare gcds with gcd(i,i) which is 0.
so binary search will automatically give us the first next index with non zero value( a[j]!=0 , (j>i) )this gives us the range where the gcd is 0.
now gcd(i,j)!=0 so gcd(i,j+k)!=0 (k>=0) so now it just becomes a normal case where we can assume that a[i] was not 0 but it was a[j] (which was the first next non zero value) and find the rest of the ranges…
so we do not really have to handle this case separately…it takes care of itself…
i know i suck at explaining 
but i hope i am clear here…
1 Like
Yep, I get it. Hadn’t thought of this before 
1 Like
Would you like to elaborate of your first approach please?
The one I have described in the answer?
yeah! From this paragraph
A tricky case arises when…
Okay, consider A=[0,0,4,2], and imagine we are at i=1. gcd(1,1)=0, gcd(1,2)=0, gcd(1,3)=4, gcd(1,4)=2. Now (0,0,4,2) is not a non-increasing sequence as it would be if A[i] was not 0. So to adjust for this, we first find the length of the whole chain of 0 s starting at i=1, which is in this case 2. Then all subarrays of this chain have gcd 0. So there are 2(2+1)/2 subarrays with gcd value 0.
Next we can see that the sequence [gcd(1,3), gcd(1,4)]=[4,2] is the same as [gcd(3,3), gcd(3,4)]=[4,2]. This is also true for [gcd(2,3), gcd(2,4)]. We have not yet processed the subarrays starting at i=3, so we just remember that whatever will be the values we get with i=3, we need to count them 2 times more to compensate for i=1 and i=2, where A[i] was 0. Then we can simply skip from i=1 to i=3 and proceed.
Note that this whole “special case” can be avoided by following @spj_29’s solution. I have also updated the solution link with neater commented code.
@meooow is there any editorial for this problem SimpleOne ? . i didn’t get the idea how to solve this problem without TLE. Please help me…