This blog is for compiling my learning and my way of thinking when solving a problem. Some people might benefit from this, so enjoy!
CREDIT TO USACO.GUIDE. THE PROBLEMS ARE FROM THERE. THANK YOU SO MUCH!
Theory
- Hashing is a way to convert a string/number into a number using the idea of base conversion. For example, $$$10_{10}=1010_2$$$.
- So we convert a string by mapping each character $$$a,b,c,\ldots,z$$$ to $$$1,2,3,\ldots,26$$$ and treating them as digits in a chosen base.
- But we take the result modulo $$$\mathrm{Mod}$$$ to make sure the number doesn't explode. This creates a collision probability: two different strings can have the same hash modulo $$$\mathrm{Mod}$$$.
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;
}
};
Big Hash + Random Base
- To make the hash harder to hack, we can use a big mod and choose a random base each time the program runs.
- Here, $$$\mathrm{Mod}=10^{18}+3$$$, which is prime. But now multiplying two numbers can overflow a
long long, so we use__int128before taking the modulo. - The base is generated once and shared by all hashed strings, so we can still compare their hashes, RANDOM THE MOD OUT OF LIST IF DOING IT IN CF.
- This makes fixed anti-hash tests much harder to use, but collisions are still possible.
- Use this instead of the template above.
get_hash(l,r)still uses 0-based, inclusive indices, and the character mapping is for lowercaseatoz.
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
const ll Mod = 1'000'000'000'000'000'003LL;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll Base = uniform_int_distribution<ll>(257, Mod - 2)(rng);
ll mul(ll a, ll b){
return (__int128)a * b % Mod;
}
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] = mul(pow[i-1], Base);
}
for (int i = 0; i < n; i++){
prefix[i] = (mul(sum, Base) + 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 - mul(prefix[l], pow[r - l]) + Mod) % Mod;
}
return x;
}
};
Problem List
Problem 1
- This problem is template hashing. The complexity comes from $$$\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+\cdots$$$, which is around $$$O(N\log N)$$$.
- For every possible period length $$$i$$$, compare each full segment $$$[j,j+i-1]$$$ with the segment $$$[0,i-1]$$$.
- Then compare the leftover suffix with the part of the prefix that has the same length.
Problem 2
- This problem is great because you can't just delete a phrase and forget about it. Deleting a phrase might create a new censored phrase.
- So we can find an intuition like this: if I delete the phrase $$$[i,j]$$$, the two segments before and after it join together and might create a new censored word.
- We can change the template from taking a string in its initialization to starting with an empty string and allowing characters to be added one by one.
- The new censored word must be around the place where we deleted the previous word. So we add characters one by one until the ending equals the censored word, delete that suffix, and keep going.
- We also remove the corresponding prefix hashes when we delete characters.
Problem 3
- This problem is template hashing + an optimization trick.
- Consider the counts of $$$0$$$ and $$$1$$$. We can brute force the replacement length of the symbol with the larger count.
- This works because $$$\max(\mathrm{cnt}[0],\mathrm{cnt}[1])\ge\left\lceil\frac{|s|}{2}\right\rceil$$$, where $$$|s|$$$ is the length of the pattern.
- So there are only around $$$O\left(\frac{|t|}{|s|}\right)$$$ lengths to try. For each one, we calculate the other length and check the whole pattern in $$$O(|s|)$$$ using hashing. Therefore, the total is $$$O(|t|)$$$ after preprocessing.
- Remember that the two replacement strings must be nonempty and different.
Problem 4
- Some people hash the strings and consider all permutations, but I do bitmask DP (simpler ngl).
- So the way to do this problem is to consider all pairs $$$(i,j)$$$ where string $$$i$$$ is put after string $$$j$$$. We consider how much of the suffix of $$$j$$$ overlaps with the prefix of $$$i$$$.
- If $$$i$$$ is a substring of $$$j$$$, then we shouldn't consider $$$i$$$ at all. For equal strings, keep only one.
- Then do bitmask DP: $$$dp[\mathrm{mask}][i]$$$ represents the minimum length after putting the strings in $$$\mathrm{mask}$$$ into one string and ending with string $$$i$$$.
- We only need to consider the last string because we have already removed the situation where one string is contained in another.
Problem 5
- This problem uses binary search on the length and an $$$O(NM)$$$ check, so the total complexity is $$$O(NM\log M)$$$.
- The problem uses template hashing, so no need to explain the template again.
Problem 6
- This problem is simulation from each position. We hash the angles and the distances, then take the minimum extra distance she needs.
- Encode straight movement, left turns, and right turns as different values. For example, straight movement $$$\to 1$$$, a $$$90^\circ$$$ corner $$$\to 2$$$, and a $$$270^\circ$$$ corner $$$\to 3$$$.
- To handle the angles, I used vectors (there is probably better code).
Problem 7
- This problem is really interesting, and the clue is pretty hard to find.
- At first, if we brute force every pair of strings $$$(i,j)$$$ and find the cost, the complexity would be $$$O(N^2K)$$$, which would TLE if $$$N$$$ is big. So what if we could guarantee that we only use this approach when $$$N$$$ is small?
- That brings us to an insight like sqrt decomposition: if $$$N$$$ is big, we use $$$O(NK^2)$$$; otherwise, we use $$$O(N^2K)$$$.
- So we choose the smaller one, giving $$$O(NK\min(N,K))$$$. With $$$NK\le 3\cdot10^4$$$, the maximum amount of work is around $$$3\cdot10^4\sqrt{3\cdot10^4} \lt 6\cdot10^6$$$ operations.
- If $$$N$$$ is small, we brute force as above.
- If $$$K$$$ is small, we consider every pair of positions $$$(i,j)$$$ with $$$i \lt j$$$. These are the positions where two strings might differ.
- We delete positions $$$i$$$ and $$$j$$$ by merging the hashes of $$$[0,i-1]$$$, $$$[i+1,j-1]$$$, and $$$[j+1,K-1]$$$, treating empty ranges as empty strings.
- For every string, we check whether any pair $$$(i,j)$$$ gives the same remaining hash as another string. If it does, the two strings differ in at most $$$2$$$ positions.
Problem 8
- This problem is misleading at first. The problem states CYCLIC SHIFT OF ROWS AND COLUMNS, which means shift all rows by $$$x$$$, then shift all columns by $$$y$$$. You choose $$$(x,y)$$$.
- So we can convert the problem like this: if we create a copy of the block and put it to the right of the original, we can generate all blocks after shifting the rows.
- Then we do that again downward to generate all blocks after shifting the columns.
- So the problem is converted to finding the lexicographically smallest $$$n\times m$$$ submatrix in the big matrix.
- We use 2D hashing: hash each row, then use the adding-hashes idea from the USACO problem to create a vertical prefix hash of the row hashes.
- Then we consider each position $$$(i,j)$$$ as the top-left corner. We use binary search to find the first row where two candidates differ, then the first character in that row, and keep the smaller one.
Problem 9
- This problem seems pretty hard at first, but the key is $$$X\le 30$$$, so there might be a solution with around $$$NX$$$ states or something like that.
- Second, we see that the split sausage is a subsequence, not necessarily one continuous substring.
- This means that once we consider a substring as a part of the split sausage, we don't really care about the earlier positions anymore. We only need to know how much of the target prefix they have covered.
- So we can use DP to track the maximum position we have covered after using $$$j$$$ pieces: $$$dp[i][j]$$$.
- For every position $$$i$$$, let $$$p=dp[i][j]$$$. We just need to find the first position where the suffixes $$$t[p\ldots m-1]$$$ and $$$s[i\ldots n-1]$$$ differ, using hashing and binary search.
- If they match for $$$L$$$ characters, update $$$dp[i+L][j+1]$$$ with $$$p+L$$$. We can also skip the current position.
Problem 10
- This problem seems impossible at first, but the trick is pretty clever.
- When we consider each sequence $$$i$$$, we can calculate the total cost, but that doesn't really prove anything. A distance of $$$k-1$$$ and another distance of $$$k+1$$$ still add up to $$$2k$$$.
- So is there a way that the total cost can tell us whether it's valid?
- This brings us to the ingenious solution of assigning each sequence a random number.
- Let the random number for sequence $$$j$$$ be $$$w_j$$$, and let $$$W=\sum_j w_j$$$. If $$$d(i,j)$$$ is the distance between sequences $$$i$$$ and $$$j$$$, we check whether $$$\sum_j w_jd(i,j)=k(W-w_i)$$$.
- If all the distances are $$$k$$$, this always works. If they aren't, the random numbers make it unlikely that the differences cancel out.
Extension: XOR Equality
Theory
- If we assign each unique value a random hash, we can take the XOR of all the unique values' hashes in a vector.
- Then we can compare $$$\mathrm{set}(x)=\mathrm{set}(y)$$$ in $$$O(1)$$$ using their maintained hashes, with a small collision probability.
- The important part is taking each unique value once, because repeated copies can cancel out under XOR.
Problem 11
- To count how many subarrays $$$[l,r]$$$ are valid, we can convert the problem into comparing the prefix states at $$$r$$$ and $$$l-1$$$.
- For this problem, we need to track each value's count modulo $$$3$$$. So we extend the hashing idea to a base-$$$3$$$ state instead of using ordinary XOR.
- If $$$H_r=H_{l-1}$$$, then every value's frequency in the subarray is divisible by $$$3$$$, assuming no hash collision.
- But what if a value appears a multiple of $$$3$$$ times, like $$$6$$$ or $$$9$$$, instead of exactly $$$3$$$?
- For each new occurrence, we can store the minimum position that $$$l-1$$$ is allowed to have. This ensures that no value appears more than $$$3$$$ times.
- So with both conditions together, each value appears either $$$0$$$ or exactly $$$3$$$ times.
Thank you for reading!
