This blog is for compiling mycompiles what I have learninged and way ofmy insights into solving a problem, soms. Some people might benefit from thisit, so enjoy!↵
CREDIT TO USACO.GUIDE THE PROBLEM ARE FROM THERE THANK YOU SO MUCH.↵
**Credit to [USACO Guide](https://usaco.guide/) for the problem list. Thank you so much!**↵
↵
## Theory:↵
↵
+ Hashing is a way to- String hashing converts a string/number into a number using base converting ex: 10 into base2 = 110 ↵
+ so you convert string by converting each character a,b,c...z into 0,1,2,3...,26 into a base↵
+ but the base must be modded to ensure the number dont explode but this create a collision probability -> two numberby treating its characters like digits in a chosen base. For example, $$$10_{10} = 1010_2$$$.↵
- We can map $$$a,b,c,\ldots,z$$$ to $$$1,2,3,\ldots,26$$$ and build a number using a base $$$B$$$.↵
- We take the result modulo $$$M$$$ to keep the number small. However, this creates the possibility of a collision: two different strings canbhave the same (mod MOD)hash modulo $$$M$$$.↵
↵
## 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;↵
}↵
};↵
↵
Problemlist:↵
↵
Problem 1: https://cses.fi/problemset/task/1733 ↵
+ THis problem is template hashing -> complexity is N/1 + N/2 + N/3,.... (N ln N estimated).↵
+ for every compare each segment, [j, j + i — 1] does it equal to the segment [0, i — 1] and compare the suffix if it is equal to the part of the prefix↵
+ code : https://ideone.com/fU6YsJ↵
↵
Problem 2: https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en↵
+ This problem is great because you can delete just one phrase because deleting a phrase might create a new censored phrase↵
+ So we can find a intution like this if I delet phrase [i,j] 2 segments [k, i] and [j, u] might create a censored word [k,j] so we can do such,↵
+ change the template from taking a string in its intialization into getting a empty string and allow adding character one by one, because if delete segment [i,j] the segment that create a new censored word MUST be around the current word↵
+ so we can add character one by one until the ending = censored, delete the prefix, and repeat the process.↵
↵
+code : https://ideone.com/T7V8u2↵
↵
Problem 3: https://codeforces.me/problemset/problem/1056/E↵
↵
+ This problem is template hashing + optimization trick↵
+ consider 0, 1 we can brute force the max(cnt[0], cnt[1]) because the maximum of (cnt[0],cnt[1]) must >= floor(|s| / 2) (|s| is the length of s) so therefor the amount of time we need to run is around 20 * |s| which is around <= t↵
code: https://ideone.com/25VYxJ↵
↵
Problem 4: https://codeforces.me/gym/104048/problem/K↵
+ somepeople use hash the string and consider all permutation but I do bitmask dp(simpler ngl)↵
+ so the way to do this problem is to consider all pair (i,j) where i is put behind j, we consider how much of suffix of i go into j, if i is a substring of j then we shouldnt consider I at all.↵
+ so then dp bitmask, dp[mask][i] where it represent after putting mask string into a string and ending at position i (we only need to consider last position because we had stop the situation where i go into j.↵
code: https://ideone.com/7qCNAV↵
↵
Problem 5: https://usaco.org/index.php?page=viewproblem2&cpid=741↵
+ Problem uses Binary Search the length and use an O(NM) check so total complexity (NM log M)↵
+ The problem uses template Hashing so no need. ↵
+ code : https://ideone.com/GP0HH5↵
↵
Problem 6: https://usaco.org/index.php?page=viewproblem2&cpid=599↵
+This problem is stimulation at each position and we hash the angles : (180,0 : 1; 90 : 2; 270 : 3) + the distances and then take the minimum, though to handle the angles I used vectors (There probably be a better code)↵
+ https://ideone.com/sVvRkd↵
↵
Problem 7: 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, trying to do all string (i,j) and find cost, the complexity would be N^2K which would tle if N is big, so what if we can garunteed if N is not big?↵
+ that brings us to the insight of like sqrt decomposition if N is big, we use NK^2, else N^2K↵
+ which means that maximum amount of operations is somtimes around 3e4 * sqrt(3e4) which is like <= 6e6 plenty of 350ms↵
+ if N is small, we bruteforce as above↵
+ if K is small, we consider all position (i,j) where i and j is the position they differ, we delete the position i,j by merging the hash [0,i] + [i +1, j -1] + [j + 1, |s| — 1] and for every n we check if for every position (i,j) no other position match.↵
+ code : https://ideone.com/SubDgs↵
↵
Problem 8: https://oj.uz/problem/view/COCI20_satellti↵
+ This problem is misleading at first, the problem states CYCLIC SHIFT OF ROWS AND COLUMNS which mean SHIFT ALL ROWS by x then SHIFT ALL COLUMN by y, you choose (x,y)↵
+ which mean we can convert the problem by if we create a copy of the block and put it to the right of the orginial position we can generate all block after we shift all rows. Then we could do that again to generate all block after shifting all column↵
+ so the problem is converted to finding the lexicographically lowest submatrix n * m in the big matrix.↵
+ so we use hash 2d, hashing each row and then use the add hash thing, in the usaco problem to create a prefix column of the hash↵
+ then we consider each position (i,j) where (i,j) is the topleft and find the first position where they differ by binary search. and then find max.↵
+ code : https://ideone.com/5CvjA2↵
↵
Problem 9: https://codeforces.me/contest/822/problem/E↵
+ This problem seems at first pretty hard but the key is X <= 30, so there might be a sol NX or something like that. ↵
+ second we saw that the problem said that the split sausage is a subsequence not a substring which mean that once we consider a substring as a part in the split sausage we dont really care about the lower position, we only need to know if the lower position has covered part [0,i-1]↵
+ so we can use dp to track the maximum position we had covered after use j split, dp[i][j]. for every position i, if we just need to find the first position where prefix [dp[i][j], m] and [i,n] change and update dp.↵
+ code: https://ideone.com/CaNVc6↵
↵
Problem 10: https://open.kattis.com/problems/genetics2↵
+ This problem seems impossible at first but the trick is pretty clever:↵
+ when we consider each position i, we can caculate the total cost, but that doesnt really prove anything because cost j is k — 1 and cost j + 1 is k + 1 still averages to 2k so is there a way that the total cost prove its valid?↵
+ this create the ingenius solution of assigning each position a random number and then if the total cost equal (total cost — cost i) * k — 1 then position is the target.↵
+ code: https://ideone.com/mLmDvp↵
↵
EXTENSION XOR EQUALITY:↵
theory:↵
+ if we assign each unique value a hash, we can consider the xor of all unique number in a vector and we can compare set x = set y in O(1)↵
↵
Problem 11: https://codeforces.me/contest/1418/problem/G↵
+ to count amount of subarray l — r is a valid array, we can conver it to arr[r] — arr[l-1] is a valid array.↵
+ to verify arr[r] — arr[l-1] is good, then xor_hash[r] — xor_hash[l-1] = 0, so we convert each xor into base 3↵
+ but what if instead of 3, the value of a number is a mutiple of 3? for each position that appear we can just store the minimum positon that l-1 could be which ensure that the count of a value isnt a mutiple of 3↵
+code : https://ideone.com/9ROJmR- prefix[l] * pow[r - l] % Mod) % Mod + Mod) % Mod;↵
}↵
return x;↵
}↵
};↵
```↵
↵
## Problem List↵
↵
### Problem 1↵
↵
[Problem](https://cses.fi/problemset/task/1733)↵
↵
- This problem uses 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.
**Credit to [USACO Guide](https://usaco.guide/) for the problem list. Thank you so much!**↵
↵
## Theory
↵
+ so you convert string by converting each character a,b,c...z into 0,1,2,3...,26 into a base↵
+ but the base must be modded to ensure the number dont explode but this create a collision probability -> two number
- We can map $$$a,b,c,\ldots,z$$$ to $$$1,2,3,\ldots,26$$$ and build a number using a base $$$B$$$.↵
- We take the result modulo $$$M$$$ to keep the number small. However, this creates the possibility of a collision: two different strings can
↵
## 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]
sum = prefix[i];↵
}↵
}↵
ll get_hash(ll l, ll r){↵
ll x = prefix[r];↵
if (l >= 1){↵
l--;↵
x = ((x
}↵
return x;↵
}↵
};↵
↵
Problemlist:↵
↵
Problem 1: https://cses.fi/problemset/task/1733 ↵
+ THis problem is template hashing -> complexity is N/1 + N/2 + N/3,.... (N ln N estimated).↵
+ for every compare each segment, [j, j + i — 1] does it equal to the segment [0, i — 1] and compare the suffix if it is equal to the part of the prefix↵
+ code : https://ideone.com/fU6YsJ↵
↵
Problem 2: https://usaco.org/index.php?page=viewproblem2&cpid=529&lang=en↵
+ This problem is great because you can delete just one phrase because deleting a phrase might create a new censored phrase↵
+ So we can find a intution like this if I delet phrase [i,j] 2 segments [k, i] and [j, u] might create a censored word [k,j] so we can do such,↵
+ change the template from taking a string in its intialization into getting a empty string and allow adding character one by one, because if delete segment [i,j] the segment that create a new censored word MUST be around the current word↵
+ so we can add character one by one until the ending = censored, delete the prefix, and repeat the process.↵
↵
+code : https://ideone.com/T7V8u2↵
↵
Problem 3: https://codeforces.me/problemset/problem/1056/E↵
↵
+ This problem is template hashing + optimization trick↵
+ consider 0, 1 we can brute force the max(cnt[0], cnt[1]) because the maximum of (cnt[0],cnt[1]) must >= floor(|s| / 2) (|s| is the length of s) so therefor the amount of time we need to run is around 20 * |s| which is around <= t↵
code: https://ideone.com/25VYxJ↵
↵
Problem 4: https://codeforces.me/gym/104048/problem/K↵
+ somepeople use hash the string and consider all permutation but I do bitmask dp(simpler ngl)↵
+ so the way to do this problem is to consider all pair (i,j) where i is put behind j, we consider how much of suffix of i go into j, if i is a substring of j then we shouldnt consider I at all.↵
+ so then dp bitmask, dp[mask][i] where it represent after putting mask string into a string and ending at position i (we only need to consider last position because we had stop the situation where i go into j.↵
code: https://ideone.com/7qCNAV↵
↵
Problem 5: https://usaco.org/index.php?page=viewproblem2&cpid=741↵
+ Problem uses Binary Search the length and use an O(NM) check so total complexity (NM log M)↵
+ The problem uses template Hashing so no need. ↵
+ code : https://ideone.com/GP0HH5↵
↵
Problem 6: https://usaco.org/index.php?page=viewproblem2&cpid=599↵
+This problem is stimulation at each position and we hash the angles : (180,0 : 1; 90 : 2; 270 : 3) + the distances and then take the minimum, though to handle the angles I used vectors (There probably be a better code)↵
+ https://ideone.com/sVvRkd↵
↵
Problem 7: 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, trying to do all string (i,j) and find cost, the complexity would be N^2K which would tle if N is big, so what if we can garunteed if N is not big?↵
+ that brings us to the insight of like sqrt decomposition if N is big, we use NK^2, else N^2K↵
+ which means that maximum amount of operations is somtimes around 3e4 * sqrt(3e4) which is like <= 6e6 plenty of 350ms↵
+ if N is small, we bruteforce as above↵
+ if K is small, we consider all position (i,j) where i and j is the position they differ, we delete the position i,j by merging the hash [0,i] + [i +1, j -1] + [j + 1, |s| — 1] and for every n we check if for every position (i,j) no other position match.↵
+ code : https://ideone.com/SubDgs↵
↵
Problem 8: https://oj.uz/problem/view/COCI20_satellti↵
+ This problem is misleading at first, the problem states CYCLIC SHIFT OF ROWS AND COLUMNS which mean SHIFT ALL ROWS by x then SHIFT ALL COLUMN by y, you choose (x,y)↵
+ which mean we can convert the problem by if we create a copy of the block and put it to the right of the orginial position we can generate all block after we shift all rows. Then we could do that again to generate all block after shifting all column↵
+ so the problem is converted to finding the lexicographically lowest submatrix n * m in the big matrix.↵
+ so we use hash 2d, hashing each row and then use the add hash thing, in the usaco problem to create a prefix column of the hash↵
+ then we consider each position (i,j) where (i,j) is the topleft and find the first position where they differ by binary search. and then find max.↵
+ code : https://ideone.com/5CvjA2↵
↵
Problem 9: https://codeforces.me/contest/822/problem/E↵
+ This problem seems at first pretty hard but the key is X <= 30, so there might be a sol NX or something like that. ↵
+ second we saw that the problem said that the split sausage is a subsequence not a substring which mean that once we consider a substring as a part in the split sausage we dont really care about the lower position, we only need to know if the lower position has covered part [0,i-1]↵
+ so we can use dp to track the maximum position we had covered after use j split, dp[i][j]. for every position i, if we just need to find the first position where prefix [dp[i][j], m] and [i,n] change and update dp.↵
+ code: https://ideone.com/CaNVc6↵
↵
Problem 10: https://open.kattis.com/problems/genetics2↵
+ This problem seems impossible at first but the trick is pretty clever:↵
+ when we consider each position i, we can caculate the total cost, but that doesnt really prove anything because cost j is k — 1 and cost j + 1 is k + 1 still averages to 2k so is there a way that the total cost prove its valid?↵
+ this create the ingenius solution of assigning each position a random number and then if the total cost equal (total cost — cost i) * k — 1 then position is the target.↵
+ code: https://ideone.com/mLmDvp↵
↵
EXTENSION XOR EQUALITY:↵
theory:↵
+ if we assign each unique value a hash, we can consider the xor of all unique number in a vector and we can compare set x = set y in O(1)↵
↵
Problem 11: https://codeforces.me/contest/1418/problem/G↵
+ to count amount of subarray l — r is a valid array, we can conver it to arr[r] — arr[l-1] is a valid array.↵
+ to verify arr[r] — arr[l-1] is good, then xor_hash[r] — xor_hash[l-1] = 0, so we convert each xor into base 3↵
+ but what if instead of 3, the value of a number is a mutiple of 3? for each position that appear we can just store the minimum positon that l-1 could be which ensure that the count of a value isnt a mutiple of 3↵
+code : https://ideone.com/9ROJmR
}↵
return x;↵
}↵
};↵
```↵
↵
## Problem List↵
↵
### Problem 1↵
↵
[Problem](https://cses.fi/problemset/task/1733)↵
↵
- This problem uses 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.
