This blog is for compiling my learning and way of insight into solving a problem, some might benefit from this so enjoy CREDIT TO USACO.GUIDE THE PROBLEM ARE FROM THERE THANK YOU SO MUCH.

Theory:

• Hashing is a way to convert string/number to 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 number can be the same (mod MOD)

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

struct hashed_string{ private: string s; ll n; vector prefix; vector 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〈=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