This blog compiles what I haveis for compiling my learneding and my insights intoway of thinking when solving a problems. Some people might benefit from itthis, so enjoy!↵
↵
**Credit toREDIT TO [USACO Guide.GUIDE](https://usaco.guide/) for the problem list. Thank you so much. THE PROBLEMS ARE FROM THERE. THANK YOU SO MUCH!**↵
↵
## Theory↵
↵
-String hashingHashing is a way to converts a string/number into a number by treating its characters like digits in a chosen baseusing the idea of base conversion. For example, $$$10_{10} = =1010_2$$$.↵
-We can map $$So we convert a string by mapping each character $a,b,c,\ldots,z$$$ to $$$1,2,3,\ldots,26$$$ and build a number ustreating them as digits ing a base $$$B$$$.↵
- Wchosen base.↵
- But we take the result modulo $$$M$$$ to keep the number small. However, this creates the possibility of a collision\mathrm{Mod}$ to make sure the number doesn't explode. This creates a collision probability: two different strings can have the same hash modulo $$$M$$\mathrm{Mod}$.↵
↵
## Template↵
↵
```cpp++↵
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](https://cses.fi/problemset/task/1733)↵
↵
- This problemuses template hashing. The number of comparisons is approximately $$$\frac{N}{1}+\frac{N}{2}+\frac{N}{3}+\cdots+\frac{N}{N}=O(N\log N)$$$.↵
- For each candidate period length $$$i$$$, compare every complete segment $$$[j,j+i-1]$$$ with $$$[0,i-1]$$$.↵
- If the final segment is shorter than $$$i$$$, compare it with the prefix of the same length.↵
↵
[Code](https://ideone.com/fU6YsJ)↵
↵
### Problem 2↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en)↵
↵
- This problem is interesting because deleting a phrase might create a new censored phrase.↵
- If we delete a segment $$$[i,j]$$$, the remaining parts $$$[0,i-1]$$$ and $$$[j+1,n-1]$$$ 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](https://ideone.com/T7V8u2)↵
↵
### Problem 3↵
↵
[Problem](https://codeforces.me/problemset/problem/1056/E)↵
↵
- This problem combines template hashing with an optimization trick.↵
- Let $$$c_0$$$ and $$$c_1$$$ be the counts of $$$0$$$ and $$$1$$$ in $$$s$$$. If the replacement lengths are $$$L_0$$$ and $$$L_1$$$, then $$$c_0L_0+c_1L_1=|t|$$$.↵
- Enumerate the replacement length for the more frequent symbol. Since $$$\max(c_0,c_1)\ge\left\lceil\frac{|s|}{2}\right\rceil$$$, there are at most $$$O\left(\frac{|t|}{|s|}\right)$$$ candidate lengths.↵
- For each candidate, calculate the other length and check the pattern using hashing in $$$O(|s|)$$$. This gives $$$O(|t|)$$$ time after hash preprocessing.↵
- Both replacement strings must be nonempty, and they must be different.↵
↵
[Code](https://ideone.com/25VYxJ)↵
↵
### Problem 4↵
↵
[Problem](https://codeforces.me/gym/104048/problem/K)↵
↵
- 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 $$$(i,j)$$$, calculate the maximum overlap between a suffix of string $$$i$$$ and a prefix of string $$$j$$$.↵
- Then use bitmask DP. Let $$$dp[\mathrm{mask}][i]$$$ represent the minimum length after combining the strings in $$$\mathrm{mask}$$$ and ending with string $$$i$$$.↵
- We only need to remember the last string because we have already removed strings contained in other strings.↵
↵
[Code](https://ideone.com/7qCNAV)↵
↵
### Problem 5↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=741)↵
↵
- Binary search the substring length and use an $$$O(NM)$$$ check, giving a total complexity of $$$O(NM\log M)$$$.↵
- The check uses template hashing to compare the substrings.↵
↵
[Code](https://ideone.com/GP0HH5)↵
↵
### Problem 6↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=599)↵
↵
- 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 $$$0^\circ$$$, $$$90^\circ$$$, and $$$270^\circ$$$ as three different values.↵
- I used vectors to handle the turns. There is probably a cleaner implementation.↵
↵
[Code](https://ideone.com/sVvRkd)↵
↵
### Problem 7↵
↵
[Problem](https://csacademy.com/contest/rmi-2017-day-1/task/hangman2/)↵
↵
- This problem is really interesting, and the key observation is hard to find.↵
- If we brute force every pair of strings $$$(i,j)$$$ and calculate their Hamming distance, the complexity is $$$O(N^2K)$$$. This is too slow when $$$N$$$ is large.↵
- What if we choose the approach based on which dimension is smaller? If $$$N$$$ is small, use $$$O(N^2K)$$$; if $$$K$$$ is small, use $$$O(NK^2)$$$.↵
- This gives $$$O(NK\min(N,K))$$$. Since $$$\min(N,K)\le\sqrt{NK}$$$, if $$$NK\le 3\cdot10^4$$$, the work is roughly bounded by $$$3\cdot10^4\sqrt{3\cdot10^4}<6\cdot10^6$$$.↵
- If $$$N$$$ is small, brute force as described above.↵
- If $$$K$$$ is small, consider every pair of positions $$$i<j$$$. Delete these two positions from each string by concatenating the hashes of $$$[0,i-1]$$$, $$$[i+1,j-1]$$$, and $$$[j+1,K-1]$$$, 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 $$$2$$$.↵
↵
[Code](https://ideone.com/SubDgs)↵
↵
### Problem 8↵
↵
[Problem](https://oj.uz/problem/view/COCI20_satellti)↵
↵
- This problem is misleading at first. The operation shifts all rows by the same amount $$$x$$$ and all columns by the same amount $$$y$$$. We choose one pair $$$(x,y)$$$.↵
- 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 $$$n\times m$$$ 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 $$$(i,j)$$$. 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](https://ideone.com/5CvjA2)↵
↵
### Problem 9↵
↵
[Problem](https://codeforces.me/contest/822/problem/E)↵
↵
- This problem seems hard at first, but the key is $$$X\le 30$$$, which suggests a DP with about $$$NX$$$ 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 $$$dp[i][j]$$$ be the maximum target-prefix length we can form using at most $$$j$$$ pieces from the first $$$i$$$ characters of the original string.↵
- We can skip the current character. Alternatively, if $$$p=dp[i][j]$$$, find the longest common prefix of the suffixes starting at $$$s[i]$$$ and $$$t[p]$$$ using hashing and binary search.↵
- If that common-prefix length is $$$L$$$, update $$$dp[i+L][j+1]$$$ with $$$p+L$$$.↵
↵
[Code](https://ideone.com/CaNVc6)↵
↵
### Problem 10↵
↵
[Problem](https://open.kattis.com/problems/genetics2)↵
↵
- This problem seems impossible at first, but the trick is clever.↵
- For each sequence $$$i$$$, we can calculate its total Hamming distance to all other sequences. However, this does not prove that every distance equals $$$k$$$: distances $$$k-1$$$ and $$$k+1$$$ still add up to $$$2k$$$.↵
- The idea is to assign each sequence $$$j$$$ a random weight $$$w_j$$$.↵
- Let $$$d(i,j)$$$ be the Hamming distance and $$$W=\sum_j w_j$$$. Check whether $$$\sum_j w_jd(i,j)=k(W-w_i)$$$.↵
- If every distance from $$$i$$$ to another sequence is $$$k$$$, 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](https://ideone.com/mLmDvp)↵
↵
## Extension: XOR Equality↵
↵
### Theory↵
↵
- Assign each distinct value $$$v$$$ a random hash $$$h(v)$$$.↵
- For a set $$$S$$$, define $$$H(S)=\bigoplus_{v\in S}h(v)$$$.↵
- Once these hashes are maintained, comparing $$$H(A)$$$ and $$$H(B)$$$ takes $$$O(1)$$$ 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](https://codeforces.me/contest/1418/problem/G)↵
↵
- To count valid subarrays $$$[l,r]$$$, use prefix states so that the state of a subarray is determined by the states at $$$r$$$ and $$$l-1$$$.↵
- Here, we need frequencies modulo $$$3$$$. Ordinary XOR tracks parity, so instead hash the vector of frequencies modulo $$$3$$$.↵
- A subarray passes this check when $$$H_r=H_{l-1}$$$, meaning that every frequency is divisible by $$$3$$$, subject to hash collisions.↵
- But a frequency could be $$$6,9,\ldots$$$, while we need every appearing value to occur exactly $$$3$$$ times.↵
- Maintain the minimum allowed prefix index $$$l-1$$$ so that no value appears more than $$$3$$$ times in the subarray. Combined with the modulo-$$$3$$$ condition, this leaves only frequencies $$$0$$$ and $$$3$$$.↵
↵
[Code](https://ideone.com/9ROJmR) Thank for reading.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.↵
↵
[Code](https://ideone.com/fU6YsJ)↵
↵
### Problem 2↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en)↵
↵
- 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.↵
↵
[Code](https://ideone.com/T7V8u2)↵
↵
### Problem 3↵
↵
[Problem](https://codeforces.me/problemset/problem/1056/E)↵
↵
- 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.↵
↵
[Code](https://ideone.com/25VYxJ)↵
↵
### Problem 4↵
↵
[Problem](https://codeforces.me/gym/104048/problem/K)↵
↵
- 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.↵
↵
[Code](https://ideone.com/7qCNAV)↵
↵
### Problem 5↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=741)↵
↵
- 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.↵
↵
[Code](https://ideone.com/GP0HH5)↵
↵
### Problem 6↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=599)↵
↵
- 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).↵
↵
[Code](https://ideone.com/sVvRkd)↵
↵
### Problem 7↵
↵
[Problem](https://csacademy.com/contest/rmi-2017-day-1/task/hangman2/)↵
↵
- 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}<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<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.↵
↵
[Code](https://ideone.com/SubDgs)↵
↵
### Problem 8↵
↵
[Problem](https://oj.uz/problem/view/COCI20_satellti)↵
↵
- 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.↵
↵
[Code](https://ideone.com/5CvjA2)↵
↵
### Problem 9↵
↵
[Problem](https://codeforces.me/contest/822/problem/E)↵
↵
- 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.↵
↵
[Code](https://ideone.com/CaNVc6)↵
↵
### Problem 10↵
↵
[Problem](https://open.kattis.com/problems/genetics2)↵
↵
- 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.↵
↵
[Code](https://ideone.com/mLmDvp)↵
↵
## 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↵
↵
[Problem](https://codeforces.me/contest/1418/problem/G)↵
↵
- 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.↵
↵
[Code](https://ideone.com/9ROJmR)↵
↵
**Thank you for reading!**
↵
**C
↵
## Theory↵
↵
-
-
- W
- But we take the result modulo $
↵
## Template↵
↵
```c
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](https://cses.fi/problemset/task/1733)↵
↵
- This problem
- For each candidate period length $$$i$$$, compare every complete segment $$$[j,j+i-1]$$$ with $$$[0,i-1]$$$.↵
- If the final segment is shorter than $$$i$$$, compare it with the prefix of the same length.↵
↵
[Code](https://ideone.com/fU6YsJ)↵
↵
### Problem 2↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en)↵
↵
- This problem is interesting because deleting a phrase might create a new censored phrase.↵
- If we delete a segment $$$[i,j]$$$, the remaining parts $$$[0,i-1]$$$ and $$$[j+1,n-1]$$$ 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](https://ideone.com/T7V8u2)↵
↵
### Problem 3↵
↵
[Problem](https://codeforces.me/problemset/problem/1056/E)↵
↵
- This problem combines template hashing with an optimization trick.↵
- Let $$$c_0$$$ and $$$c_1$$$ be the counts of $$$0$$$ and $$$1$$$ in $$$s$$$. If the replacement lengths are $$$L_0$$$ and $$$L_1$$$, then $$$c_0L_0+c_1L_1=|t|$$$.↵
- Enumerate the replacement length for the more frequent symbol. Since $$$\max(c_0,c_1)\ge\left\lceil\frac{|s|}{2}\right\rceil$$$, there are at most $$$O\left(\frac{|t|}{|s|}\right)$$$ candidate lengths.↵
- For each candidate, calculate the other length and check the pattern using hashing in $$$O(|s|)$$$. This gives $$$O(|t|)$$$ time after hash preprocessing.↵
- Both replacement strings must be nonempty, and they must be different.↵
↵
[Code](https://ideone.com/25VYxJ)↵
↵
### Problem 4↵
↵
[Problem](https://codeforces.me/gym/104048/problem/K)↵
↵
- 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 $$$(i,j)$$$, calculate the maximum overlap between a suffix of string $$$i$$$ and a prefix of string $$$j$$$.↵
- Then use bitmask DP. Let $$$dp[\mathrm{mask}][i]$$$ represent the minimum length after combining the strings in $$$\mathrm{mask}$$$ and ending with string $$$i$$$.↵
- We only need to remember the last string because we have already removed strings contained in other strings.↵
↵
[Code](https://ideone.com/7qCNAV)↵
↵
### Problem 5↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=741)↵
↵
- Binary search the substring length and use an $$$O(NM)$$$ check, giving a total complexity of $$$O(NM\log M)$$$.↵
- The check uses template hashing to compare the substrings.↵
↵
[Code](https://ideone.com/GP0HH5)↵
↵
### Problem 6↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=599)↵
↵
- 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 $$$0^\circ$$$, $$$90^\circ$$$, and $$$270^\circ$$$ as three different values.↵
- I used vectors to handle the turns. There is probably a cleaner implementation.↵
↵
[Code](https://ideone.com/sVvRkd)↵
↵
### Problem 7↵
↵
[Problem](https://csacademy.com/contest/rmi-2017-day-1/task/hangman2/)↵
↵
- This problem is really interesting, and the key observation is hard to find.↵
- If we brute force every pair of strings $$$(i,j)$$$ and calculate their Hamming distance, the complexity is $$$O(N^2K)$$$. This is too slow when $$$N$$$ is large.↵
- What if we choose the approach based on which dimension is smaller? If $$$N$$$ is small, use $$$O(N^2K)$$$; if $$$K$$$ is small, use $$$O(NK^2)$$$.↵
- This gives $$$O(NK\min(N,K))$$$. Since $$$\min(N,K)\le\sqrt{NK}$$$, if $$$NK\le 3\cdot10^4$$$, the work is roughly bounded by $$$3\cdot10^4\sqrt{3\cdot10^4}<6\cdot10^6$$$.↵
- If $$$N$$$ is small, brute force as described above.↵
- If $$$K$$$ is small, consider every pair of positions $$$i<j$$$. Delete these two positions from each string by concatenating the hashes of $$$[0,i-1]$$$, $$$[i+1,j-1]$$$, and $$$[j+1,K-1]$$$, 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 $$$2$$$.↵
↵
[Code](https://ideone.com/SubDgs)↵
↵
### Problem 8↵
↵
[Problem](https://oj.uz/problem/view/COCI20_satellti)↵
↵
- This problem is misleading at first. The operation shifts all rows by the same amount $$$x$$$ and all columns by the same amount $$$y$$$. We choose one pair $$$(x,y)$$$.↵
- 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 $$$n\times m$$$ 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 $$$(i,j)$$$. 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](https://ideone.com/5CvjA2)↵
↵
### Problem 9↵
↵
[Problem](https://codeforces.me/contest/822/problem/E)↵
↵
- This problem seems hard at first, but the key is $$$X\le 30$$$, which suggests a DP with about $$$NX$$$ 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 $$$dp[i][j]$$$ be the maximum target-prefix length we can form using at most $$$j$$$ pieces from the first $$$i$$$ characters of the original string.↵
- We can skip the current character. Alternatively, if $$$p=dp[i][j]$$$, find the longest common prefix of the suffixes starting at $$$s[i]$$$ and $$$t[p]$$$ using hashing and binary search.↵
- If that common-prefix length is $$$L$$$, update $$$dp[i+L][j+1]$$$ with $$$p+L$$$.↵
↵
[Code](https://ideone.com/CaNVc6)↵
↵
### Problem 10↵
↵
[Problem](https://open.kattis.com/problems/genetics2)↵
↵
- This problem seems impossible at first, but the trick is clever.↵
- For each sequence $$$i$$$, we can calculate its total Hamming distance to all other sequences. However, this does not prove that every distance equals $$$k$$$: distances $$$k-1$$$ and $$$k+1$$$ still add up to $$$2k$$$.↵
- The idea is to assign each sequence $$$j$$$ a random weight $$$w_j$$$.↵
- Let $$$d(i,j)$$$ be the Hamming distance and $$$W=\sum_j w_j$$$. Check whether $$$\sum_j w_jd(i,j)=k(W-w_i)$$$.↵
- If every distance from $$$i$$$ to another sequence is $$$k$$$, 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](https://ideone.com/mLmDvp)↵
↵
## Extension: XOR Equality↵
↵
### Theory↵
↵
- Assign each distinct value $$$v$$$ a random hash $$$h(v)$$$.↵
- For a set $$$S$$$, define $$$H(S)=\bigoplus_{v\in S}h(v)$$$.↵
- Once these hashes are maintained, comparing $$$H(A)$$$ and $$$H(B)$$$ takes $$$O(1)$$$ 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](https://codeforces.me/contest/1418/problem/G)↵
↵
- To count valid subarrays $$$[l,r]$$$, use prefix states so that the state of a subarray is determined by the states at $$$r$$$ and $$$l-1$$$.↵
- Here, we need frequencies modulo $$$3$$$. Ordinary XOR tracks parity, so instead hash the vector of frequencies modulo $$$3$$$.↵
- A subarray passes this check when $$$H_r=H_{l-1}$$$, meaning that every frequency is divisible by $$$3$$$, subject to hash collisions.↵
- But a frequency could be $$$6,9,\ldots$$$, while we need every appearing value to occur exactly $$$3$$$ times.↵
- Maintain the minimum allowed prefix index $$$l-1$$$ so that no value appears more than $$$3$$$ times in the subarray. Combined with the modulo-$$$3$$$ condition, this leaves only frequencies $$$0$$$ and $$$3$$$.↵
↵
[Code](https://ideone.com/9ROJmR) Thank for reading.
- 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.↵
↵
[Code](https://ideone.com/fU6YsJ)↵
↵
### Problem 2↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en)↵
↵
- 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.↵
↵
[Code](https://ideone.com/T7V8u2)↵
↵
### Problem 3↵
↵
[Problem](https://codeforces.me/problemset/problem/1056/E)↵
↵
- 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.↵
↵
[Code](https://ideone.com/25VYxJ)↵
↵
### Problem 4↵
↵
[Problem](https://codeforces.me/gym/104048/problem/K)↵
↵
- 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.↵
↵
[Code](https://ideone.com/7qCNAV)↵
↵
### Problem 5↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=741)↵
↵
- 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.↵
↵
[Code](https://ideone.com/GP0HH5)↵
↵
### Problem 6↵
↵
[Problem](https://usaco.org/index.php?page=viewproblem2&cpid=599)↵
↵
- 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).↵
↵
[Code](https://ideone.com/sVvRkd)↵
↵
### Problem 7↵
↵
[Problem](https://csacademy.com/contest/rmi-2017-day-1/task/hangman2/)↵
↵
- 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}<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<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.↵
↵
[Code](https://ideone.com/SubDgs)↵
↵
### Problem 8↵
↵
[Problem](https://oj.uz/problem/view/COCI20_satellti)↵
↵
- 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.↵
↵
[Code](https://ideone.com/5CvjA2)↵
↵
### Problem 9↵
↵
[Problem](https://codeforces.me/contest/822/problem/E)↵
↵
- 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.↵
↵
[Code](https://ideone.com/CaNVc6)↵
↵
### Problem 10↵
↵
[Problem](https://open.kattis.com/problems/genetics2)↵
↵
- 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.↵
↵
[Code](https://ideone.com/mLmDvp)↵
↵
## 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↵
↵
[Problem](https://codeforces.me/contest/1418/problem/G)↵
↵
- 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.↵
↵
[Code](https://ideone.com/9ROJmR)↵
↵
**Thank you for reading!**
