408624: GYM103230 A Torty and Shields

Torty the sea turtle is fending off invading jellyfish!

Torty has an army of $$$n$$$ turtles standing in a line, each holding a shield of length $$$\ell$$$. Initially, the shield of the $$$i$$$-th turtle is at the interval $$$[x_i, x_i + \ell)$$$. Torty wants the turtles to arrange their defense positions so that their shields concatenate into a contiguous interval of length $$$n\cdot\ell$$$ inside the battle interval $$$[0, b)$$$.

Turtles are serene creatures. They would rather bask in the sun than move around. But once moving, they can go any distance. What is the minimum number of turtles that have to move to form the target configuration?

Torty entrusts this important problem to you. Solve it quickly!

The first line contains three integers $$$n$$$, $$$\ell$$$, and $$$b$$$, where $$$1 \le n \le 2\cdot 10^5$$$, $$$1 \le \ell, b \le 10^9$$$, and $$$n\cdot\ell \le b$$$. The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$, where $$$-10^9 \le x_i \le 10^9$$$. The shields may overlap at their initial positions.

Print the minimum number of turtles that have to move.

6 2 13
-1 3 4 5 12 11

3

10 77510323 901306288
620843873 233292258 698354196 310802581 761289 155781935 465823227 388312904 78271612 543333550

0

10 22312461 336063920
332343265 290626439 150730813 173043274 148781733 83793430 171756290 65988290 158227842 170597107

7

The best way is to move the turtle with shield at $$$[-1, 1)$$$ to $$$[1, 3)$$$, the turtle with shield at $$$[4, 6)$$$ to $$$[7, 9)$$$, and the turtle with shield at $$$[12, 14)$$$ to $$$[9, 11)$$$. Then all shields are joined into a contiguous interval $$$[1, 13)$$$ inside the battle interval $$$[0, 13)$$$.