FoxAndMountainEasy | Topcoder Archive

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:

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 ints 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.

Definition

Class:: FoxAndMountainEasy
Method:: possible
Parameters:: int, int, int, String
Returns:: String
Method signature:: String possible(int n, int h0, int hn, String history)
(be sure your method is public)

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

```
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".
```
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.
```
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".
```
4
```
```
0
```
```
0
```
```
"DDU"
```
```
Returns: "NO"
```
```
20
```
```
20
```
```
20
```
```
"UDUDUDUDUD"
```
```
Returns: "YES"
```
```
20
```
```
0
```
```
0
```
```
"UUUUUUUUUU"
```
```
Returns: "YES"
```
```
20
```
```
0
```
```
0
```
```
"UUUUUUUUUUU"
```
```
Returns: "NO"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.