malviyanshiv's blog

Needed data structure suggestion for answering these queries
By malviyanshiv, 4 years ago, In English

I was giving this hiring contest ( already over ). I am stuck at this question. Needed some help

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

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

The only conclusion I was able to reach is that for any query L, R, a and b, let g be the gcd of a, b. Then

if g == 1:
    return 0
else
    ans = 0
    for i in range(L, R):
        ans = ans + min(arr[i]%g, g - arr[i]%g)
    return ans

But it is just an optimization of bruteforce.

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

    Since $$$max(a, b) \le 10^3$$$, an optimization can be to build segment tree over the array, the nodes of which, will contain $$$10^3$$$ values, each corresponding to the required range sum as the gcd varies from $$$1$$$ to $$$1000$$$.

    Update is $$$O(M \cdot \log N)$$$ and query is $$$O(\log N)$$$ with $$$O(N \cdot M)$$$ memory, where $$$M = max(a, b)$$$.

    Since $$$M \le 10^3$$$, this could probably be fit into TL depending on how much it is.

    → Reply