Dropping Blocks
Time limit2sMemory limit512 MB
Given pile heights, decide whether prefix-wise operations (add 1 to a prefix or a suffix starting at k) can produce exactly that array, and say valid or invalid.
- Level
Hard8 of 10
- Topics
- Greedy, Math, Prefix sum, Implementation
- Solved
- No attempts yet
Problem
Daniel likes playing a game with blocks. The game starts with N empty piles of blocks in a line. While playing the game, Daniel does the following operation: he chooses a pile k and puts a block in every pile either to the left or to the right of pile k (including pile k). A valid game state is reached by applying only this operation zero or more times.
For example, in the above image, Daniel played a game with four piles and performed four operations. Firstly, he put one block in each pile to the left of pile 2 (including pile 2), then he put one block in each pile to the right of pile 2 (including pile 2), then he put one block in each pile to the left of pile 3 (including pile 3), and finally, he put one block in each pile to the left of pile 1 (including pile 1).
Given the number of blocks in each pile, determine if it is a valid game state.
Input
The first line contains a single integer N (1 ≤ N ≤ 100 000), which is the number of piles.
The second line describes the piles. The line contains N integers, each of which is the number of blocks in a pile. The piles are listed from left to right and each number is at least 0 and at most 100 000.
Output
Display if the input describes a valid game state.