Expand the Path
Contest: Educational Codeforces Round 123 (Rated for Div. 2)
Difficulty rating: 1900
Tags: brute force, combinatorics, data structures, implementation, math

Consider a grid of size $$$n \times n$$$. The rows are numbered top to bottom from $$$1$$$ to $$$n$$$, the columns are numbered left to right from $$$1$$$ to $$$n$$$.

The robot is positioned in a cell $$$(1, 1)$$$. It can perform two types of moves:

- D — move one cell down;
- R — move one cell right.

The robot is not allowed to move outside the grid.

You are given a sequence of moves $$$s$$$ — the initial path of the robot. This path doesn't lead the robot outside the grid.

You are allowed to perform an arbitrary number of modifications to it (possibly, zero). With one modification, you can duplicate one move in the sequence. That is, replace a single occurrence of D with DD or a single occurrence of R with RR.

Count the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains the single integer $$$n$$$ ($$$2 \le n \le 10^8$$$) — the number of rows and columns in the grid.

The second line of each testcase contains a non-empty string $$$s$$$, consisting only of characters D and R, — the initial path of the robot. This path doesn't lead the robot outside the grid.

The total length of strings $$$s$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
For each testcase, print a single integer — the number of cells such that there exists at least one sequence of modifications that the robot visits this cell on the modified path and doesn't move outside the grid.

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

Note:
In the first testcase, it's enough to consider the following modified paths:

- RD $$$\rightarrow$$$ RRD $$$\rightarrow$$$ RRRD $$$\rightarrow$$$ RRRDD $$$\rightarrow$$$ RRRDDD — this path visits cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 4)$$$, $$$(3, 4)$$$ and $$$(4, 4)$$$;
- RD $$$\rightarrow$$$ RRD $$$\rightarrow$$$ RRDD $$$\rightarrow$$$ RRDDD — this path visits cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 3)$$$ and $$$(4, 3)$$$;
- RD $$$\rightarrow$$$ RDD $$$\rightarrow$$$ RDDD — this path visits cells $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(2, 2)$$$, $$$(3, 2)$$$ and $$$(4, 2)$$$.

Thus, the cells that are visited on at least one modified path are: $$$(1, 1)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$, $$$(3, 4)$$$, $$$(4, 2)$$$, $$$(4, 3)$$$ and $$$(4, 4)$$$.

In the second testcase, there is no way to modify the sequence without moving the robot outside the grid. So the only visited cells are the ones that are visited on the path DRDRDRDR.

In the third testcase, the cells that are visited on at least one modified path are: $$$(1, 1)$$$, $$$(2, 1)$$$ and $$$(3, 1)$$$.

Here are the cells for all testcases:

Example input:
3
4
RD
5
DRDRDRDR
3
D

Example output:
13
9
3

Editorial:
First, get rid of the corner cases. If the string doesn't contain either of the letters, the answer is $$$n$$$.
The general solution to the problem is to consider every single way to modify the path, then find the union of them. Well, every single path is too much, let's learn to reduce the number of different sequences of modifications that we have to consider.
The main observation is that all cells that the robot can visit are enclosed in the space formed by the following two paths:
• the first 'R' is duplicated the maximum number of times, then the last 'D' is duplicated the maximum number of times;
• the first 'D' is duplicated the maximum number of times, then the last 'R' is duplicated the maximum number of times.
You can realize that by drawing the visited cells for some large test.
To show that more formally, you can consider the visited cells row by row. Let's show that for every two different visited cells in the same row, all cells in-between them can also be visited.
In general case, we want to show that we can take the prefix of the path to the left one of these cells and duplicate any 'R' on it to reach the right cell. The suffixes of the paths will remain the same as in the initial path.
If there exists an 'R' on the prefix, then we are good. Otherwise, the reason that it doesn't exist is that we duplicated 'D' too many times. Reduce that and there will be 'R' immediately after reaching the cell or earlier.
We should also show that the number of 'R's on the path to the left cell won't reach the maximum allowed amount until reaching the right cell. Use the fact that the number of 'D's on both prefixes of the paths is the same.
The other non-obvious part is that you can't reach cells outside this space. However, that can also be shown by analyzing each row independently.
Finally, about the way to calculate the area of this space. The main idea is to calculate the total number of cells outside this area and subtract it from $$$n^2$$$.
Notice that non-visited cells form two separate parts: the one above the first path and the one to the left of the second path. These are pretty similar to each other. Moreover, you can calculate them with a same function. If we replace all 'D's in the string with 'R' and vice versa, then these parts swap places. So we can calculate the upper part, swap them and calculate it again.
I think the algorithm is best described with a picture. Consider test $$$n=15$$$, $$$s=$$$ DDDRRDRRDDRRR, for example.
First, there are some rows that only have one cell visited. Then the first 'R' in the string appears. Since we duplicate it the maximum amount of times, it produces a long row of visited cells. The remaining part of the part becomes the outline of the area.
Note that the row that marks the end of the string, always ends at the last column. Thus, only at most first $$$|s|$$$ rows matter. To be exact, the amount of rows that matter is equal to the number of letters 'D' in the string.
For each letter 'D', let's calculate the number of non-visited cells in a row it goes down to.
I found the most convenient way is to go over the string backwards. We start from the row corresponding to the number of letters 'D' in the string. It has zero non-visited cells. We can maintain the number of non-visited cells in the current row. If we encounter an 'R' in the string, we add $$$1$$$ to this number. If we encounter a 'D', we add the number to the answer.
We have to stop after the first 'R' in the string. The later (well, earlier, since we are going backwards) part corresponds to the prefix of letters 'D' — the starting column on the picture.
Each of these rows have $$$1$$$ visited cell, so $$$n-1$$$ non-visited. So we can easily calculate this part as well.
Overall complexity: $$$O(|s|)$$$ per testcase.