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

×

GQR - Editorial

2
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

This question is marked "community wiki".

asked 31 Mar '18, 19:11

adkroxx's gravatar image

6★adkroxx
306719
accept rate: 7%

edited 01 Apr '18, 22:50

admin's gravatar image

0★admin ♦♦
19.8k350498541


Constraints were too tight. Even testers code gave tle:

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

link

answered 01 Apr '18, 23:37

abdullah768's gravatar image

6★abdullah768
2.5k421
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★

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.

link

answered 02 Apr '18, 12:33

mathprogrammer's gravatar image

3★mathprogrammer
585
accept rate: 5%

edited 07 Apr '18, 18:57

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) mathprogrammer3★
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) mathprogrammer3★

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) 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) mathprogrammer3★

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) mathprogrammer3★

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) mathprogrammer3★

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) 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) mathprogrammer3★
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.

link

answered 02 Apr '18, 12:33

mathprogrammer's gravatar image

3★mathprogrammer
585
accept rate: 5%

edited 02 Apr '18, 13:55

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

link

answered 05 Apr '18, 23:35

pk301's gravatar image

2★pk301
62710
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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