Home » 国际竞赛 » Details

USACO 2021 January Contest, Gold Problem 1. Uddered but not Herd

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午4:15

USACO 2021 January Contest, Gold Problem 1. Uddered but not Herd

A little known fact about cows is that they have their own version of the alphabet, the "cowphabet". It consists of the 26 letters 'a' through 'z', but when a cow speaks the cowphabet, she lists these letters in a specific ordering that might be different from the order 'abcdefghijklmnopqrstuvwxyz' we are used to hearing.

To pass the time, Bessie's cousin Mildred has been humming the cowphabet over and over again, and Farmer Nhoj is curious how many times she's hummed it.

Given a lowercase string of letters that Farmer Nhoj has heard Mildred say, compute the minimum number of times Mildred must have hummed the entire cowphabet in order for Farmer Nhoj to have heard the given string. Farmer Nhoj isn't always paying attention to what Mildred hums, and so he might have missed some of the letters that Mildred has hummed. The string you are told consists of just the letters that he remembers hearing.

Note: the time limit per test case on this problem is twice the default.

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

The only line of input contains the string of lowercase letters that Farmer Nhoj heard Mildred say. This string has length at least $1$ and at most $10^{5}$ .

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

Print the minimum number of times Mildred must have hummed the entire cowphabet.

SAMPLE INPUT:

mildredree

SAMPLE OUTPUT:

Mildred must have hummed the cowphabet at least three times. It is possible for Mildred to have only hummed the cowphabet three times if the cowphabet starts with "mildre" and Farmer Nhoj heard the letters in uppercase as denoted below.

MILDREabcfghjknopqstuvwxyz
milDREabcfghjknopqstuvwxyz
mildrEabcfghjknopqstuvwxyz

SCORING:

In test cases 1-5, Farmer Nhoj only heard letters that appear in Mildred's or Bessie's names.
In test cases 6-16, Farmer Nhoj never heard any of the letters that appear in Mildred's name.

Problem credits: Nick Wu and Brian Dean

USACO 2021 January Contest, Gold Problem 1. Uddered but not Herd 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi, Sofia Yang)

Let $c_{1}, c_{2}, \dots, c_{N}$ be the distinct letters that appear in the input string (all other letters can be ignored). Note how the scoring gives bounds on $N$ (rather unoriginally). Specifically, $N \leq 8$ for the first few test cases and $N \leq 20$ for the remaining test cases.

For a permutation $p$ of $1 \dots N$ , define $evaluate ([p_{1}, p_{2}, \dots, p_{N}])$ to be the minimum number of times the cowphabet is hummed when the order of the cowphabet is fixed as $[c_{p_{1}}, c_{p_{2}}, \dots, c_{p_{N}}]$ . From the analysis for the Bronze version of this problem, $evaluate (p)$ equals one plus the number of consecutive substrings of the form $c_{p_{i}} c_{p_{j}}$ where $i \geq j$ .

Defining $adjacent [i] [j]$ to be the number of consecutive substrings of the form $c_{i} c_{j}$ in the input string, we may rewrite $evaluate (p)$ as:

evaluate (p) := 1 + \sum i = 1 N \sum j = 1 i adjacent [p i] [p j] .

The answer is equal is to compute the minimum of $evaluate ([p_{1}, p_{2}, \dots, p_{N}])$ over all permutations $p$ of $1 \dots N$ :

ans := min (p 1, p 2, \dots, p N) \sim (1, 2, \dots N) evaluate (p) .

Subtask: $N \leq 8$

Compute all entries of $adjacent$ in $O (length (input string))$ time. Then iterate over all $N!$ possible permutations $p$ of the cowphabet. For each $p$ , $evaluate (p)$ may be computed in $O (N^{2})$ time.

Time Complexity: $O (N! \cdot N^{2} + length (input string))$

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

int main() {
	string heard; cin >> heard;
	int n = 0; // number of unique letters
	map<char,int> index;
	for (char letter: heard) if (!index.count(letter)) index[letter] = n++;
	vector<vector<int>> adjacent(n, vector<int>(n));
	for (int j = 1; j < heard.size(); ++j)
		++adjacent[index[heard[j-1]]][index[heard[j]]];
	vector<int> p(n); iota(begin(p), end(p), 0); // 0 ... n-1
	int ans = INT_MAX;
	do {
		int cur_ans = 1;
		for (int i = 0; i < n; ++i)
			for (int j = 0; j <= i; ++j)
				cur_ans += adjacent[p[i]][p[j]];
		// now cur_ans = evaluate(p)
		ans = min(ans, cur_ans);
	} while (next_permutation(begin(p), end(p)));
	cout << ans << "\n";
}

Full Solution: $N \leq 20$

The idea is to apply dynamic programming on subsets of the cowphabet.

Let $S = {i_{1}, i_{2}, \dots, i_{n}}$ be the indices of any subset of the letters of the cowphabet ( $0 \leq n \leq N$ ). We initially defined $evaluate$ only when $p$ was a permutation of $1 \dots N$ , but observe that the definition naturally extends to the case where $p$ is a permutation of $S$ . Then similarly to our definition of $ans$ above, we may define

dp [S] = min (p 1, p 2, \dots, p n) \sim S evaluate (p) .

To compute this quantity when $S$ is nonempty, suppose that we fix $p_{n}$ , the index of the character in $S$ that appears last in the cowphabet. The minimum number of times the cowphabet needs to be sung considering only the remaining indices in $S$ is precisely $dp [S ∖ {p_{n}}]$ , and then we need to add the number of consecutive pairs between $p_{n}$ and all the letters in $S$ . Specifically, we may write

dp [S] = min p n \in S (dp [S ∖ {p n}] + \sum i \in S adjacent [p n] [i]) .

For example, for the input “abcac,” $adjacent$ would be as follows:

+===+===+===+===+
|   | a | b | c |
+===+===+===+===+
| a | 0 | 1 | 1 |
+---+---+---+---+
| b | 0 | 0 | 1 |
+---+---+---+---+
| c | 1 | 0 | 0 |
+---+---+---+---+

And the calculations would be as follows:

dp[000] = 1;
dp[001] = 1;
dp[010] = 1;

dp[011] = 1;
dp[001] + adjacent[b][b] + adjacent[b][c] = 1
dp[010] + adjacent[c][b] + adjacent[c][c] = 2

dp[100] = 1;

dp[101] = 2;
dp[001] + adjacent[a][a] + adjacent[a][c] = 2
dp[100] + adjacent[c][a] + adjacent[c][c] = 2

dp[110] = 1;
dp[010] + adjacent[a][a] + adjacent[a][b] = 2
dp[100] + adjacent[b][a] + adjacent[b][b] = 1

dp[111] = 2;
dp[011] + adjacent[a][a] + adjacent[a][b] + adjacent[a][c] = 3
dp[101] + adjacent[b][a] + adjacent[b][b] + adjacent[b][c] = 3
dp[110] + adjacent[c][a] + adjacent[c][b] + adjacent[c][c] = 2

In the code, we represent $S$ with a length $N$ bitmask $mask$ , where the $i$ 'th bit of $mask$ is 1 if $i \in S$ , and 0 otherwise. The final answer corresponds to $dp [(1 ≪ N) - 1]$ , corresponding to $S = {1, 2, \dots, N}$ .

Time Complexity: $O (2^{N} \cdot N^{2} + length (input string))$

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
 
public class UdderedButNotHerdGold {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String heard = in.readLine();
        // Index stores the index of every unique letter in the string.
        Map<Character, Integer> index = new HashMap<>();
        for (char letter : heard.toCharArray()) {
            if (!index.containsKey(letter)) {
                index.put(letter, index.size());
            }
        }
        // Number of unique letters
        int n = index.size();
        /*
         * adjacent[i][j] is the number of pairs where
         * the ith unique letter appears directly before the jth.
         */
        int[][] adjacent = new int[n][n];
        for (int j = 1; j < heard.length(); j++) {
            adjacent[index.get(heard.charAt(j - 1))][index.get(heard.charAt(j))]++;
        }
        /*
         * DP on subsets.
         * (1 means this bit is in the subset, 0 means not)
         */
        int[] dp = new int[1 << n];
        dp[0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            dp[mask] = heard.length();
            for (int j = 0; j < n; j++) {
                // If jth letter comes last in the cowphabet out of those in the subset
                if ((mask & (1 << j)) != 0) {
                    // this is the answer for the state corresponding to removing j from mask
                    int sum = dp[mask ^ (1 << j)];
                    // add the number of consecutive pairs between j and all bits in mask
                    for (int k = 0; k < n; ++k) if ((mask & (1 << k)) != 0) sum += adjacent[j][k];
                    dp[mask] = Math.min(dp[mask], sum);
                }
            }
        }
        // the answer corresponds to all n bits set
        System.out.println(dp[(1 << n) - 1]);
    }
}

It was possible (but not necessary) to remove a factor of $N$ from the runtime.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
 
public class UdderedButNotHerdGold {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String heard = in.readLine();
        Map<Character, Integer> index = new HashMap<>();
        for (char letter : heard.toCharArray()) {
            if (!index.containsKey(letter)) {
                index.put(letter, index.size());
            }
        }
        int n = index.size();
        int[][] adjacent = new int[n][n];
        for (int j = 1; j < heard.length(); j++) {
            adjacent[index.get(heard.charAt(j - 1))][index.get(heard.charAt(j))]++;
        }
        int[][] sums = new int[n][1 << n];
        int[] dp = new int[1 << n];
        dp[0] = 1;
        for (int mask = 1; mask < (1 << n); mask++) {
            dp[mask] = heard.length();
            int k = 0;
            while ((mask & (1 << k)) == 0) {
                k++;
            }
            for (int j = 0; j < n; j++) {
                sums[j][mask] = sums[j][mask - (1 << k)] + adjacent[j][k];
                if ((mask & (1 << j)) != 0) {
                    dp[mask] = Math.min(dp[mask], dp[mask - (1 << j)] + sums[j][mask]);
                }
            }
        }
        System.out.println(dp[(1 << n) - 1]);
    }
}

However, this solution uses $Θ (N \cdot 2^{N})$ memory. We can reduce the required memory to $O (2^{N})$ and the runtime by a constant factor by using two 2D arrays to store the sums rather than one:

#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

int stor1[1<<10][20], stor2[1<<10][20];
 
int main() {
	string s; cin >> s;
	map<char,int> m; for(char c: s) m[c] = 0;
	int cnt = 0; for (auto& t: m) t.s = cnt++;
	int N = m.size(); assert(N <= 20);
	vector<vector<int>> oc(N,vector<int>(N));
	for (int i = 0; i+1 < s.size(); ++i) 
		++oc[m[s[i]]][m[s[i+1]]];
	vector<int> dp(1<<N,1e9);
	dp[0] = 1;
	int bits = N/2;
	for (int j = 0; j < N; ++j) {
		for (int i = 0; i < 1<<bits; ++i) 
			for (int k = 0; k < bits; ++k) if (i&1<<k) 
				stor1[i][j] += oc[k][j];
		for (int i = 0; i < 1<<(N-bits); ++i) 
			for (int k = 0; k < N-bits; ++k) if (i&1<<k)
				stor2[i][j] += oc[bits+k][j];
	}
	for (int i = 0; i < 1<<N; ++i)
		for (int j = 0; j < N; ++j) if (i&1<<j) {
			int sum = dp[i^1<<j];
			sum += stor1[i&((1<<bits)-1)][j];
			sum += stor2[i>>bits][j];
			dp[i] = min(dp[i],sum);
		}
	cout << dp[(1<<N)-1] << "\n";
}

[/hide]