Vittorio Plays with LEGO Bricks
Contest: SWERC 2022-2023 - Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 2200
Tags: dp, geometry

Vittorio is playing with his new LEGO Duplo bricks. All the bricks have the shape of a square cuboid with a $$$2 \times 2$$$ square base and a height of $$$1$$$. They can be arranged in the 3D space to build structures, provided that the following rules are met:

1. No two bricks can intersect, but they can touch on their faces.
2. The corners of every brick must have integer coordinates (so bricks are axis-aligned) and the $$$z$$$ coordinates of all corners must be non-negative.
3. The square bases of every brick must be parallel to the ground (i.e. the plane $$$z=0$$$).
4. The lower base of any brick that is not touching the ground must touch the upper base of some other brick in a region of positive area (when this happens, the two bricks stay attached to each other thanks to small studs).

For example, this is a valid structure:

Vittorio wants to build a structure that includes purple bricks in the following $$$n$$$ positions: $$$(x_1, 0, h)$$$, $$$(x_2, 0, h)$$$, $$$\dots$$$, $$$(x_n, 0, h)$$$ — these are the coordinates of the centers of their lower bases; note that all of these bricks have $$$y$$$ coordinate equal to $$$0$$$ and $$$z$$$ coordinate equal to $$$h$$$. Vittorio will use additional bricks of other colors to support the purple bricks. He is willing to place bricks only in positions where the center of the lower base has $$$y$$$ coordinate equal to $$$0$$$. What is the minimum number of additional bricks needed?

It can be shown that a valid construction always exists.

Input format:
The first line contains two integers $$$n$$$ and $$$h$$$ ($$$1 \le n \le 300$$$, $$$0 \le h \le 10^9$$$) — the number of purple bricks and their common $$$z$$$ coordinate.

The second line contains $$$n$$$ integers $$$x_1, \, x_2, \, \dots, \, x_n$$$ ($$$1 \le x_i \le 10^9$$$, $$$x_i + 1 < x_{i+1}$$$) — the $$$x$$$ coordinates of the purple bricks (centers of the bases), given in increasing order.

Output format:
Print the minimum number of additional bricks needed.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first sample, all the purple bricks lie on the ground, so no additional bricks are needed.

In the second sample, Vittorio will have to place supporting bricks under the purple bricks, and he can use a single brick to support both the third and the fourth purple bricks. For example, he can place additional bricks at positions $$$(3, 0, 0)$$$, $$$(7, 0, 0)$$$ and $$$(12, 0, 0)$$$. It can be shown that it is impossible to build a valid construction using less than $$$3$$$ additional bricks.

In the fourth sample, a possible structure that minimizes the number of additional bricks is shown in the problem description.

Example input:
4 0
2 7 11 13

Example output:
0

Example input:
4 1
2 7 11 13

Example output:
3

Editorial:
Each purple brick needs to be at the top of a chain of $$$h$$$ bricks at heights $$$0, 1, \ldots, h$$$ such that the $$$x$$$ coordinates of consecutive bricks differ by at most $$$1$$$. In an optimal structure, we may assume that every brick belongs to at least one of the $$$n$$$ chains, and that any two chains that differ at some height $$$h'$$$ also differ at all heights $$$\geq h'$$$.
We say that two chains diverge at height $$$h'$$$ if their bricks coincide up to height $$$h'-1$$$ but not at height $$$\geq h'$$$. In particular, two chains with different bricks at height $$$0$$$ are said to diverge at height $$$0$$$. For now, let's pretend that bricks can partially overlap with each other, so that there are no further constraints on how chains can be formed; at the end we will show how to account for overlapping bricks.
For $$$1 \leq l \leq r \leq n$$$, denote by $$$f(l, r)$$$ the minimum number of additional bricks needed to support the purple bricks $$$l, l+1, \dotsc, r$$$. We will recursively compute $$$f(l, r)$$$. For $$$l=r$$$, a single chain is needed and so $$$f(l,r) = h$$$.
Suppose now that $$$l < r$$$. For any $$$m$$$ with $$$l \leq m < r$$$, we can build a structure as follows. First, place $$$f(l, m)$$$ blocks to support the purple bricks $$$l, l+1, \dotsc, m$$$. It is easy to see that we can modify such a structure so that the chain supporting the leftmost purple brick always climbs to the left, i.e., it consists of the bricks at positions $$$(x_l+h, 0, 0), (x_l+h-1, 0, 1), \dotsc, (x_l, 0, h)$$$. Similarly, add $$$f(m+1, r)$$$ bricks to support the purple bricks $$$m+1, m+2, \dotsc, r$$$, while ensuring that the chain supporting the rightmost purple brick always climbs to the right. If we set $$$h_{lr} := \max(0, h + 1 - \lceil (x_r - x_l) / 2 \rceil)$$$, then it is possible to further change the leftmost and rightmost chains so that they coincide at heights $$$0, 1, \dotsc, h_{lr}-1$$$ (and in fact diverge at height $$$h_{lr}$$$). We obtained a valid structure to support the purple bricks $$$l, l+1, \dotsc, r$$$ consisting of $$$f(l, m) + f(m+1, r) - h_{lr}$$$ additional bricks.
Conversely, suppose to have an optimal structure to support the purple bricks $$$l, l+1, \dotsc, r$$$. Let $$$m$$$ be the index of any purple brick such that the $$$m$$$-th and the $$$(m+1)$$$-th chain diverge at the lowest possible height $$$h'$$$. In particular, all chains coincide at heights $$$0, 1, \dotsc, h'-1$$$. Additionally, the first $$$m$$$ chains share no bricks with the other chains at heights $$$\geq h'$$$. Note that $$$h' \leq h_{lr}$$$, otherwise it would not be possible to support both the $$$l$$$-th and the $$$r$$$-th purple bricks. Therefore, the number of non-purple bricks is at least $$$f(l, m) + f(m+1, r) - h' \geq f(l, m) + f(m+1, r) - h_{lr}$$$.
This allows us to use dynamic programming to calculate $$$f(l,r)$$$ through the following recursive formula: $$$$$$ f(l, r) = \min_{l \leq m < r} f(l, m) + f(m+1, r) - h_{lr}. $$$$$$ In particular, we can compute the answer $$$f(1, n)$$$ in $$$O(n^3)$$$ time.
To conclude, we now show that any optimal structure with overlapping bricks can be modified into an optimal structure with the same number of bricks which do not overlap. Suppose to have two overlapping bricks with $$$x$$$ coordinates $$$\overline x$$$ and $$$\overline x+1$$$ (and same height). There can't be any brick at the same height and with $$$x$$$ coordinate equal to $$$\overline x-2$$$, $$$\overline x-1$$$, $$$\overline x+2$$$, or $$$\overline x+3$$$, otherwise we could remove one of the two overlapping bricks (it would not be needed to support the bricks above). Then we can move the left brick to position $$$\overline x-1$$$ or the right brick to position $$$\overline x+2$$$ (at least one of the two works, based on the position of the bricks in the row immediately below).