omoyamo's blog

Interesting (actually not) range queries problem.
By omoyamo, history, 4 years ago, translation, In English

In some close russian circles this task was born. Can you solve it?

You have an array of length N of non-negative integers. Also you have to answer Q queries.

Query (L, R) — you have to find a max[ lcm(A, B) — gcd(A, B) ], where A and B — some elements of segment (L, R) (not necessarily of different index). Consider gcd(0, 0) = 0, lcm(0, 0) = 0.

N <= 10^5, Q <= 10^5

Write your ideas in comments.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by omoyamo (original revision, translated revision, compare)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the source of this problem?

→ Reply
»
4 years ago, # |
  Vote: I like it +34 Vote: I do not like it

What is the range of the integers in the array?

→ Reply
»
4 years ago, # |
  Vote: I like it +28 Vote: I do not like it

I don't know exact time complexity, but use treap, where every node maintains '2D-Persistent tree with FFT on each node'. To further optimization use meet-in-the-middle, but I don't know how to merge, but at all you can create a graph, after that go to Dominator tree and do some stuffs with combinatorics or Burnside's lemma. But I don't know time complexity.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't have an exact time complexity, but I think I do have a few steps towards a solution.

First let's make a segment tree of sets. Since it doesn't help to have multiple of a single number, we can operate on those sets instead of the raw array.

Second, let's compensate for the GCD by getting the maximum 2-3 LCM's. This should be safe because GCD is almost always small relative to LCM.

Now, how do we find the largest LCM quickly from a set of numbers? I suggest we simply run two for loops, each starting from the large end of the set, and calculate the LCMs. Importantly, we should short-circuit when we cannot possibly find a larger LCM later in the loop.

If we consider the first run of the outer loop, either we find some LCM greater than the largest number in the set, or it we don't. If we don't then we know all the rest of the numbers are factors of this one, so there is a small number of them and our loops will be short. If we don't, then we have some larger number as out biggest current LCM. Each inner loop can them be short circuited when the two elements multiplied is smaller than that LCM.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "This should be safe because GCD is almost always small relative to LCM." Yeah, but this is not an approximation problem. What about something like 4 7 10 15 4 7 10 15 4 7 10 15 etc.?

    → Reply