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

# | User | Rating |
---|---|---|

1 | tourist | 3434 |

2 | fateice | 3337 |

3 | Um_nik | 3292 |

4 | OO0OOO00O0OOO0O0…O | 3280 |

5 | Syloviaely | 3274 |

6 | Petr | 3223 |

7 | Swistakk | 3105 |

8 | mnbvmar | 3096 |

9 | yosupo | 3091 |

10 | dotorya | 3081 |

# | User | Contrib. |
---|---|---|

1 | rng_58 | 163 |

2 | tourist | 161 |

3 | csacademy | 152 |

4 | Petr | 151 |

5 | Swistakk | 148 |

6 | Um_nik | 144 |

7 | Nickolas | 142 |

7 | Vovuh | 142 |

9 | PikMike | 138 |

9 | BledDest | 138 |

9 | matthew99 | 138 |

9 | Errichto | 138 |

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

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/23/2018 00:59:35 (d2).

Desktop version, switch to mobile version.

User lists

Name |
---|

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:CodeThe 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]`

.Thanks, corrected that.

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

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)