Skip to content
CCC Python Course

2D range-max DP and doubling on shapes

Stage
7
Module
M7.8
Lessons
1

In this module

  • Apply 2D DP to compute maximum values over rectangular regions.
  • Use doubling on geometric shapes to build solutions from smaller pieces.
  • Combine overlapping sub-shapes to construct a larger shape solution.
  • Recognize when full-scale solutions are infeasible and focus on partial subtasks.

Before this module

M6.12Doubling and binary lifting on sequencesM7.3Sparse table

Lessons

  1. 12D range-max DP and doubling on shapes

Practice

Try this on the judge. The link opens the problem on DMOJ.

  1. 2019 S5
    Triangle: The Data Structure (opens on DMOJ in a new tab) DMOJ

    A triangular grid of values, queried and updated many times.

    Why DMOJ: An older problem with a small first subtask, good for practicing a partial attempt.