USACO 2022 US Open Contest, Platinum Problem 3. Up Down Subsequence

USACO 2022 US Open Contest, Platinum Problem 3. Up Down Subsequence

Farmer John's NN cows (2N31052≤N≤3⋅105), conveniently numbered 1N1…N as usual, have ordered themselves according to a permutation p1,p2,,pNp1,p2,…,pN of 1N1…N. You are also given a string of length N1N−1 consisting of the letters U and D. Please find the maximum KN1K≤N−1 such that there exists a subsequence a0,a1,,aKa0,a1,…,aK of pp such that for all 1jK1≤j≤Kaj1<ajaj−1<aj if the jjth letter in the string is U, and aj1>ajaj−1>aj if the jjth letter in the string is D.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains NN.The second line contains p1,p2,,pNp1,p2,…,pN.

The last line contains the string.

OUTPUT FORMAT (print output to the terminal / stdout):

Write out maximum possible value of KK.

SAMPLE INPUT:

5
1 5 3 4 2
UDUD


SAMPLE OUTPUT:

4


We can choose [a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5][a0,a1,a2,a3,a4]=[p1,p2,p3,p4,p5]; the entire permutation is consistent with the string.

SAMPLE INPUT:

5
1 5 3 4 2
UUDD


SAMPLE OUTPUT:

3


We can choose [a0,a1,a2,a3]=[p1,p3,p4,p5][a0,a1,a2,a3]=[p1,p3,p4,p5].

SCORING:

• Test cases 3-4 satisfy N500N≤500.
• Test cases 5-8 satisfy N5000N≤5000.
• In test cases 9-12, the string consists of Us followed by Ds.
• Test cases 13-22 satisfy no additional constraints.

Problem credits: Danny Mittal

USACO 2022 US Open Contest, Platinum Problem 3. Up Down Subsequence 题解(翰林国际教育提供，仅供参考)

[/hide]

(Analysis by Danny Mittal)

We will refer to the string of Us and Ds as ss.

Subtask 1: N500N≤500

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

Subtask 2: N5000N≤5000

We can improve the DP from the previous subtask by noting that depending on whether sj+1sj+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)(j,k) both the smallest and the largest numbers such that there exists a subsequence of p1,,pkp1,…,pk consistent with s1sjs1…sj that ends in that number. Transitions are again constant time, so the runtime is O(N2)O(N2).

Subtask 3: ss 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 pp). Now let the number of Us in ss be jj. If there is no LIS of pp with j+1j+1, then we simply use the longest LIS that we found. Otherwise, find the first position in pp where we have an LIS of length j+1j+1, then use the longest reverse LIS that ends at or after that position to compute the answer.

The runtime is O(NlgN)O(Nlg⁡N) 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 pp consistent with each prefix of ss, and build on that subsequence to find the fastest subsequence for the next prefix of ss. Unfortunately, this idea doesn't even work for normal LIS (longest increasing subsequence), i. e. the case where ss is UUUU..., because we can have a case like

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

where the fastest increasing subsequence of length 33 is [5,6,7][5,6,7], but the fastest one of length 44 is [1,2,3,4][1,2,3,4] which doesn't build on [5,6,7][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 sjsj is D, and the next xx letters in ss are U. If the fastest subsequence aa of pp consistent with s1sjs1…sj ends at index kk, then consider finding the fastest LIS bb of length x+1x+1 in pp considering only positions from kk onwards. Say that bb ends at position kk′.

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

However, we can actually use aa and bb to create a subsequence consistent with s1sj+xs1…sj+x that ends at position kk′. If the last number ajaj in aa and the first number b0b0 in bb 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<b0aj<b0, because otherwise we could add ajaj to the beginning of bb and remove bb's last element to get an LIS of length x+1x+1 that ends earlier. Therefore, it must be that aj>b0aj>b0. However, since sjsj is D, we can actually take aa, remove ajaj, then add on b0b0, which is valid because aj1>aj>b1aj−1>aj>b1 so the D is still satisfied, and now use b0b0 to glue together aa and bb.

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

This means that our algorithm can work as follows. We divide ss 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+1 that only considers the part of pp 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 NN, as there can potentially be many segments in ss. 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)O(xlg⁡x) where xx is the number of elements we consider, the runtime of our overall algorithm is O(NlgN)O(Nlg⁡N).

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);
}
}

[/hide]