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

Help with problem
Автор szawinis, история, 7 лет назад, По-английски

You are given two arrays of integers a, b both with length n <= 10^5. For each 0 <= x <= n print the sum of a[i]*b[x-i] for all 0 <= i <= x.

It's obvious this can be done in quadratic time, but can we do any better?

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

»
7 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
Hint: two questions
Answer to first question
Answer to second question
→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Thanks for the reply. Your strategy is quite interesting, however that only solves the problem if we want the sum over a[i]*b[x-i] for all x and for all i. The problem was to isolate each x and calculate the sum over a[i]*b[x-i] for all i for this value of x only, then move on to the next value of x. I'm very sorry if this wasn't clear.

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

      Oh, I didn't get that. I think that the same strategy works in this case though.

      → Ответить
»
7 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

It seems that the answer will always be equal to . (can't prove it, sorry)
Let p be the partial sum array of a. Then the answer is simply .

→ Ответить