Блог пользователя malviyanshiv

Needed data structure suggestion for answering these queries
Автор malviyanshiv, 5 лет назад, По-английски

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

  • Проголосовать: нравится
  • +6
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    → Ответить