FoxAndMountainEasy
SRM 557 · 2012-06-05 · by cgy4ever
SRM 557 · 2012-06-05 · by cgy4ever · Dynamic Programming, Greedy
Problem Statement
Problem Statement
Fox Ciel lives in a beautiful countryside.
She loves climbing mountains.
Yesterday, she went hiking in the mountains.
Her trip can be described as a sequence of (n+1) integers: h[0], h[1], ..., h[n]. These values represent altitudes visited by Fox Ciel during the trip, in order. Fox Ciel does not remember the precise sequence, but she remembers the following:
The last condition means that in each step the altitude of Fox Ciel either increased by 1, or decreased by 1. We will call the two types of steps "steps up" and "steps down", respectively. Steps up will be denoted 'U' and steps down will be denoted 'D'.
You are given theint s n, h0, and hn: the length of the trip, the altitude at the beginning, and the altitude at the end.
In addition to these, Fox Ciel remembers some contiguous segment of her trip.
You are given this segment as a String history.
Each character of history is either 'U' or 'D'.
Check whether there is a valid trip that matches everything Fox Ciel remembers. Return "YES" (quotes for clarity) if there is at least one such trip, or "NO" if there is none.
Her trip can be described as a sequence of (n+1) integers: h[0], h[1], ..., h[n]. These values represent altitudes visited by Fox Ciel during the trip, in order. Fox Ciel does not remember the precise sequence, but she remembers the following:
- for each i, h[i] >= 0
- h[0] = h0
- h[n] = hn
- for each i, abs(h[i+1]-h[i]) = 1
The last condition means that in each step the altitude of Fox Ciel either increased by 1, or decreased by 1. We will call the two types of steps "steps up" and "steps down", respectively. Steps up will be denoted 'U' and steps down will be denoted 'D'.
You are given the
Check whether there is a valid trip that matches everything Fox Ciel remembers. Return "YES" (quotes for clarity) if there is at least one such trip, or "NO" if there is none.
Constraints
- n will be between 1 and 100,000, inclusive.
- history will contain between 1 and min(50,n) characters, inclusive.
- Each character in history will be either 'U' or 'D'.
- h0 will be between 0 and 100,000, inclusive.
- hn will be between 0 and 100,000, inclusive.
Examples
0)
4 0 4 "UU" Returns: "YES"
The only solution is: h[] = {0, 1, 2, 3, 4}, the history of the entire trip will be "UUUU".
1)
4 0 4 "D" Returns: "NO"
Based on n, h0 and hn, the history of the entire trip must be "UUUU". There is no 'D' in this history.
2)
4 100000 100000 "DDU" Returns: "YES"
We have the following solution: h[] = {100000, 100001, 100000, 99999, 100000}, the history of the entire trip is "UDDU".
3)
4 0 0 "DDU" Returns: "NO"
4)
20 20 20 "UDUDUDUDUD" Returns: "YES"
Submissions are judged against all 262 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class FoxAndMountainEasy with a public method string possible(int n, int h0, int hn, string history) · 262 test cases · 2 s / 256 MB per case