TheEgoist's blog

By TheEgoist, 3 weeks ago, In English

Given an array pixel of size $$$n$$$ where $$$ith$$$ pixel is $$$pixel[i]$$$, An image is clear if the array pixel has a padding of some number of 0s (possibly none) in the prefix and the suffix and the non-zero part in the array pixel say from index $$$i$$$ to index $$$j$$$,starts from $$$pixel[i]=1$$$, strictly increases for some $$$k$$$ in steps of $$$1$$$ and then strictly decreases in steps of $$$1$$$ such that $$$pixel[j]=1$$$. For example the pixel arrays $$$[0, 0, 1, 2, 3, 2, 1], [1, 2, 1], [1], [0, 0, 0, 1, 2, 3, 4, 3, 2, 1, 0]$$$ are clear. In a single operation you can reduce any pixel value by $$$1$$$. Given $$$n$$$ pixels of an image and an array pixel find the minimum number of operations required to make the array pixel clear.

Constraints:

$$$1 <= pixel[i] <= 1e9$$$

$$$1 <= n <= 3 * 1e5$$$

Full text and comments »

  • Vote: I like it
  • -19
  • Vote: I do not like it