GQR - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Div1, Div2

Practice

Author: Misha Chorniy

Tester: Lewin Gan

Editorialist: Adarsh Kumar

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

Setter’s solution

Tester’s solution

2 Likes
2

Constraints were too tight. Even testers code gave tle:

https://www.codechef.com/submit/complete/18017154

3

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

1 Like
4

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


[1] and the [explanation][2].


  [1]: https://github.com/MathProgrammer/CodeChef/blob/master/C%20Programs/C%20Programs%2010/Queries%20with%20GCD%20Offline%20Solution.cpp
  [2]: https://github.com/MathProgrammer/CodeChef/blob/master/Explanations/Explanations%2010/Queries%20with%20GCD%20Offline%20Solution%20Explanation.txt
5

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.

6

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

7

Alright, Thanks. But, my IDE does not allow me to have such big arrays and causes run time errors.

8

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.

1 Like
9

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 :slight_smile: Click at setter’s solution please :slight_smile:

10

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 ?

11

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 :wink:

12

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.

13

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.

14

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

15

You can even obtain O(768N+Qsqrt(N)) solution if you’ll use SQRT-decomposition instead of segment tree.

16

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 !

17

“If we update TEMP[ij][ij+1] = max(TEMP[ij][ij+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.” Can someone please explain me how it is going to cover all possible pairs?