Olá Codeforces!
Tomorrow, on August 17, we'll be holding Universidade de São Paulo Try-outs, a competition that aims to select the teams that will represent our university in the Brazilian regionals. We will also run an online mirror contest in Codeforces Gym starting at 14:30 (UTC -3, São Paulo time)!
The link for the mirror in Codeforces: https://codeforces.me/gym/106039
Contestants should follow ICPC rules. We have prepared challenging and interesting problems suitable for both beginners and veterans. You can check previous contests to get an estimate of the difficulty level.
A huge thanks to all setters and testers for their time and valuable feedback.
We look forward your participation!
I was really quite interested in problem C (despite not solving it). Will there be an editorial released for this contest?
Wait same, I also liked problem C but couldn't get it (probably some SA+LCP w/Mo's or ds idek). Seemed interesting though. I would also really like to see and editorial for this contest!
You can solve it with persistent double-ended eertree (6.1.2) in $$$O(n \sqrt q (log(n) + log(\sigma))$$$ but its really painful to implement and I hope there is another way to solve this problem.
Basically, the number of nodes in eertree (minus $$$1$$$) is equal to the number of distinct palindromic substrings, but in our queries, we have some set of strings. We need to find a way to concatenate strings that are in the set into some single string without creating new palindromic substrings. The simplest way is to take some string $$$t$$$ with length $$$2$$$ that contains $$$2$$$ different symbols that are NOT in $$$\sigma$$$ (for example: "!#", "*&", etc.) and create string $$$u = s_{1} + t + s_{2} + t + \dots + s_{n-1} + t + s_{k} + t$$$ ($$$k$$$ is equal to the size of the set of some query and $$$s_{i}$$$ is the i-th string in this set) (for example: if the set is {"abc", "aa", "a"}, $$$t$$$ = "!#", then $$$u$$$ = abc!#aa!#a). And we can see that we counted every palindromic substring of every string in the set (because they are in our string $$$u$$$) and we also counted $$$2$$$ extra palindromic substrings that are the first and second characters of the string $$$t$$$ (because they are of length $$$1$$$). We can prove that there won't be more extra substrings because of $$$t$$$.
And if we make string $$$p = s_{1} + t + s_{2} + t + \dots + s_{n-1} + t + s_{n} + t$$$ we have transformed our problem into counting the number of distinct palindromic substrings in some range $$$p_{l..r}$$$ (and we need to subtract $$$2$$$ from our answer because of string $$$t$$$).
Frankly, I am a bit baffled that you really believe this is a solution because you still fail to get past testcase 7. Although it may work in hindsight, upon the brutal implementation, I'm sure that it does not work. The problem writer must have come up with a more elegant solution!
You are right, after the reduction you can solve the last part with $$$O(n \log n)$$$ preprocessing and $$$O(\log n)$$$ per query with persistent segment trees.
Lets solve our queries offline and sort them by $$$r$$$ coordinate. Lets create array $$$a$$$ of length $$$n$$$ such as $$$a[k]$$$ = $$$ans(s_{k..r})$$$ — $$$ans(s_{k+1..r})$$$. Then the answer to our query $$$[l..r]$$$ would be $$$\displaystyle \sum_{i = l}^r a[i]$$$. Easy to see that $$$0 \leq a[x] \leq 1$$$.
We need to find a way to transition from $$$r-1$$$ to $$$r$$$. $$$a[k]$$$ right now is equal to $$$ans(s_{k..r-1}) - ans(s_{k+1..r-1})$$$. So we just need to consider the longest palindrome with symbol at position $$$r$$$ (lets say this palindrome is $$$\displaystyle s_{x..r}$$$ with length equal to $$$len$$$). Lets say that this palindrome is unique, then we are adding $$$1$$$ to $$$a[x]$$$ (because all strings that start at position $$$j \leq x$$$ will contain it, and all strings that start at position $$$j \gt x$$$ will not have it.) What if there is some occurrence of our $$$\displaystyle s_{x..r}$$$? Lets consider the maximum pos $$$y \neq x$$$ such as $$$\displaystyle s_{y..y + len - 1} = s_{x..r}$$$. We need to subtract $$$1$$$ from $$$y$$$ and still add $$$1$$$ to $$$x$$$. (because only the last occurrence of unique palindrome changes our array $$$a$$$). And we can maintain the position of last occurrence of palindrome with eertree.
How to make this algorithm work online? Use persistent segtree for every $$$r$$$.
334280775 or code on ideone
We aim to release an editorial later this week.
has it been published?
You can solve it with eertree + merge sort tree in O(nlogn + qlog²n).
Let's transform each string $$$s_i$$$ into a vector $$$v_i$$$ such that $$$v_{i,j}$$$ is the id of the eertree vertex that corresponds to the longest palindromic suffix of the string $$$s_i[0..j]$$$. This is easy with the eertree because that is exactly what it computes after inserting the jth character of a string.
For example, for this set of strings, it could look something like this:
abc = {0, 1, 2}
aaa = {0, 3, 4}
abacaa = {0, 1, 5, 2, 6, 3}
Notice how the vertex id's are actually shared between all strings, that is, I want the palindromic string "aa" to have the same id on both strings "aaa" and "abacaa".
On the example above, this is the id of each palindromic substring:
"a" -> 0
"b" -> 1
"c" -> 2
"aa" -> 3
"aaa" -> 4
"aba" -> 5
"aca" -> 6
To get that "shared id" behaviour, we can simply work with a single eertree and we add all the strings to it. To make sure the words don't cross with each other, we can append something like "#%" after each word we add.
Claim: every unique palindromic substring id of string $$$s_i$$$ will appear on its vector $$$v_i$$$.
I actually won't give any formal proof, but just an idea of why that is correct. Whenever a palindromic substring appears for the first time within a string, it is obviously a suffix of the characters added so far. I claim that, if it is new, then, its not only a suffix, but actually the longest palindromic suffix of the string.
Suppose that it isn't. Let 'c' be the last appended character. We are essentially saying that the current string is made of
cyczc
where 'y' and 'z' are (possibly empty) palindromic strings. The string "czc" is what we claim is the new palindromic substring found, and "cyczc" is what we are assuming is the longest palindromic suffix. We also assume "ycz" is palindromic, otherwise "cyczc" wouldn't be a palindrome.
Let's denote by z* the reverse of the string z. Because "cyczc" is a palindrome, it equals its reverse. Therefore:
cyczc = (cyczc)*
= (c*)(z*)(c*)(y*)(c*)
= c(z*)c(y*)c
= czc(y*)c
We used the facts that c == (c*) (because c is a single character) and z == (z*) (because z is palindromic).
As you can see, czc already appeared before, and, therefore, is not a NEW palindromic string (absurd).
Merge all of those vectors into a single vector called 'a'.
Given that every palindromic substring id of $$$s_i$$$ appears on $$$v_i$$$ (although possibly repeated times), now, all we gotta do is query the amount of unique numbers on the range [l, r] of 'a'. That can be done with merge sort tree as follows:
Build a vector "prev" such that prev[i] is the largest index j<i such that a[i] == a[j]. Essentially, "prev" just tells the position of the next equal element immediately to the left. If it doesn't exist, set prev[i] to -INF. Counting distinct elements on the range [l, r] is equivalent to counting how many elements have their prev[i] smaller than 'l' (because this means this is the first time it appears on this range). That is a classic usage of merge sort tree, and can be done in log²(n).