Problems Notes on Codeforces String Problems

My goal is to solve all the problems related to strings/hashing/suffix structure starting from rating 2600 in Codeforces. I will keep summarizing problem ideas here.

If a problems falls into a specific large category, I will summarize it in those independent blogs:
Palindrome Tree
Suffix Automaton

Shortest/Longest Path Cut Vertex Checking1214D650D, MCPC19B
Sometimes, if we want to check if a vertex is neccesary for a shortest path/longest path, one way to do is hashing as mentioned in the hashing blog. Another much easier way is to group the vertices by distance. The vertex is the cut vertex if and only if it is the only one in that “distance level”.

Non-Palindrome Cutting: Timus 2057
Consider that the only “impossible” cases are like $aaaaa$, $aaaabaaaa$, or $abababa$ (not really sure how to prove, though).
Otherwise the minimum answer is either $1$ or $2$. Check it brute-forcely.
For the maximum answer, we have $dp[i] = max\{dp[j] + 1\}$ for all $j$ s.t. $s[j + 1, i]$ is possible to split. Then we do the dp transition by excluding the three impossible cases.

1. URAL Palindromic Contest (in Chinese)

Leave a Reply

Your email address will not be published. Required fields are marked *