Beautiful Mountains
Time limit1sMemory limit1024 MB
Given an array where some entries are unknown, decide whether the unknown positive values can be filled so the array splits into equal-length mountains, with the last block allowed to be shorter.
- Level
Hard8 of 10
- Topics
- Greedy, Implementation, Array, Brute force
- Solved
- No attempts yet
Problem
A subarray of an array is a contiguous portion of the array. A partition of an array into subarrays is a collection of subarrays that cover the whole array without overlaps, so each element of the array belongs to exactly one subarray. For instance, if A = [3, 1, 4, 1, 5], then [3, 1, 4] and [1, 5] form a partition of A into subarrays, while [3, 4, 5] is not a subarray of A.
These are standard definitions that you may have read elsewhere. A few more definitions follow.
Given an array A of integers, a subarray [Ai, Ai+1, . . . , Aj] of A is called a mountain if there exists an index k such that i < k < j, the subarray from Ai to Ak is non-decreasing, and the subarray from Ak to Aj is non-increasing. In simple words, the values in the subarray go up until index k and then go down, resembling a mountain. A subarray with fewer than three elements cannot be a mountain.
An array of integers is called a beautiful mountain chain if it can be partitioned into mountains, each of them having the same number of elements, except for the last mountain, which may have fewer elements.
For example, [5, 10, 4, 1, 3, 2] is a beautiful mountain chain because it can be partitioned into [5, 10, 4] and [1, 3, 2], both mountains with the same number of elements. Another example is the array [5, 10, 4, 4, 10, 20, 30, 20, 2, 3, 1], which is also a beautiful mountain chain because it can be partitioned into [5, 10, 4, 4], [10, 20, 30, 20], and [2, 3, 1].
Given an array of positive integers in which some values may be missing, determine whether it is possible to complete the array with positive integers so that it becomes a beautiful mountain chain.
Input
The first line contains an integer N (3 ≤ N ≤ 105) indicating the number of elements in the array. The second line contains N integers A1, A2, . . . , AN (Ai = −1 or 1 ≤ Ai ≤ 109 for i = 1, 2, . . . , N), where Ai = −1 indicates that the i-th element of the array needs to be determined, and a positive value is the actual i-th element of the array.
Output
Output a single line with the uppercase letter “Y” if it is possible to complete the array with positive integers so that it becomes a beautiful mountain chain, and the uppercase letter “N” otherwise.