PROBLEM LINK:Div1, Div2 DIFFICULTY:Medium PREREQUISITES:Familiarity with GCD, Dynamic Programming PROBLEM:You are given a sequence $A$ with $N$ elements and $Q$ queries on this sequence. In each query, you are given two indices $L$ and $R$; you should compute the maximum value of the greatest common divisor (GCD) of two elements $A_x$, $A_y$ satisfying $L \le x < y \le R$. EXPLANATION:We will try to precompute the answers for all the possible query ranges. For the same purpose create two twodimensional array $TEMP[N][N]$ and $ANS[N][N]$, where $N=10005$. We will define $ANS[L][R] = max(TEMP[x][y])$ ∀ $L \le x < y \le R$. Observation: Let's take a look at multiple of any particular numbers $D$. Say the multiples of $D$ in the array are located at $i_1,i_2,i_3,..i_k$. Now, any query range which contains atleast two of the above index will have answer $\ge D$ (Why?). If we update $TEMP[i_j][i_{j+1}] = max(TEMP[i_j][i_{j+1}],D)$ ∀ $j < k$, and recompute $ANS$ array, we can see it will cover all the required query ranges that needs to be updated. We will try to build our solution using the above observation. Iterate over each of the numbers in the array, find their respective divisors in $O(\sqrt{A[i]})$. Corresponding to every divisor, find the right most index $j < i$ where multiple of this divisor has appeared. You can use another array to ease this process. After finding such $j$ you just need to update $TEMP[j][i]=max(TEMP[j][i],\text{corresponding divisor})$. Once you have iterated over all the numbers, compute $ANS[x][y]$ ∀ $1 \le x < y \le N$. You can have a look at pseudocode for the same,
You can answer every query in $O(1)$ now. Time Complexity:$O(N^2+Q)$. AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 31 Mar '18, 19:11

Constraints were too tight. Even testers code gave tle: answered 01 Apr '18, 23:37
1
It isn't tester's solution. It's kind of very fast O(N^2 log A) solutions. Here is the tester's solution: https://pastebin.com/0NMGeUtw
(01 Apr '18, 23:43)

In the setter's solution, the array is allocated 10^8 memory. How is this possible ? Note  I was taught another solution in the comments by the kind mgch. It has better time and memory complexity. Offline processing of the queries. Here is the code and the explanation. answered 02 Apr '18, 12:33
Codechef has ML for all problems in range 1.52 GB. Actually, (N^2+A) memory, it's ~800 MB. Anyways, you were able to solve it in offline with O(N log N + Q) memory: read all queries, sort them by right end. Create the segment tree with operations: update the value on a segment and find a maximum on a segment. Go through all numbers from 1 to N and update the value TEMP[prev[d]] by d, prev[d] means previous number divisible by d, d means divisor, set prev[d] = i. Answer queries of this right end. It took ~O(Q * log N + N * sqrt(A) + N * 768(maximal number of divisors till 10^8) * log N) time
(02 Apr '18, 12:56)
Alright, Thanks. But, my IDE does not allow me to have such big arrays and causes run time errors.
(02 Apr '18, 13:56)
1
I was not able to follow your segment tree approach. Please add it to the editorial. I followed the editorial's approach of Answer(L, R) = max{Answer(L, R), Answer(L + 1, R), Answer(L, R  1)}. My approach  https://github.com/MathProgrammer/CodeChef/blob/master/Explanations/Explanations%2010/Queries%20with%20GCD%20Explanation.txt But I wasn't able to understand what you said with segment trees. Please help.
(02 Apr '18, 13:58)
About segment trees, you can take a look on this code https://www.codechef.com/viewsolution/18011514 and add unordered_map <int, int=""> have[] instead int have[] and you'll need ~O(768*N) memory. My solution is like an editorial :) Click at setter's solution please :)
(02 Apr '18, 14:07)
The solution link I posted was made after studying your code only :). Which solution is better ? The segment tree solution, or the DP solution you used in your code ?
(02 Apr '18, 14:27)
The difference between them that original one is online and the second one in offline. But the first one using more memory than the second. They both are accepted. But if you had Q <= 1e8(only the first solution was accepted). If MemoryLimit was 256 MB then only the second solution was accepted. So, it's your choice to choose the algorithm. Your goal is to get 100 pts ;)
(02 Apr '18, 14:43)
As far as I can tell, in this solution, segment[n] holds the maximum gcd you can make using A[n] and any element upto A[R]. How can we guarantee that when we call max[L, R], we don't get segment[x] = gcd (A[x], A[y]), where x is inside [L, R] and y is < L. This is not clear to me. Please explain.
(02 Apr '18, 14:48)
For example, A = 300, 1, 1, 300, 1 Now [L, R] = [3, 5] MAx[3, 5] = 300, but the answer should be 1. Since gcd(A[1], A[4]) = 300. And 1 is outside the range.
(02 Apr '18, 14:56)
No, when you're checking 300 at position 4, you're updating maximum at previous positions for divisors, i.e F[3] = max(F[3], 1), F[1] = max(F[1], 2), F[1] = max(F[1], 3), ... F[1] = max(F[1], d, d > 1), ..., F[1] = max(F[1], 300) And when you're at position 5, you're checking the maximum overall F[i], i >= L=3 at that momemnt. You'll get 1
(02 Apr '18, 15:53)
You can even obtain O(768N+Qsqrt(N)) solution if you'll use SQRTdecomposition instead of segment tree.
(02 Apr '18, 15:54)
Oh ... So you're saying that segment[n], holds the maximum gcd A[n] gets with any element in [n + 1, R], since only those are allowed to update A[n]. I get it. Thanks for your help !
(02 Apr '18, 16:43)
showing 5 of 11
show all

If you understood the concept of using the insight that if gcd(a, b) = g, then it means that a and b are multiples of g, here is a problem from HackerRank where you can practice the same concept. answered 02 Apr '18, 12:33

"If we update $TEMP[ij][ij+1] = max(TEMP[ij][ij+1], D)$ ∀j<k, and recompute ANS array, we can see it will cover all the required query ranges that needs to be updated." Can someone please explain me how it is going to cover all possible pairs? answered 05 Apr '18, 23:35
