Home » 国际竞赛 » Details

USACO 2022 US Open Contest, Silver Problem 2. Subset Equality

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

USACO 2022 US Open Contest, Silver Problem 2. Subset Equality

The cows are trying out a new method of exchanging coded messages with each-other where they mix irrelevant letters in among relevant letters to make the messages hard to decode.

The cows transmit two strings? $s$ ?and? $t$ ?each of length at most? $10^{5}$ ?consisting only of the lowercase English letters 'a' through 'r'. To try and make sense of this coded message, you will be given? $Q$ ?queries ( $1 \leq Q \leq 10^{5}$ ). Each query provides a subset of the lowercase English letters from 'a' to 'r.' You need to determine for each query whether? $s$ ?and? $t$ , when restricted only to the letters in the query, are equal.

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

First line contains? $s$ .Second line contains? $t$ .

Third line contains? $Q$ .

Next? $Q$ ?lines each contain a query string. Within a query string, no letters are repeated. Furthermore, all query strings are in sorted order, and no query string appears more than once.

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

For each query, print 'Y' if? $s$ ?and? $t$ , when restricted only to the letters in the query, are equal, or 'N' otherwise.

SAMPLE INPUT:

aabcd
caabd
4
a
ac
abd
abcd

SAMPLE OUTPUT:

YNYN

For the first query, both strings become "aa" when restricted only to 'a.'

For the second query, the first string becomes "aac" while the second string becomes "caa."

SCORING:

Test case 2 satisfies? $| s |, | t |, Q \leq 1000$ .
Test cases 3-11 satisfy no additional constraints.

Problem credits: Danny Mittal

USACO 2022 US Open Contest, Silver Problem 2. Subset Equality 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Danny Mittal)

A starting point for this problem is to notice that if? $s$ ?and? $t$ ?are equal when restricted to some subset? $X$ ?of letters, then they must also be equal when restricted to any subset? $Y$ ?of? $X$ . In particular, this means that if? $s$ ?and? $t$ ?are equal when restricted to some subset? $X$ ?of letters, they are also equal when restricted to any two letters in? $X$ .

Now consider the case where? $s$ ?and? $t$ ?are not equal when restricted to? $X$ . Again let? $s^{'}$ ?and? $t^{'}$ ?be? $s$ ?and? $t$ ?restricted to? $X$ . One possibility is that? $s^{'}$ ?and? $t^{'}$ ?are of different lengths, which means that? $s$ ?and? $t$ ?have differing amounts of the letters in? $X$ .

The other possibility is that? $s^{'}$ ?and? $t^{'}$ ?have different letters at some position. In this case, consider the first position at which? $s^{'}$ ?and? $t^{'}$ ?differ, and let? $x$ ?and? $y$ ?be the two letters that? $s^{'}$ ?and? $t^{'}$ ?have at this position. Since? $s^{'}$ ?and? $t^{'}$ ?are completely the same up to this position, if we remove all letters other than? $x$ ?and? $y$ ?from? $s^{'}$ ?and? $t^{'}$ ?to create new strings? $s^{″}$ ?and? $t^{″}$ , the portion before this position will become the same (smaller) portion at the beginning of? $s^{″}$ ?and? $t^{″}$ , and so the? $x$ ?and? $y$ ?at the same position in? $s^{'}$ ?and? $t^{'}$ ?will still be in the same position in? $s^{″}$ ?and? $t^{″}$ . This means that? $s^{″}$ ?and? $t^{″}$ ?are not the same, and so, since? $s^{″}$ ?and? $t^{″}$ ?are actually just? $s$ ?and? $t$ ?restricted to the two letters? $x$ ?and? $y$ , we can conclude that? $s$ ?and? $t$ ?are not the same when restricted to? $x$ ?and? $y$ .

We have therefore shown that if? $s$ ?and? $t$ ?are not equal when restricted to? $X$ , then either they do not have the same amount of letters in? $X$ , or they are not the same when restricted to some pair of letters in? $X$ . However, we already know that if? $s$ ?and? $t$ ?are equal when restricted to? $X$ , then they must be the same when restricted to any pair of letters in? $X$ , and in this case they clearly must also have the same amount of letters in? $X$ .

This means that? $s$ ?and? $t$ ?being equal when restricted to? $X$ ?is actually?equivalent?to having the same amount of letters in? $X$ ?and being equal when restricted to any pair of letters in? $X$ .

We can use this fact to write our algorithm. We need to be able to quickly compute, for a given subset of letters? $X$ , whether? $s$ ?and? $t$ ?have the same amount of letters in? $X$ , and whether? $s$ ?and? $t$ ?are the same when restricted to any pair of letters in? $X$ .

We can make checking the first condition easy by precomputing the frequencies of each letter in each of? $s$ ?and? $t$ . This takes linear time. Then, for a given? $X$ , we simply add up the frequencies of all letters in? $X$ ?for each of? $s$ ?and? $t$ ?and check if the sums are equal.

We can make checking the second condition easy by just precomputing the answer for each pair of letters. For each pair, we can find the answer in linear time by simply reducing? $s$ ?and? $t$ ?to the strings? $s^{'}$ ?and? $t^{'}$ ?that only have the letters in the pair, then checking whether? $s^{'}$ ?and? $t^{'}$ ?are equal. Then, for a given? $X$ , we simply loop through all pairs of letters in? $X$ ?and check our precomputed answers.

The overall runtime becomes? $O (number of pairs \cdot (| s | + | t | + Q))$ ?due to the linear time precomputation for each pair and then checking each pair in constant time for each query. Since there are only? $18$ ?letters we need to consider, there are only? $\frac{18 \cdot 17}{2} = 153$ ?pairs, which is small enough for this algorithm to be reasonably efficient.

Java code:

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

public class SubsetEquality {

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        char[] s = in.readLine().toCharArray();
        char[] t = in.readLine().toCharArray();
        int[] freqsS = new int[26];
        int[] freqsT = new int[26];
        for (char x = 'a'; x <= 'z'; x++) {
            for (char letter : s) {
                if (letter == x) {
                    freqsS[x - 'a']++;
                }
            }
            for (char letter : t) {
                if (letter == x) {
                    freqsT[x - 'a']++;
                }
            }
        }
        boolean[][] compatible = new boolean[26][26];
        for (char y = 'a'; y <= 'z'; y++) {
            for (char x = 'a'; x < y; x++) {
                StringBuilder sRestricted = new StringBuilder();
                StringBuilder tRestricted = new StringBuilder();
                for (char letter : s) {
                    if (letter == x || letter == y) {
                        sRestricted.append(letter);
                    }
                }
                for (char letter : t) {
                    if (letter == x || letter == y) {
                        tRestricted.append(letter);
                    }
                }
                compatible[x - 'a'][y - 'a'] = sRestricted.toString().equals(tRestricted.toString());
            }
        }
        StringBuilder out = new StringBuilder();
        for (int q = Integer.parseInt(in.readLine()); q > 0; q--) {
            char[] subset = in.readLine().toCharArray();
            char answer = 'Y';
            int sSum = 0;
            int tSum = 0;
            for (char x : subset) {
                sSum += freqsS[x - 'a'];
                tSum += freqsT[x - 'a'];
            }
            if (sSum != tSum) {
                answer = 'N';
            }
            for (int j = 0; j < subset.length; j++) {
                for (int k = j + 1; k < subset.length; k++) {
                    if (!compatible[subset[j] - 'a'][subset[k] - 'a']) {
                        answer = 'N';
                    }
                }
            }
            out.append(answer);
        }
        System.out.println(out);
    }
}

[/hide]