Uddered but not Herd USACO 2021 January Contest

Uddered but not Herd USACO Solution

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.

See Also: USACO 2021 January Contest

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 11 and at most 105105.

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:

3

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

Solution

Let NN denote the number of distinct letters that appear in the input string (we can disregard all other letters). Note how the scoring gives bounds on NN (rather unoriginally).

From the analysis for the Bronze version of this problem, if we are given the order of the cowphabet, then the minimum number of times the alphabet is hummed is equal to one plus the number of consecutive pairs of letters such that the first letter in the pair comes at the same position or after the second letter in the pair. Specifically, if the order of the cowphabet is c1,c2,…,cNc1,c2,…,cN, then the minimum number of times the cowphabet was hummed isevaluate([c1,c2,…,cN])=1+∑i=1N∑j=1i(# occurrences of cicj).evaluate([c1,c2,…,cN])=1+∑i=1N∑j=1i(# occurrences of cicj).

Subtask: N≤8N≤8

First, process the input string such that for any two letters c1c1 and c2c2, we know the number of occurrences of the substring c1c2c1c2. Now we can iterate over all N!N! possible orders of the cowphabet and compute the quantity above in O(N2)O(N2) time.

Time Complexity: O(N!⋅N2+length(input string))O(N!⋅N2+length(input string))

Full Solution: N≤20N≤20

Do dynamic programming on subsets. The DP state for a subset S={c1,c2,…,cn}S={c1,c2,…,cn} of the cowphabet is minp(evaluate(p))minp(evaluate(p)) over all n!n! permutations pp of SS. The DP transition for all nonempty SS is as follows:dp[S]=mincj∈S(dp[S∖{cj}]+∑ck∈S(# occurrences of cjck))dp[S]=mincj∈S(dp[S∖{cj}]+∑ck∈S(# occurrences of cjck))

Time Complexity: O(2N⋅N2+length(input string))O(2N⋅N2+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();
        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[] 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 ((mask & (1 << j)) != 0) {
                    int sum = dp[mask ^ (1 << j)];
                    for (int k = 0; k < n; ++k) if ((mask & (1 << k)) != 0) sum += adjacent[j][k];
                    dp[mask] = Math.min(dp[mask], sum);
                }
            }
        }
        System.out.println(dp[(1 << n) - 1]);
    }
}

It was possible (but not necessary) to remove a factor of NN 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⋅2N)Θ(N⋅2N) memory. We can reduce the required memory to O(2N)O(2N) 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";
}

USACO 2021 January Contest Solution

Leave a Comment

Please Click on 1 or 2 Ads to help us run this site.
+