Santa Claus and Robot
Contest: Technocup 2017 - Elimination Round 3
Difficulty rating: 1400
Tags: constructive algorithms, math

Santa Claus has Robot which lives on the infinite grid and can move along its lines. He can also, having a sequence of m points p1, p2, ..., pm with integer coordinates, do the following: denote its initial location by p0. First, the robot will move from p0 to p1 along one of the shortest paths between them (please notice that since the robot moves only along the grid lines, there can be several shortest paths). Then, after it reaches p1, it'll move to p2, again, choosing one of the shortest ways, then to p3, and so on, until he has visited all points in the given order. Some of the points in the sequence may coincide, in that case Robot will visit that point several times according to the sequence order.

While Santa was away, someone gave a sequence of points to Robot. This sequence is now lost, but Robot saved the protocol of its unit movements. Please, find the minimum possible length of the sequence.

Input format:
The first line of input contains the only positive integer n (1 ≤ n ≤ 2·105) which equals the number of unit segments the robot traveled. The second line contains the movements protocol, which consists of n letters, each being equal either L, or R, or U, or D. k-th letter stands for the direction which Robot traveled the k-th unit segment in: L means that it moved to the left, R — to the right, U — to the top and D — to the bottom. Have a look at the illustrations for better explanation.

Output format:
The only line of input should contain the minimum possible length of the sequence.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
The illustrations to the first three tests are given below.

The last example illustrates that each point in the sequence should be counted as many times as it is presented in the sequence.

Example input:
4
RURD

Example output:
2

Example input:
6
RRULDD

Example output:
2

Editorial:
Solution #1: denote by dpi the least possible number of points if the robot passed only i unit segments, and we assume that dp0 = 0. Thus, the answer to the problem is dpn. It's clear that dpk + 1 ≥ dpk for every k, so for every i ≤ n one can obtain that dpi = dpj + 1, where j is the minimal of such indices that s[j + 1... i] can be a path from one point to another. That means two constraints:
• either s[j + 1... i] doesn't contain any L, or it doesn't contain any R;
• either s[j + 1... i] doesn't contain any U, or it doesn't contain any D.
This fact is offered to the reader.
Such j can be found in O(1) if we iterate over all i-s from 1 to n and keep the last occurence of L, R, U and D. So one can, storing these occurences and dp itself, implement the algorithm above and pass each test for O(n) time.
Solution #2: since we know the way to determine whether the path is valid or not (from the first solution), let's find the longest prefix of s and say that that's a path to the first point of the required collection. Then we find the longest prefix of the remaining string and state that this is the shortest path from p1 to p2, and so on.
This greedy algorithm works (obviously, in linear time), since the first solution is in fact the same greedy algorithm applied to the reversed string.