作者： chenchen

Farmer John has N gifts labeled 1…N for his N cows, also labeled 1…N (1≤N≤18). Each cow has a wishlist, which is a permutation of all N gifts such that the cow prefers gifts that appear earlier in the list over gifts that appear later in the list.
FJ was lazy and just assigned gift i to cow i for all i. Now, the cows have gathered amongst themselves and decided to reassign the gifts such that after reassignment, every cow ends up with the same gift as she did originally, or a gift that she prefers over the one she was originally assigned.
There is also an additional constraint: a gift may only be reassigned to a cow if it was originally assigned to a cow of the same type (each cow is either a Holstein or a Guernsey). Given Q (1≤Q≤min(105,2N)) length-N breed strings, for each one count the number of reassignments that are consistent with it.
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N.
The next N lines each contain the preference list of a cow. It is guaranteed that each line forms a permutation of 1…N.
The next line contains Q.
The final Q lines each contain a breed string, each N characters long and consisting only of the characters G and H. No breed string occurs more than once.
OUTPUT FORMAT (print output to the terminal / stdout):
For each breed string, print the number of reassignments that are consistent with it on a new line.
SAMPLE INPUT:
4
1 2 3 4
1 3 2 4
1 2 3 4
1 2 3 4
5
HHHH
HHGG
GHGH
HGGG
GHHG
SAMPLE OUTPUT:
2
1
1
2
2
In this example, for the first breed string, there are two possible reassignments:
The original assignment: cow 1 receives gift 1, cow 2 receives gift 2, cow 3 receives gift 3, and cow 4 receives gift 4.
Cow 1 receives gift 1, cow 2 receives gift 3, cow 3 receives gift 2, and cow 4 receives gift 4.
For the second breed string, the only reassignment consistent with it is the original assignment.
SCORING:
For T=2,…,13, test case T satisfies N=T+4.
Test cases 14-18 satisfy N=18.
Problem credits: Benjamin Qi

Bessie has a new cell phone with nine buttons, laid out as follows:
123
456
789
Bessie is trying to type out a given phone number in a hurry, so she decides to save time by pressing multiple buttons at the same time with one of her hooves. Specifically, Bessie's hoof might press a single digit, two digits that share a side (for twelve possible pairs in total), or four digits that form a square (1245, 2356, 4578, or 5689).
For example, if the phone number Bessie is trying to type is 123659874, she might attempt to save time by
Pressing 1 and 2 at the same time.
Pressing 3.
Pressing 6, 5, 9, and 8 at the same time.
Pressing 7 and 4 at the same time.
Unfortunately, Bessie drastically overestimated her skill at performing this task - if Bessie's hoof pressess multiple buttons at the same time, then all of the digits will be typed in arbitrary order. So if Bessie attempts the above sequence of presses, she may end up typing 123596847 or 213659874 instead (or one of many other possibilities).
Given a sequence of digits that Bessie has typed, count the number of phone numbers that she could have been trying to type modulo 109+7.
**Note: the time limit for this problem is 4s, twice the default.**
INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases to solve.
The next T lines each contain a nonempty string of the digits 1 through 9. It is guaranteed that the total length of these strings does not exceed 105.
OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, the number of phone numbers Bessie might have been trying to type modulo 109+7.
SAMPLE INPUT:
5
1478
4455
5968
31313211
123659874
SAMPLE OUTPUT:
5
2
24
3
255
For the first case, Bessie might be trying to type any of the following five phone numbers:
1478
1487
4178
4187
1748
For example, if Bessie was trying to type 4187, she might have tried pressing 1 and 4 at the same time and then tried pressing 7 and 8 at the same time.
For the third case, as the numbers form a square, Bessie might have been trying to type any permutation of the input sequence.
SCORING:
In inputs 2-3, all phone numbers have length at most 8.
In inputs 4-5, the phone number only contains 1, 2, and 3.
In inputs 6-7, the phone number doesn't contain the digit 5.
In inputs 8-9, the phone number only contains 5, 6, 8, and 9.
In inputs 10-12, the sum of the string lengths does not exceed 102.
In inputs 13-15, the sum of the string lengths does not exceed 103.
In inputs 16-18, the sum of the string lengths does not exceed 104.
In inputs 19-21, no additional constraints.
Problem credits: Nick Wu

Bessie the cow was excited to recently return to in-person learning! Unfortunately, her instructor, Farmer John, is a very boring lecturer, and so she ends up falling asleep in class often.
Farmer John has noticed that Bessie has not been paying attention in class. He has asked another student in class, Elsie, to keep track of the number of times Bessie falls asleep in a given class. There are N class periods (2≤N≤10^5), and Elsie logs that Bessie fell asleep ai times (1≤ai≤10^18) in the i-th class period. The total number of times Bessie fell asleep across all class periods is at most 1018.

Elsie, feeling very competitive with Bessie, wants to make Farmer John feel like Bessie is consistently falling asleep the same number of times in every class -- making it appear that the issue is entirely Bessie's fault, with no dependence on Farmer John's sometimes-boring lectures.

The only ways Elsie may modify the log are by combining two adjacent class periods or splitting a class period into two. For example, if a=[1,2,3,4,5], then if Elsie combines the second and third class periods the log will become [1,5,4,5]. If Elsie then chooses to split the third class period into two, the log can become any of [1,5,0,4,5], [1,5,1,3,5], [1,5,2,2,5], [1,5,3,1,5], or [1,5,4,0,5].

Given Q (1≤Q≤10^5) candidates q1,…,qQ for Bessie's least favorite number (1≤qi≤1018), for each of them help Elsie compute the minimum number of modifications to the log that she needs to perform so that all the numbers in the log become the same.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of each test case contains N, and the second contains a1,a2,…,aN. The third contains Q, followed by Q lines each containing an integer qi, a candidate for Bessie's least favorite number.
OUTPUT FORMAT (print output to the terminal / stdout):
For each qi, compute the minimum number of modifications required for Elsie to convert every entry of the log into qi, or −1 if it is impossible.
SAMPLE INPUT:
6
1 2 3 1 1 4
7
1
2
3
4
5
6
12
SAMPLE OUTPUT:
6
6
4
5
-1
4
5
Elsie needs at least four modifications to convert the log into all 3s.

1 2 3 1 1 4
-> 3 3 1 1 4
-> 3 3 1 5
-> 3 3 6
-> 3 3 3 3
It is impossible for Elsie to convert the log into all 5s, which is why the correct output for that candidate is −1.

SCORING:
In test cases 2-4, N,Q≤5000
In test cases 5-7, all ai are at most 109.
Test cases 8-26 satisfy no additional constraints.
Problem credits: Jesse Choe and Benjamin Qi

After her previous artwork was met with critical acclaim, Bessie was offered a job designing painting sets. She designs these paintings by choosing 1≤N≤105 axis-aligned rectangles in the plane such that no two edges are collinear. The boundaries of these rectangles define the boundaries of the painting's colored regions.
Still being an avant-garde artist, Bessie decides that the painting should resemble a Holstein cow. More specifically, each region formed by the rectangles is colored either black or white, no two adjacent regions have the same color, and the region outside of all the rectangles is colored white.

After choosing the rectangles, Bessie would like you to output one of two things based on a parameter T:

If T=1, output the total number of regions.
If T=2, output the number of white regions followed by the number of black regions.
**Note: the time limit for this problem is 4s, twice the default.**

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N and T.
The next N lines each contain the description of a rectangle in the form (x1,y1),(x2,y2) where 1≤x1<x2≤2N and 1≤y1<y2≤2N. (x1,y1) and (x2,y2) are the bottom left and top right corners of the rectangle respectively.

It is guaranteed that all the xi form a permutation of 1…2N, and the same holds for all the yi.

OUTPUT FORMAT (print output to the terminal / stdout):
A single integer if T=1, otherwise two separated by spaces.
SAMPLE INPUT:
2 1
1 1 3 3
2 2 4 4
SAMPLE OUTPUT:
4
There are two white regions and two black regions, for a total of four regions. The boundaries of all rectangles are connected, so this input would satisfy the conditions of subtask 3.

SAMPLE INPUT:
5 2
1 5 3 6
5 4 7 9
4 1 8 3
9 8 10 10
2 2 6 7
SAMPLE OUTPUT:
4 5
The boundary of the rectangle in the upper-right is not connected to the rest of the boundaries, so this input would not satisfy the conditions of subtask 4.

SCORING:
Test cases 3-4 satisfy N≤103.
In test cases 5-7, no two rectangle boundaries intersect.
In test cases 8-10, T=1 and the boundaries of all rectangles are connected.
In test cases 11-13, T=2 and the boundaries of all rectangles are connected.
In test cases 14-18, T=1.
In test cases 19-23, T=2.
Problem credits: Andi Qu

Farmer John has conducted an extensive study of the evolution of different cow breeds. The result is a rooted tree with N (2≤N≤105) nodes labeled 1…N, each node corresponding to a cow breed. For each i∈[2,N], the parent of node i is node pi (1≤pi<i), meaning that breed i evolved from breed pi. A node j is called an ancestor of node i if j=pi or j is an ancestor of pi.

Every node i in the tree is associated with a breed having an integer number of spots si. The "imbalance" of the tree is defined to be the maximum of |si−sj| over all pairs of nodes (i,j) such that j is an ancestor of i.

Farmer John doesn't know the exact value of si for each breed, but he knows lower and upper bounds on these values. Your job is to assign an integer value of si∈[li,ri] (0≤li≤ri≤10^9) to each node such that the imbalance of the tree is minimized.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains T (1≤T≤10), the number of independent test cases to be solved, and an integer B∈{0,1}.
Each test case starts with a line containing N, followed by N−1 integers p2,p3,…,pN.

The next N lines each contain two integers li and ri.

It is guaranteed that the sum of N over all test cases does not exceed 105.

OUTPUT FORMAT (print output to the terminal / stdout):
For each test case, output one or two lines, depending on the value of B.
The first line for each test case should contain the minimum imbalance.

If B=1, then print an additional line with N space-separated integers s1,s2,…,sN containing an assignment of spots that achieves the above imbalance. Any valid assignment will be accepted.

SAMPLE INPUT:
3 0
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10
SAMPLE OUTPUT:
3
1
4
For the first test case, the minimum imbalance is 3. One way to achieve imbalance 3 is to set [s1,s2,s3]=[4,1,7].

SAMPLE INPUT:
3 1
3
1 1
0 100
1 1
6 7
5
1 2 3 4
6 6
1 6
1 6
1 6
5 5
3
1 1
0 10
0 1
9 10
SAMPLE OUTPUT:
3
3 1 6
1
6 5 5 5 5
4
5 1 9
This input is the same as the first one aside from the value of B. Another way to achieve imbalance 3 is to set [s1,s2,s3]=[3,1,6].

SCORING:
Test cases 3-4 satisfy li=ri for all i.
Test cases 5-6 satisfy pi=i−1 for all i.
Test cases 7-16 satisfy no additional constraints.
Within each subtask, the first half of the test cases will satisfy B=0, and the rest will satisfy B=1.

Problem credits: Andrew Wang

(Analysis by Benjamin Qi)
First, discard all occurrences of ×1 since they don't affect the answer. Also, if a program contains an occurrence of ×0, discard the portion of the program before the last such occurrence.

Say that two instructions are of the same type if they are both ×d or both +s. When do two interleaved programs produce the same expression? It turns out that this happens if and only if one interleaved program can be transformed into the other by repeatedly swapping two adjacent instructions of the same type, where one of the instructions belongs to Bessie and the other belongs to Elsie.

Therefore, the number of distinct expressions is precisely the number of interleaved programs that do not contain a pair of adjacent instructions of the same type where the first instruction belongs to Elsie and the second instruction belongs to Bessie, because every such program that contains such a pair can be uniquely transformed via a series of swaps into a program that does not contain such a pair (while there exists such a pair, swap the two instructions in the pair).

The full solution involves dynamic programming on a grid. In the code below, dp[i][j][k] is the number of ways to interleave the first i instructions of Bessie's program with the first j instructions of Elsie's program such that the last instruction in the interleaving belongs to Bessie if k=0 or Elsie if k=1. dp[i][j][k] is used to update both dp[i][j+1][1] (if Elsie adds her j-th instruction to the end of the interleaving) and dp[i+1][j][0] (if Bessie adds her i-th instruction to the end of the interleaving) unless Elsie last added to the interleaving and the j−1-th instruction of Elsie's program has the same type as the i-th instruction of Bessie's program.

The overall time complexity is proportional to the number of DP states, which is O(N2).

#include <bits/stdc++.h>
using namespace std;

template <class T> using V = vector<T>;

const int MOD = 1e9 + 7;
void mod_add(int &a, int b) { a = (a + b) % MOD; }

void read(string &s) {
string _s;
cin >> _s;
for (char c : _s) {
if (c == '1') continue;
if (c == '0') s.clear();
if (c != '+') c = '2';
s += c;
}
}

int solve() {
int N;
cin >> N;
string A, B;
read(A);
read(B);
V<V<array<int, 2>>> dp((int)size(A) + 1,
V<array<int, 2>>((int)size(B) + 1));
int ans = 0;
auto upd = [&](int x, int y, int k, int v) {
if (x <= (int)size(A) && y <= (int)size(B))
mod_add(dp.at(x).at(y).at(k), v);
};
dp.at(0).at(0).at(0) = 1;
for (int i = 0; i <= (int)size(A); ++i) {
for (int j = 0; j <= (int)size(B); ++j) {
for (int k : {0, 1}) {
int v = dp.at(i).at(j).at(k);
if (v == 0) continue;
if (i == (int)size(A) && j == (int)size(B)) mod_add(ans, v);
else {
upd(i, j + 1, 1, v);
if (k == 0) upd(i + 1, j, 0, v);
else {
assert(j > 0);
if (i < (int)size(A) && B.at(j - 1) != A.at(i))
upd(i + 1, j, 0, v);
}
}
}
}
}
return ans;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) cout << solve() << "\n";
}

A program consists of a sequence of instructions, each of which is of one of the following forms:

×d, where d is a digit in the range [0,9]
+s, where s is a string denoting the name of a variable. Within a program, all variable names must be distinct.
The result of executing a program is defined to be the expression that results after applying each instruction in order, starting with 0. For example, the result of executing the program [×3,+x,+y,×2,+z] is the expression (0×3+x+y)×2+z=2×x+2×y+z. Different programs, when executed may produce the same expressions; for example, executing [+w,×0,+y,+x,×2,+z,×1] would also result in the expression 2×x+2×y+z.

Bessie and Elsie each have programs of N (1≤N≤2000) instructions. They will interleave these programs to produce a new program of length 2N. Note that there are (2N)!N!×N! ways to do this, but not all such programs, when executed, will produce distinct expressions.

Count the number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved program, modulo 109+7.

Each input contains T (1≤T≤10) test cases that should be solved independently. It is guaranteed that the sum of N over all test cases does not exceed 2000.

INPUT FORMAT (input arrives from the terminal / stdin):
The first line of the input contains T, the number of test cases.
The first line of each test case contains N.

The second line of each test case contains Bessie's program, represented by a string of length N. Each character is either a digit d∈[0,9], representing an instruction of type 1, or the character +, representing an instruction of type 2.

The third line of each test case contains Elsie's program in the same format as Bessie's.

Within a test case, the variable names among all instructions are distinct. Note that their actual names are not provided, as they do not affect the answer.

OUTPUT FORMAT (print output to the terminal / stdout):
The number of distinct expressions that may be produced by executing Bessie and Elsie's interleaved programs, modulo 109+7.
SAMPLE INPUT:
4
1
0
1
3
12+
+02
3
0++
++9
4
5+++
+6+1
SAMPLE OUTPUT:
1
3
9
9
For the first test case, the two possible interleaved programs are [×1,×0] and [×0,×1]. These will both produce the expression 0 when executed.

For the second test case, executing an interleaving of [×1,×2,+x] and [+y,×0,×2] could produce one of the expressions 0, x, or 2×x.

SCORING:
Input 2 satisfies N≤6.
In inputs 3-5, the sum of all N is at most 100.
In inputs 6-8, the sum of all N is at most 500.
Inputs 9-16 satisfy no additional constraints.
Problem credits: Benjamin Qi

(Analysis by Danny Mittal)
Visualize the cows and apples as being on a plane where position is the x-axis and time is the y-axis. For a given cow that arrives at time t to position x, the possible apples that that cow could catch are the ones landing at time t′ at position x′ that satisfy t′≥t and |x′−x|≤|t′−t|. This region in the plane is a sort of infinite V shape with 45 degree angles extending upwards from the point (x,t).

If we rotate the entire plane 45 degrees clockwise (transform each point (x,t) to (u,v)=(t+x2√,t−x2√)), then those infinite V shapes become infinite squares, which means that the condition for a cow (u,v) to be able to catch an apple (u′,v′) is simply u≤u′ and v≤v′.

Let's use that transformation. We can simply ignore the 2–√ factor as it doesn't change the condition. For now, we will assume that n is 1, so each line of the input represents a single cow or apple.

We can take a greedy approach to this problem. Consider the apple a with smallest v, assuming that it can be caught by at least one cow, and out of all cows that could catch it, consider the cow c with largest u. There is no apple that c can catch that any other cow that can catch a cannot catch, because all of them have u at most the u of c, and since they can all catch a, all of them have a v not larger than the v of any apple that can be caught at all. Therefore, it is optimal to assign c to catch a.

Based on this greedy principle, we can devise an algorithm to solve this problem. First, sort all the cows and all the apples by v. Now, for each apple in increasing order of v, we will find the optimal cow to catch it. We will do this by maintaining a BST (binary search tree) of the cows that have v at most the v of the current apple, with the BST being sorted by u. For each apple a, we will first add in all the cows with v at most the v of a that haven't been added yet. Then, we will query our BSTs to find the cow in the BST with the largest u such that the u is still small enough to catch a. If there is such a cow, then we use it to catch a, meaning that we remove it from the BST and increment our answer.

This algorithm runs in O(NlgN) as we add and remove each cow to/from the BST at most once, and we query the BST once for each apple.

It remains to handle the fact that each line of the input can represent multiple cows or apples. To handle this, we modify the part where we find the optimal cow to catch each apple. We will instead repeatedly find the optimal group of cows for the current group of apples, and assign as many cows as possible to apples. At each step of this algorithm, either the group of cows will be exhausted, or the group of apples will be exhausted. Therefore, the amount of steps is N, and so this algorithm still runs in O(NlgN).

Java code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class AppleCatching {

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
List<Stuff> cows = new ArrayList<>();
List<Stuff> apples = new ArrayList<>();
for (int j = 1; j <= n; j++) {
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
int q = Integer.parseInt(tokenizer.nextToken());
int time = Integer.parseInt(tokenizer.nextToken());
int location = Integer.parseInt(tokenizer.nextToken());
int amount = Integer.parseInt(tokenizer.nextToken());
int y = time - location;
int x = time + location;
(q == 1 ? cows : apples).add(new Stuff(amount, y , x));
}
Collections.sort(cows, Comparator.comparingInt(cow -> cow.y));
Collections.sort(apples, Comparator.comparingInt(apple -> apple.y));
TreeSet<Stuff> treeSet = new TreeSet<>((cow1, cow2) -> {
if (cow1.x != cow2.x) {
return cow1.x - cow2.x;
} else {
return cow1.y - cow2.y;
}
});
int j = 0;
int answer = 0;
for (Stuff apple : apples) {
while (j < cows.size() && cows.get(j).y <= apple.y) {
treeSet.add(cows.get(j));
j++;
}
int amount = apple.amount;
while (amount > 0 && !treeSet.isEmpty() && treeSet.first().x <= apple.x) {
Stuff cow = treeSet.floor(new Stuff(0, 1000000000, apple.x));
treeSet.remove(cow);
int caught = Math.min(amount, cow.amount);
answer += caught;
amount -= caught;
if (caught < cow.amount) {
treeSet.add(new Stuff(cow.amount - caught, cow.y, cow.x));
}
}
}
System.out.println(answer);
}

static class Stuff {
final int amount;
final int y;
final int x;

Stuff(int amount, int y, int x) {
this.amount = amount;
this.y = y;
this.x = x;
}
}
}

It's raining apples! At certain points in time, some number of apples will hit the number line. At certain points in time, some of Farmer John's cows will arrive on the number line and start catching apples.

If an apple hits the number line without a cow to catch it, it is lost forever. If a cow and an apple arrive at the same time, the cow catches it. Each cow can travel one unit per second. Once a cow catches a single apple, she exits the number line.

If FJ's cows collaborate optimally, how many apples can they catch in total?

INPUT FORMAT (input arrives from the terminal / stdin):
The first line contains N (1≤N≤2⋅105), the number of times apples hit the number line or FJ's cows appear.
The next N lines each contain four integers qi, ti, xi, and ni (qi∈{1,2},0≤ti≤109,0≤xi≤10^9,1≤ni≤10^3).

If qi=1, this means that ni of FJ's cows arrive on the number line at time ti at location xi.
If qi=2, this means that ni apples will hit the number line at time ti at location xi.
It is guaranteed that all of the ordered pairs (ti,xi) are distinct.

OUTPUT FORMAT (print output to the terminal / stdout):
The maximum number of apples FJ's cows may collectively catch.
SAMPLE INPUT:
5
2 5 10 100
2 6 0 3
2 8 10 7
1 2 4 5
1 4 7 6
SAMPLE OUTPUT:
10
In this example, none of the 100 apples that land at time t=5 may be caught. Here is a way for 10 apples to be caught:

All six of FJ's cows that arrive at time t=4 catch one of the apples that land at time t=8.
One of FJ's cows that arrive at time t=2 catches one of the apples that land at time t=8.
Three of the remaining cows that arrive at time t=2 catch one of the apples that land at time t=6.
SAMPLE INPUT:
5
2 5 10 100
2 6 0 3
2 8 11 7
1 2 4 5
1 4 7 6
SAMPLE OUTPUT:
9
Here again, none of the apples that land at time t=5 may be caught. Furthermore, none of the cows that arrive at time t=2 may catch any of the apples that land at time t=8. Here is a way for 9 apples to be caught:

All six of FJ's cows that arrive at time t=4 catch one of the apples that land at time t=8.
Three of the remaining cows that arrive at time t=2 catch one of the apples that land at time t=6.
Problem credits: Benjamin Qi

(Analysis by Danny Mittal)
We will refer to the string of Us and Ds as s.

Subtask 1: N≤500

We can do DP. For each triple (j,k,u), our DP says whether there exists a subsequence of p1,…,pk consistent with s1…sj that ends in the number u. Transitions are constant time, so the runtime is O(N3).

Subtask 2: N≤5000

We can improve the DP from the previous subtask by noting that depending on whether sj+1 is U or D, it's optimal for the previous number in the subsequence to be as small or as large as possible. Therefore, our DP should find for each pair (j,k) both the smallest and the largest numbers such that there exists a subsequence of p1,…,pk consistent with s1…sj that ends in that number. Transitions are again constant time, so the runtime is O(N2).

Subtask 3: s is Us followed by Ds

Apply a standard LIS algorithm to find for each number the longest LIS ending in that number, as well as the longest LIS ending in that number that goes in reverse (starting from the end of p). Now let the number of Us in s be j. If there is no LIS of p with j+1, then we simply use the longest LIS that we found. Otherwise, find the first position in p where we have an LIS of length j+1, then use the longest reverse LIS that ends at or after that position to compute the answer.

The runtime is O(NlgN) using an appropriate LIS algorithm.

Subtask 4: No additional constraints

Intuitively, it makes sense for us to try to find the fastest (ending the earliest) subsequence of p consistent with each prefix of s, and build on that subsequence to find the fastest subsequence for the next prefix of s. Unfortunately, this idea doesn't even work for normal LIS (longest increasing subsequence), i. e. the case where s is UUUU..., because we can have a case like

p=[5,6,7,1,2,3,4]

where the fastest increasing subsequence of length 3 is [5,6,7], but the fastest one of length 4 is [1,2,3,4] which doesn't build on [5,6,7] at all.

However, it turns out that we can actually apply this idea when switching from contiguous segments of U to contiguous segments of D and vice versa. Specifically, suppose that sj is D, and the next x letters in s are U. If the fastest subsequence a of p consistent with s1…sj ends at index k, then consider finding the fastest LIS b of length x+1 in p considering only positions from k onwards. Say that b ends at position k′.

It's clear that the fastest subsequence of p consistent with s1…sj+x must end at or after position k′, because clearly it's not possible to find a subsequence consistent with s1…sj then an LIS of length x+1 that starts with the previous subsequence prior to k′.

However, we can actually use a and b to create a subsequence consistent with s1…sj+x that ends at position k′. If the last number aj in a and the first number b0 in b are the same, then we're done, because we can simply attach them at that number. Otherwise, note that it can't be that aj<b0, because otherwise we could add aj to the beginning of b and remove b's last element to get an LIS of length x+1 that ends earlier. Therefore, it must be that aj>b0. However, since sj is D, we can actually take a, remove aj, then add on b0, which is valid because aj−1>aj>b1 so the D is still satisfied, and now use b0 to glue together a and b.

Therefore, the end position of the fastest subsequence of p consistent with s1…sj+x is simply the end position of the fastest LIS of p considering only positions starting from the end position of the fastest subsequence consistent with s1…sj. All of this also applies when U and D are switched.

This means that our algorithm can work as follows. We divide s into its contiguous segments of U and D, and for each segment find the fastest LIS or LDS of the length of the segment +1 that only considers the part of p starting (inclusive) from the end of the previous LDS or LIS. We finish when we are unable to find an LIS or LDS of the appropriate length for some segment and simply use the longest one we were able to find for that last segment to compute the answer.

To find LISs and LDSs, we can simply apply one of the standard algorithms for finding LIS, but we have to be careful that the algorithm we use runs in time a function of the number of elements we consider, not a function of N, as there can potentially be many segments in s. An elegant choice given this constraint is the binary search tree algorithm for LIS, which is used in the Java code below.

Assuming our LIS algorithm runs in O(xlgx) where x is the number of elements we consider, the runtime of our overall algorithm is O(NlgN).

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class UpDownSubsequence {

public static void main(String[] args) throws IOException {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(in.readLine());
StringTokenizer tokenizer = new StringTokenizer(in.readLine());
char[] directions = in.readLine().toCharArray();
int k = 0;
int last = Integer.parseInt(tokenizer.nextToken());
while (tokenizer.hasMoreTokens() && k < directions.length) {
char direction = directions[k];
TreeSet<Integer> treeSet = new TreeSet<Integer>(direction == 'U' ? Comparator.naturalOrder() : Comparator.reverseOrder());
treeSet.add(last);
while (tokenizer.hasMoreTokens() && k < directions.length && directions[k] == direction) {
last = Integer.parseInt(tokenizer.nextToken());
Integer displaced = treeSet.higher(last);
if (displaced == null) {
k++;
} else {
treeSet.remove(displaced);
}
treeSet.add(last);
}
}
System.out.println(k);
}
}