You are not logged in. Please login at www.codechef.com to post your questions!

×

# GQR - Editorial

Div1, Div2
Practice

Author: Misha Chorniy
Tester: Lewin Gan

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 pre-compute the answers for all the possible query ranges. For the same purpose create two two-dimensional 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 re-compute $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 pseudo-code for the same,

for i=1...N-1:
ANS[i][i+1]=TEMP[i][i+1]
for l=3...N:
for i=1...(N-l+1):
j = i+l-1
ANS[i][j] = max(ANS[i+1][j],ANS[i][j-1])
ANS[i][j] = max(ANS[i][j],TEMP[i][j])

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 306719
accept rate: 7% 19.8k350498541

 0 Constraints were too tight. Even testers code gave tle: https://www.codechef.com/submit/complete/18017154 answered 01 Apr '18, 23:37 2.5k●4●21 accept rate: 17% 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) mgch6★
 0 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 58●5 accept rate: 5% Codechef has ML for all problems in range 1.5-2 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) mgch6★ 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)}. 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 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) mgch6★ 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) mgch6★ 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, A) = 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 = max(F, 1), F = max(F, 2), F = max(F, 3), ... F = max(F, d, d > 1), ..., F = max(F, 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) mgch6★ You can even obtain O(768N+Qsqrt(N)) solution if you'll use SQRT-decomposition instead of segment tree. (02 Apr '18, 15:54) mgch6★ 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
 0 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 58●5 accept rate: 5%
 0 "If we update $TEMP[ij][ij+1] = max(TEMP[ij][ij+1], D)$ ∀j
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×2,658
×2,214
×321
×47
×5

question asked: 31 Mar '18, 19:11

question was seen: 2,046 times

last updated: 10 Apr '18, 13:34