TopCoder Statistics - 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:

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"
10

10

22

"U"

Returns: "NO"
10

10

11

"D"

Returns: "NO"
36

52

70

"DDDDDDDDDDUUDDDDDDDDDDDDDDDDD"

Returns: "NO"
5

5

4

"U"

Returns: "YES"
67994

2675

645

"DDDDDDDUUDUUDDDUDDDDDDDDDDDDDDDDUDDDDD"

Returns: "YES"
89003

85932

10413

"UUDDDDDDDDDDDDDDDDDDDDUDUDU"

Returns: "YES"
52281

2513

48060

"DDDDDDDUDUDUUD"

Returns: "YES"
7274

72

492

"DDDDDDDDDDDDDDUDDUDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"

Returns: "YES"
37

36

31

"U"

Returns: "YES"
10370

4658

3990

"UUDUUDUDDUDUUUUDDUDDUUDUUDDDUUUUUDUDUDDDDDUUDDUU"

Returns: "YES"
66264

40406

48634

"DDDDDDUDUDDUUUUDUUUDUUUDDDDUUDUUUUDDDDUDDDDDDDU"

Returns: "YES"
25

190

165

"DUUUDUUUDDUUUUUDD"

Returns: "NO"
74154

84

7

"UUUDUUUUDUUUUDUUUUDUDDUDUUDUUUDDUUUDDUUUDUDUDUUDU"

Returns: "NO"
5650

1397

969

"UDUUUDUDDDDUDDUUDUUUUDDUUUUDUDUDUDUDDDD"

Returns: "YES"
2198

0

2

"DDUUUUUD"

Returns: "YES"
36546

14655

30305

"DDDDDDDUDDDUDDDDDDD"

Returns: "YES"
49

22

35

"UDDDDDUUUDDDDDDUDDDDDUDDUUDUDDDDUDUDDDDDDDDDDD"

Returns: "NO"
7

33

32

"DDD"

Returns: "YES"
69566

62705

52473

"UDDDDDDDUDDDDDDDDUDDDDDDDDDDDDDDUDD"

Returns: "YES"
49

61

64

"DDDDDUDUUUD"

Returns: "YES"
76879

67

66

"DDDDDDDDDUUDDDDDDDDDDDDUDU"

Returns: "YES"
15

5

34

"UUDDDUD"

Returns: "NO"
39

30

25

"UDDDDDUUDUUUD"

Returns: "YES"
39273

9813

332

"UUDUUUDDUUUDDUUUUDUUDUDDDDDDDDUUUUDUDUUU"

Returns: "YES"
29

16

29

"UUUUUUUUUDU"

Returns: "YES"
20

15

17

"UDDUDUUUUUDUUUUUUU"

Returns: "NO"
43

31

42

"DDDDDUUUDDDUDUUUDDUDDDDDUDUDDDDDUDDDDDD"

Returns: "NO"
48

6

20

"DUUDUDUUDUDDUU"

Returns: "YES"
2

2

2

"UU"

Returns: "NO"
38

82

62

"DDUDUDUDUUUUDDDUUDUDUUUUUUUDUDUU"

Returns: "NO"
2

0

2

"U"

Returns: "YES"
37

33

0

"UUUUDUU"

Returns: "NO"
50

8

6

"DDDDUDU"

Returns: "YES"
97608

82137

8191

"UUUUUUDDUUUDUDUDUUUUDUDUUDDUU"

Returns: "YES"
97667

856

3

"UDUUUUDDD"

Returns: "YES"
31016

2393

5153

"UDUU"

Returns: "YES"
43916

31531

93

"UUUUUDUDUUDDUUUDUUDUDUUUUUU"

Returns: "YES"
1010

137

9

"UUDUUDDDDUDDDUUUUDUD"

Returns: "YES"
31634

26590

23936

"DUUUUDUUUDUDDDUUUUDUUUDD"

Returns: "YES"
49849

11786

19043

"DUUDUDDDDDDDUDDUDUUUUUDDUDUUD"

Returns: "YES"
2231

439

876

"UUUUUUUUUUUUUUUUUUUUUUUUUUUUU"

Returns: "YES"
8

1

7

"UU"

Returns: "YES"
45

42

7

"DUUUUUUDUDDU"

Returns: "NO"
45

4479

20447

"UUUUUUUDUUUDD"

Returns: "NO"
34

16

18

"DDUDDDDDDDDDDDDDDDDDD"

Returns: "NO"
26

26

0

"UUUUUUUUUUUUUUUUDUUUUUUU"

Returns: "NO"
33669

28682

6015

"DUDUDDDDDUUDDUUUUDDDUDDD"

Returns: "YES"
17622

6717

5053

"UDDUDDDDUUDUDDDDUUDUDDUDDUDDDDUDDUUDDUDDUDDDU"

Returns: "YES"
78461

20417

44852

"UUUDDDUUDDUUUUUUUDUDUUUUDDDUUDU"

Returns: "YES"
22653

713

8

"DDDDDDDDDDDDDDDDDDUUUDUUDDDDDUDDUDDDDDDDDDDDDDDDD"

Returns: "YES"
51992

9888

40740

"UUU"

Returns: "YES"
2275

2155

1170

"DDUUDDUUDUDUDDUDUDUDDUUDUD"

Returns: "YES"
65356

24588

48968

"DDDUUDUDDDDDDUDUUDDDUDUDUDDU"

Returns: "YES"
53691

24583

45056

"UDUDDUUUUDUUDUUUDUUDUUUDUDDUDD"

Returns: "YES"
51367

64

725

"DUUUUUUDUDDDUUUUDUDDDUDDDDDDUUDDDDUDUDDUDDUUDUDDD"

Returns: "YES"
40491

96176

75

"UDUDUDUDUUUDDDDUUUDUDUDDUDUU"

Returns: "NO"
15046

8

6060

"DDDDDDDDUUUUUUUUUUDDUUDDDDDUDUDDDUDDDUDDUDUDDD"

Returns: "YES"
35

7

0

"UUUUUUUUUUUDUDDDDUUU"

Returns: "NO"
30565

617

2

"DUUUDDDUDUUUUDDDUUUUUU"

Returns: "YES"
5

5

10

"DD"

Returns: "NO"
45

33

28

"DDDDDDDDDDDUDDDDDDDDDUDDDDUDDDDDDDDDD"

Returns: "NO"
5563

99089

1794

"DDDDUDDDDDDUD"

Returns: "NO"
20165

981

19244

"DDDDDDDDDUDDUDDDDDDDDDDDDDD"

Returns: "YES"
2

790

788

"D"

Returns: "YES"
72692

4

2094

"UUUDUUDUDUDUUDUUUUDUDUUUUUUUUUUUDUUU"

Returns: "YES"
33

3297

3292

"UDD"

Returns: "YES"
32747

5810

947

"DDUDDDDUDDDDDDDDDDDDDDDDU"

Returns: "YES"
16

4

2

"UDUUUDUUU"

Returns: "YES"
52784

2841

21951

"DDDDDDDDDDDDDDDDDDDUUUUDDUDDDDDDDDD"

Returns: "YES"
15896

3

4487

"UUUUUUUUUUUUDUUUUUUUUUUUU"

Returns: "YES"
1807

1554

87

"UDDUDDUDDDDDD"

Returns: "YES"
27

23

9

"UDUUDDUUUUDUU"

Returns: "NO"
8

10

4

"DUDUU"

Returns: "NO"
23378

15888

3688

"DDDDUDUDUDUUUDDDDD"

Returns: "YES"
27

4

13

"UUDDDDDDDDDDUUD"

Returns: "NO"
20

9

15

"DDDDDUUDUUUUU"

Returns: "YES"
70226

11702

46434

"DDDDDDDDDUUUDUUDDUDUUDUUDUDUDDDD"

Returns: "YES"
29

3

8

"DDUDUDDDDDUDDDDUDDDDDDUDDDDDU"

Returns: "NO"
49163

4647

4596

"UDDDUUUDUDUDUUUDUUDDDUU"

Returns: "YES"
14

47862

96

"DUUDDD"

Returns: "NO"
19381

13084

12043

"DUUUUUUUUU"

Returns: "YES"
85719

881

0

"UDUUUUUUUDUDUUDDUUDUUUUDDUDUUDUUDDU"

Returns: "YES"
85252

20

51

"DDDDDDDDDDDUDD"

Returns: "NO"
26

3

11

"UUUUUUUUUUUUDUU"

Returns: "YES"
4520

9

39

"UUDDUDDUDDDUDDDDDDDDDUDUDUDDDDU"

Returns: "YES"
11096

2054

227

"DDDDDDDDDDDDDDDDDDUDDDUDDDDDDDDDDDDDDDDDDDDUDUDUDD"

Returns: "NO"
30

3

9

"DUDDDUDUUDDDDUDDDD"

Returns: "NO"
3

1

2

"DD"

Returns: "NO"
75551

71114

50437

"UUUDUUDDDDUDDUUDDDDUUUDDUDDDUDUUUUDDD"

Returns: "YES"
11296

9271

10235

"UD"

Returns: "YES"
54095

7499

9498

"DUDDUUUUUUDUD"

Returns: "YES"
15484

0

8

"DDDDDDDDDDDUDDDDDDDDUDDDDDDDDDDDD"

Returns: "YES"
41

9

34

"DUDDDUUUDDDDUUDDDDU"

Returns: "NO"
20654

9486

15728

"DDDDDD"

Returns: "YES"
47

23

12

"UUDDUUUUUDUUDUDUUUDUUUD"

Returns: "YES"
57752

92

3670

"UUUDUUDDUUDUDDUUUUDDDDDDDUDUDUUDUUDUDUDUDUDUDDDDDD"

Returns: "YES"
17

13

14

"DDDDDUD"

Returns: "YES"
40

1

1701

"DDDDDDDDUUDDUDDUDDDDUDDUUDDDUDDUDD"

Returns: "NO"
40655

34737

40012

"UUUUDUDUUUUUDDDDD"

Returns: "YES"
10

10

8

"DU"

Returns: "YES"
38

9818

19932

"DDDDDDDDDDDUDDDDDDDDDDDDDDDD"

Returns: "NO"
66040

6

119

"UDDUUDDDUD"

Returns: "NO"
20

2

18

"DUDDDDDD"

Returns: "NO"
28

806

66

"DDDUUDDDDDDUD"

Returns: "NO"
40077

1202

2015

"DDDDDDDDDUUDDDUDUDDDDDDDUUDDDUUUUDDDUUD"

Returns: "YES"
96533

29232

31164

"DDDDDDDDDDDDD"

Returns: "NO"
85704

74956

32264

"DDUDDDDUDDUUDDDDDDDDDDDD"

Returns: "YES"
69755

8

67

"DDDDUUDUDDDUUUUDUDDUUUUDUDDUDUUUDUDD"

Returns: "YES"
15

4

5

"DUUU"

Returns: "YES"
21

2

11

"UDUDDUU"

Returns: "YES"
65744

982

6958

"DDDDD"

Returns: "YES"
27

3

6

"DUUUUUUUUUUDUUUU"

Returns: "YES"
14

4

2

"UUUUUUUUUUU"

Returns: "NO"
6

1

3

"DD"

Returns: "YES"
65818

51172

10510

"DDDDDDUDDDDDDDDU"

Returns: "YES"
59614

30979

58789

"UDUUDUUUUDDDUUUDDDUUUUUUUUUDUDUDUD"

Returns: "YES"
3

2

1

"DD"

Returns: "YES"
59325

18740

26375

"DDDDDDDUDDDDDDDDDDDDUDDDDDUDUDDDDDDUDDDD"

Returns: "YES"
8171

5391

6296

"UDDDDUUDD"

Returns: "YES"
25

18

21

"UUUUUUUUUUUUUDUUU"

Returns: "NO"
49649

19

10

"UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU"

Returns: "YES"
21

1

2

"UUUUUDDDUDUUDDUDDD"

Returns: "YES"
29

22

27

"UUUDDDUDUUUDUDUUDDDDUU"

Returns: "YES"
36

26

8

"UUUD"

Returns: "YES"
37

5

8

"DUDDDUDDDDUDDDD"

Returns: "YES"
35794

496

158

"UUUUUUUUUUUUDU"

Returns: "YES"
66025

59664

2651

"DDUUDDDDDDDDDDDUDUUDDDDDDDDUDDDDDDDDDDDDDDUD"

Returns: "YES"
95538

30372

31669

"DDDDDDU"

Returns: "NO"
29

61670

841

"UUUUDDDUUUUUDDUDDUUUDD"

Returns: "NO"
17

1

8

"UUUUUUUU"

Returns: "YES"
15

13

8

"DDDDDDDDDUDDD"

Returns: "NO"
35

14

3

"UUUUUU"

Returns: "YES"
81409

37491

3246

"UDDDDDDDDDDDDDDDD"

Returns: "YES"
33

4

9

"DDUDDDDDDDDDDDDDDDDD"

Returns: "NO"
48968

14

8

"DUUU"

Returns: "YES"
64770

3

7

"UDDUUUDUDDUUUUUUUDUUUDUUUUDUDUDUUUUDUDUUUUUUUUU"

Returns: "YES"
14646

387

9

"UUUUU"

Returns: "YES"
79695

19586

64451

"UUUUDUUUUUUUU"

Returns: "YES"
59186

9802

796

"DDDDUDUUUDDDDDDUUDDDDDDUDDDDDDUDDDUDDUDDDUUDDDDU"

Returns: "YES"
747

347

42

"DUUDDDDDDUDDDDDDDDUDDDDDDDDUDDDDDDDDDDUDDDUDDD"

Returns: "YES"
77236

50874

52914

"UUUDDDUDUDUUUUDUDDUDUUDUUUDUUDUUUDDDUUUUUDUD"

Returns: "YES"
10

12

2

"UUUU"

Returns: "NO"
26026

15327

3443

"UDDUUUDDDDUDUUUDUDDUDDDDUUDUDDUUUUDDUUU"

Returns: "YES"
44785

44634

7

"DDDUDDDDDDDDDDUDDDUDDDDDDUDDDDDUDDD"

Returns: "YES"
8639

677

98

"UUUUUUUUUU"

Returns: "YES"
55739

55584

50483

"DDDUUUDDDDDDDDDDDDDDDDUDDUDDDUDDDDDUDDDDDDUDDDDD"

Returns: "YES"
29250

27367

1659

"UUUUUDDUUUUDUUUUUDUUUUUUUDUUUDUDUDDUUUUUUUUUUUUU"

Returns: "YES"
36935

8184

1

"DDUUDUDDDUDDDDDUUDDDUDDDDUDDDDUDDDDDDDUDDDDDUDDD"

Returns: "YES"
67656

63536

58208

"DDDDDD"

Returns: "YES"
30

2

18

"UDDDDDDDDDDDDDUDDUDDDDDDUDDDDD"

Returns: "NO"
8297

644

441

"UUUUUUUUUUUUUUDDUUDUDUUUUUUUUUUUUUDUDUUDUU"

Returns: "YES"
18

65058

646

"UU"

Returns: "NO"
99999

0

0

"UD"

Returns: "NO"
4

0

0

"DDUU"

Returns: "NO"
2

0

1

"U"

Returns: "NO"
3

2

2

"UD"

Returns: "NO"
8

0

0

"DDDD"

Returns: "YES"
4

0

0

"DD"

Returns: "YES"
9

0

0

"U"

Returns: "NO"
10

1

10

"U"

Returns: "NO"
6

0

1

"UUDD"

Returns: "NO"
10000

0

0

"U"

Returns: "YES"
5

0

4

"UU"

Returns: "NO"
999

100

100

"UD"

Returns: "NO"
199

100

100

"U"

Returns: "NO"
3

10

10

"UD"

Returns: "NO"
10

0

5

"U"

Returns: "NO"
50

0

0

"DDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUU"

Returns: "NO"
100000

0

50000

"UDUDUDUD"

Returns: "YES"
3

0

1

"U"

Returns: "YES"
2

0

0

"D"

Returns: "YES"
4

4

5

"U"

Returns: "NO"
10

0

1

"U"

Returns: "NO"
8

4

0

"DDDD"

Returns: "YES"
4

0

2

"DU"

Returns: "YES"
100000

1

1

"D"

Returns: "YES"
99999

50000

50000

"U"

Returns: "NO"
1000

100000

10000

"UDDD"

Returns: "NO"
5

1

0

"DD"

Returns: "YES"
4

0

0

"DU"

Returns: "YES"
3

100

102

"U"

Returns: "NO"
2

0

0

"DU"

Returns: "NO"
3

0

2

"U"

Returns: "NO"
4

0

3

"U"

Returns: "NO"
4

0

0

"UUDD"

Returns: "YES"
15

13

0

"DDDDDDDDDDDDDD"

Returns: "YES"
1

0

1

"U"

Returns: "YES"
13

7

7

"U"

Returns: "NO"
1000

0

21

"DD"

Returns: "NO"
8

1

1

"DDDUUUD"

Returns: "NO"
3

0

0

"UD"

Returns: "NO"
3

1

0

"DD"

Returns: "YES"
3

0

1

"DU"

Returns: "YES"
2

0

0

"DD"

Returns: "NO"
100000

10001

100000

"UUUD"

Returns: "NO"
100

0

0

"DDD"

Returns: "YES"
8

0

0

"DDDDU"

Returns: "NO"
13

19

10

"DDD"

Returns: "YES"
99

99

2

"DD"

Returns: "YES"
100000

50000

50001

"U"

Returns: "NO"
5

0

2

"UD"

Returns: "NO"
10

0

2

"D"

Returns: "YES"
6

0

0

"DDUU"

Returns: "NO"
198

100

2

"U"

Returns: "YES"
1

1

0

"D"

Returns: "YES"
8

0

4

"UUUUUDD"

Returns: "YES"
10

0

0

"DD"

Returns: "YES"
6

8

7

"DDDU"

Returns: "NO"
3

0

1

"DUU"

Returns: "NO"
4

0

2

"D"

Returns: "YES"
100000

0

99999

"U"

Returns: "NO"
3

1

0

"DDU"

Returns: "NO"
6

0

2

"DD"

Returns: "YES"
100

0

0

"DDDD"

Returns: "YES"
2

3

1

"D"

Returns: "YES"
10

2

4

"DDDD"

Returns: "YES"
31

0

0

"U"

Returns: "NO"
8

0

0

"DDUU"

Returns: "YES"
100

20

10

"U"

Returns: "YES"
3

3

2

"UD"

Returns: "YES"
7

1

0

"DDUU"

Returns: "YES"
4

8

9

"UD"

Returns: "NO"
10

3

3

"DDDDUUUU"

Returns: "YES"
2

2

0

"DD"

Returns: "YES"
10

1000

1001

"UD"

Returns: "NO"
1

2

1

"U"

Returns: "NO"
6

0

2

"DDUU"

Returns: "YES"
101

21

2

"UD"

Returns: "YES"
4

0

0

"UDD"

Returns: "YES"
7

0

4

"UU"

Returns: "NO"
2

2

0

"D"

Returns: "YES"
4

1

1

"UDDU"

Returns: "YES"
6

0

0

"DDU"

Returns: "YES"
16

0

8

"DDDD"

Returns: "YES"
8

0

1

"U"

Returns: "NO"
5

3

0

"DDDUD"

Returns: "YES"
3

1

0

"D"

Returns: "YES"
100000

100000

100000

"U"

Returns: "YES"
2

0

0

"U"

Returns: "YES"
8

0

0

"DDUUUU"

Returns: "NO"
10

0

0

"DDDDU"

Returns: "YES"
4

3

1

"DUD"

Returns: "YES"
3

2

2

"U"

Returns: "NO"
100000

100000

100000

"UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU"

Returns: "YES"
6

1

3

"DDUU"

Returns: "YES"
31

0

2

"U"

Returns: "NO"
12

0

5

"DUDUUUUU"

Returns: "NO"
4

1

1

"DDU"

Returns: "YES"
5

0

1

"DUUU"

Returns: "NO"
10

0

0

"DDDDUUUU"

Returns: "NO"
2

2

2

"UD"

Returns: "YES"
6

0

0

"UDUDUD"

Returns: "YES"
1

2

1

"D"

Returns: "YES"
3

1

0

"UDD"

Returns: "YES"
8

1

2

"DDUU"

Returns: "NO"

Statistics

Problem Statement for "FoxAndMountainEasy"

Problem Statement

Definition

Constraints

Examples