This blog compiles what I have learned and my insights into solving problems. Some people might benefit from it, so enjoy!

Credit to USACO Guide for the problem list. Thank you so much!

Theory

• String hashing converts a string into a number by treating its characters like digits in a chosen base. For example,

$. - We can map

$ to

$ and build a number using a base

$. - We take the result modulo

$ to keep the number small. However, this creates the possibility of a collision: two different strings can have the same hash modulo

$.

Template

const ll Mod = 1000000009LL;
const ll Base = 271LL;

struct hashed_string{
    private:
    string s; ll n;
    vector <ll> prefix;
    vector <ll> pow;
    public:
    hashed_string(string a){
        s = a; n = a.size();
        prefix.assign(n, 0);
        ll sum = 0;
        pow.assign(n+1, 0);
        pow[0] = 1;
        for (int i = 1; i <= n; i++){
            pow[i] = (pow[i-1] * Base) % Mod;
        }
        for (int i = 0; i < n; i++){
            prefix[i] = ((sum * Base) % Mod + s[i] - 'a' + 1) % Mod;
            sum = prefix[i];
        }
    }
    ll get_hash(ll l, ll r){
        ll x = prefix[r];
        if (l >= 1){
            l--;
            x = ((x - prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;
        }
        return x;
    }
};

Problem List

Problem 1

Problem

• This problem uses template hashing. The number of comparisons is approximately

$. - For each candidate period length

$, compare every complete segment

$ with

$. - If the final segment is shorter than

$, compare it with the prefix of the same length.

Code

Problem 2

Problem

• This problem is interesting because deleting a phrase might create a new censored phrase.
• If we delete a segment

$, the remaining parts

$ and

$ join together. A new censored occurrence can cross this join. - This suggests changing the template from taking a complete string during initialization to starting with an empty string and allowing characters to be added one by one. - Add characters one by one. Whenever the current suffix equals the censored phrase, delete that suffix and continue. Maintain the prefix hashes alongside the characters so that deletions restore the previous state.

Code

Problem 3

Problem

• This problem combines template hashing with an optimization trick.
• Let

$ and

$ be the counts of

$ and

$ in

$. If the replacement lengths are

$ and

$, then

$. - Enumerate the replacement length for the more frequent symbol. Since

$, there are at most

$ candidate lengths. - For each candidate, calculate the other length and check the pattern using hashing in

$. This gives

$ time after hash preprocessing. - Both replacement strings must be nonempty, and they must be different.

Code

Problem 4

Problem

• Some people use hashing and consider all permutations, but I use bitmask DP; it feels simpler to me.
• First, remove any string that is a substring of another remaining string. Keep only one copy of duplicate strings.
• For every pair

$, calculate the maximum overlap between a suffix of string

$ and a prefix of string

$. - Then use bitmask DP. Let

$ represent the minimum length after combining the strings in

$ and ending with string

$. - We only need to remember the last string because we have already removed strings contained in other strings.

Code

Problem 5

Problem

• Binary search the substring length and use an

$ check, giving a total complexity of

$. - The check uses template hashing to compare the substrings.

Code

Problem 6

Problem

• This problem uses simulation from each starting position. Hash the turn information together with the distances, then calculate the extra distance needed.
• We need to distinguish straight movement, left turns, and right turns. In terms of directed turning angles, we can encode

$,

$, and

$ as three different values. - I used vectors to handle the turns. There is probably a cleaner implementation.

Code

Problem 7

Problem

• This problem is really interesting, and the key observation is hard to find.
• If we brute force every pair of strings

$ and calculate their Hamming distance, the complexity is

$. This is too slow when

$ is large. - What if we choose the approach based on which dimension is smaller? If

$ is small, use

$; if

$ is small, use

$. - This gives

$. Since

$, if

$, the work is roughly bounded by

$. - If

$ is small, brute force as described above. - If

$ is small, consider every pair of positions

$. Delete these two positions from each string by concatenating the hashes of

$,

$, and

$, treating empty ranges as empty strings. - If two resulting hashes match, the original strings differ only at the deleted positions, so their Hamming distance is at most

$.

Code

Problem 8

Problem

• This problem is misleading at first. The operation shifts all rows by the same amount

$ and all columns by the same amount

$. We choose one pair

$. - If we copy the matrix to its right, every cyclic horizontal shift becomes a contiguous window. Copying it downward does the same for vertical shifts. - The problem becomes finding the lexicographically smallest

$ submatrix in the doubled matrix. - Use 2D hashing: hash each row, then combine the row hashes vertically to support submatrix comparisons. - Consider each top-left position

$. To compare two candidates, binary search for the first differing row, then the first differing character in that row, and keep the lexicographically smaller candidate.

Code

Problem 9

Problem

• This problem seems hard at first, but the key is

$, which suggests a DP with about

$ states. - The pieces we select from the original string do not have to be adjacent. Once we have formed a prefix of the target string, we only need to know how far that prefix extends. - Let

$ be the maximum target-prefix length we can form using at most

$ pieces from the first

$ characters of the original string. - We can skip the current character. Alternatively, if

$, find the longest common prefix of the suffixes starting at

$ and

$ using hashing and binary search. - If that common-prefix length is

$, update

$ with

$.

Code

Problem 10

Problem

• This problem seems impossible at first, but the trick is clever.
• For each sequence

$, we can calculate its total Hamming distance to all other sequences. However, this does not prove that every distance equals

$: distances

$ and

$ still add up to

$. - The idea is to assign each sequence

$ a random weight

$. - Let

$ be the Hamming distance and

$. Check whether

$. - If every distance from

$ to another sequence is

$, the equality always holds. Otherwise, random weights make accidental cancellation unlikely. - We can compute the weighted distance sums efficiently by collecting the total weight for each character at each position.

Code

Extension: XOR Equality

Theory

• Assign each distinct value

$ a random hash

$. - For a set

$, define

$. - Once these hashes are maintained, comparing

$ and

$ takes

$ time. This gives a randomized check for set equality. - Each distinct value must be included once. XORing every occurrence instead only tracks the parity of its frequency.

Problem 11

Problem

• To count valid subarrays

$, use prefix states so that the state of a subarray is determined by the states at

$ and

$. - Here, we need frequencies modulo

$. Ordinary XOR tracks parity, so instead hash the vector of frequencies modulo

$. - A subarray passes this check when

$, meaning that every frequency is divisible by

$, subject to hash collisions. - But a frequency could be

$, while we need every appearing value to occur exactly

$ times. - Maintain the minimum allowed prefix index

$ so that no value appears more than

$ times in the subarray. Combined with the modulo-

$ condition, this leaves only frequencies

$ and

$.

Code Thank for reading.