Asia Hong Kong Regional Contest 2016


2016-11-06 03:00 CET

Asia Hong Kong Regional Contest 2016


2016-11-06 08:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -536 days 21:00:04

Time elapsed


Time remaining


Problem G

by Greg Hume on Wikipedia CC BY-SA
Bamboo scaffolding is very popular in Hong Kong. It is widely used in construction and maintenance of buildings, when high temporary structures are built to hold construction workers. You will also find bamboo scaffolds in Cantonese opera theatres and at the Bun Scrambling Competition in Cheung Chau.

As a construction worker, you want to build a bamboo scaffold for an upcoming festival. There are specific requirements for the final scaffold, which will be part of a vertical, $2$-dimensional grid. $N+1$ vertical long bamboos are already established, so there are $N$ columns in between. Initially all columns are empty. Our task is to place exactly $H_ i$ horizontal short bamboos in the $i$th column, literally from the ground up.

\includegraphics[width=.95\textwidth ]{diagrams}
Figure 1: The left diagram illustrates the initial scaffold that has $N$ empty columns. The right diagram shows the final scaffold for Sample Input 2.

You can carry at most $M$ short bamboos at a time. You will install the short bamboos in a number of rounds. In each round, you take at most $M$ short bamboos with you, and start anywhere on ground level.

You can only stand on a short bamboo that was built previously (or on ground level). Then you have two options:

  • Climb left, right or up if a short bamboo is already in place there

  • Place a short bamboo to the left, right or up if there is no short bamboo already placed

Note that you cannot go down while carrying short bamboos. You cannot place a short bamboo below you either.

Once you finish placing all the short bamboos in the current round, you go down to the ground level. You then take at most $M$ short bamboos with you and start another round from the ground level. This goes on until you have built the desired scaffold, with exactly $H_ i$ short bamboos in column $i$ for all $i$.

What is the minimum number of rounds you need?


The first line contains two integers, $N$ and $M$ ($1 \leq N \leq 100\, 000$, $1 \leq M \leq 10^9$). The second line contains $N$ integers $H_1, \dots , H_ N$ ($0 \leq H_ i \leq 100\, 000$).


Output an integer representing the minimum number of rounds.

Sample Input 1 Sample Output 1
3 4
2 1 5
Sample Input 2 Sample Output 2
5 10
2 1 2 1 2