Home » 国际竞赛 » Details

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

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月5日下午6:33

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

Farmer John's $N$ cows ( $2 \leq N \leq 3 \cdot 10^{5}$ ), conveniently numbered $1 \dots N$ as usual, have ordered themselves according to a permutation $p_{1}, p_{2}, \dots, p_{N}$ of $1 \dots N$ . You are also given a string of length $N - 1$ consisting of the letters U and D. Please find the maximum $K \leq N - 1$ such that there exists a subsequence $a_{0}, a_{1}, \dots, a_{K}$ of $p$ such that for all $1 \leq j \leq K$ , $a_{j - 1} < a_{j}$ if the $j$ th letter in the string is U, and $a_{j - 1} > a_{j}$ if the $j$ th letter in the string is D.

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

The first line contains $N$ .The second line contains $p_{1}, p_{2}, \dots, p_{N}$ .

The last line contains the string.

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

Write out maximum possible value of $K$ .

SAMPLE INPUT:

5
1 5 3 4 2
UDUD

SAMPLE OUTPUT:

We can choose $[a_{0}, a_{1}, a_{2}, a_{3}, a_{4}] = [p_{1}, p_{2}, p_{3}, p_{4}, p_{5}]$ ; the entire permutation is consistent with the string.

SAMPLE INPUT:

5
1 5 3 4 2
UUDD

SAMPLE OUTPUT:

We can choose $[a_{0}, a_{1}, a_{2}, a_{3}] = [p_{1}, p_{3}, p_{4}, p_{5}]$ .

SCORING:

Test cases 3-4 satisfy $N \leq 500$ .
Test cases 5-8 satisfy $N \leq 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 $s$ .

Subtask 1: $N \leq 500$

We can do DP. For each triple $(j, k, u)$ , our DP says whether there exists a subsequence of $p_{1}, \dots, p_{k}$ consistent with $s_{1} \dots s_{j}$ that ends in the number $u$ . Transitions are constant time, so the runtime is $O (N^{3})$ .

Subtask 2: $N \leq 5000$

We can improve the DP from the previous subtask by noting that depending on whether $s_{j + 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 $p_{1}, \dots, p_{k}$ consistent with $s_{1} \dots s_{j}$ that ends in that number. Transitions are again constant time, so the runtime is $O (N^{2})$ .

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 (N \lg 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 $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 $s_{j}$ is D, and the next $x$ letters in $s$ are U. If the fastest subsequence $a$ of $p$ consistent with $s_{1} \dots s_{j}$ 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 $s_{1} \dots s_{j + x}$ must end at or after position $k^{'}$ , because clearly it's not possible to find a subsequence consistent with $s_{1} \dots s_{j}$ 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 $s_{1} \dots s_{j + x}$ that ends at position $k^{'}$ . If the last number $a_{j}$ in $a$ and the first number $b_{0}$ 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 $a_{j} < b_{0}$ , because otherwise we could add $a_{j}$ 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 $a_{j} > b_{0}$ . However, since $s_{j}$ is D, we can actually take $a$ , remove $a_{j}$ , then add on $b_{0}$ , which is valid because $a_{j - 1} > a_{j} > b_{1}$ so the D is still satisfied, and now use $b_{0}$ to glue together $a$ and $b$ .

Therefore, the end position of the fastest subsequence of $p$ consistent with $s_{1} \dots s_{j + 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 $s_{1} \dots s_{j}$ . 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 (x \lg x)$ where $x$ is the number of elements we consider, the runtime of our overall algorithm is $O (N \lg 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]