F. Pasti Pas!
Author: Suhendry Effendy
(link to problem F)
First, we have to notice that the greedy decomposition works, i.e. always find a shortest substring which is a prefix and also a suffix of the string S.
For the example given in the problem statement (“ABCADDABCA”), we can start by omitting the first (and the last A), and then proceed by omitting BC, A and lastly D.
The next question is, how to find such substring? As the size of the string is quite large (50,000), naively iterating through the string will give you Time Limit Exceeded.
The expected solution to this problem employs hashing technique to find the matched substring. We can use rolling hash like one used in Rabin-Karp string matching algorithm.
INPUT S input string L = 0, R = 0, P = 1 i = 1, j = S.length() ans = 0 while i <= j L = L * P + S[i] R = R + S[j] * P P = P * x # x is some large prime number if L = R AND i < j ans = ans + 2 L = 0, R = 0, P = 1 i = i + 1 j = j - 1 if P <> 1 ans = ans + 1 return ans
The hash value can be computed in O(1); we only need to “add” the current character to the previous computed hash (it’s the property of rolling hash!). As there are N characters to be considered, thus the overall complexity of this approach is O(N).
At first, using Suffix Array and LCP for this problem seems to be a good idea; however this approach will not solve the problem within the given time limit. Notice that the time limit for this problem is quite strict, i.e. 2 seconds. Suffix Array’s construction has O(N lg N) and also Ω(N lg N) time complexity, which means this approach will always “hit” the N lg N order in any cases (compared to bruteforce + “smart” pruning approach below).
I have tried to implement Suffix Array and run it in judge’s PC; it needs ~6 seconds to pass all tests. With O(N lg2 N) Suffix Array, it needs ~15 seconds. I did not try other sophisticated Suffix Tree algorithm (e.g., Ukkonen’s algorithm) which run in O(N), but I guess it is overkill.
Bruteforce + “smart” pruning
Any bruteforce algorithm which run in O(N2) is expected to get TLE. However, I observed some teams got accepted on this problem using this approach combined with some “smart” pruning (actually it is a simple pruning, but we did not prepare for this). After carefully read the solution, it appears that the solutions were still in O(N2), but there is no case in the test data which trap that pruning solution. Lucky them :-(. A plain O(N2) bruteforce solution still get TLE though, as reported by team koalabiru.
Anyway, this should be a lesson for us (the authors and testers) to prepare the problem better and not let such “cheap” solutions pass in the future.