nikizakr's blog

By nikizakr, history, 5 months ago, In English,

Hi Codeforces :D I'm looking for some problems about 3D prefix sum can you provide some links thanks a lot

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

»
5 months ago, # |
Rev. 4   Vote: I like it +3 Vote: I do not like it

After writing this comment I realized that your post was asking about problems rather than requesting a tutorial :). I hope someone will find this useful anyway.

Well, I think I could explain it right there. So, for 1D prefix sums you simply do S[i + 1] = S[i] + a[i], nothing special here. For 2D, on the other side, you have to subtract overlapping region: S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + a[i][j]. For 3D there will be even more overlapping: S[i][j][k] = S[i - 1][j][k] + S[i][j - 1][k] + S[i][j][k - 1] - S[i - 1][j - 1][k] - S[i][j - 1][k - 1] - S[i - 1][j][k - 1] + S[i - 1][j - 1][k - 1] + a[i][j][k]. You can find similarity with inclusion-exclusion formulas. So, with adding new dimensions it becomes more burdensome exponentially. You can check out this code:

Code
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    The formula for two dimensions is wrong. I think it's a typo.

    The correct formula is S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j]. You wrote S[i][j+1] instead of S[i-1][j].

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

Here's a task from UVa online judge 10755 — Garbage Heap.

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

You are given a non-empty, zero-indexed array A of n (1 <= n <= 100 000) integers a[0], a[1], ... , a[n−1] (0 <= a[i] <= 1 000). This array represents number of mushrooms growing on the consecutive spots along a road. You are also given integers k and m (0 <= k, m < n). A mushroom picker is at spot number k on the road and should perform m moves. In one move she moves to an adjacent spot. She collects all the mushrooms growing on spots she visits. The goal is to calculate the maximum number of mushrooms that the mushroom picker can collect in m moves. For example, consider array A such that: 2 3 7 5 1 3 9 0 1 2 3 4 5 6 The mushroom picker starts at spot k = 4 and should perform m = 6 moves. She might move to spots 3, 2, 3, 4, 5, 6 and thereby collect 1 + 5 + 7 + 3 + 9 = 25 mushrooms. This is the maximal number of mushrooms she can collect.

Solution (Python)