bihariforces's blog

Finding an array after repeatedly applying prefix sum
By bihariforces, history, 22 months ago, In English

Suppose we're given an array of length N upto 1e6 and we apply prefix sum to the array in place, ie. [a, b, c] becomes [a, a + b, a + b + c], we repeat this K times where K can be upto 1e6.

Can we find the resulting array after K operations faster than O(N*K)?

I have observed each preceding element has some contribution for an element in resulting array, but the coefficient doesn't seem intuitive to derive, can someone help derive how to compute the resulting array?

Finding a particular element of the resulting array, for example, just last element in better than O(N*K) would also suffice, hope someone can help.

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice problem!

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

unrated huh learn binary search instead

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

    nice joke, how about you try to get a color on your name yourself?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      saar i know him irl, that's why joke

      → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Could you please give a link to the source it comes from ? (That's a rule to be sure the community doesn't help about on ongoing contest.)

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    https://cses.fi/problemset/task/1716/

    I know this has direct math formula but I want to apply DP to it, I was able to reduce it to O(N*M) but on observation, it's just applying prefix sum repeatedly N times to [1, 0, 0...] of length M, so, I was wondering if we could generalize this for arbitrary array and find a particular element of it. which is the last element in above CSES one.

    → Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it +14 Vote: I do not like it

Consider the OGF form of the array as $$$F(x)=\sum\limits_{i=0}^{\infty}a_ix^i$$$.

For a generating function to do a prefix sum, just multiply it by $$$\sum\limits_{i=0}^{\infty}x^i$$$.

So to do k times prefix sum just multiply by $$$(\sum\limits_{i=0}^{\infty}x^i)^k=\sum\limits_{i=0}^{\infty}\binom{k+i-1}{i}x^i$$$, and then use NTT convolution.

→ Reply