A note on CF1679E Typical Party in Dorm (CF791DIV2E)

Revision en19, by Aveiro_quanyue, 2023-03-18 10:06:23

Problem link, link: https://codeforces.net/contest/1679/problem/E

Part 1: Notations

$$$s$$$: The original string that might contain '?'.

$$$s[i,j]$$$: The substring including $$$s[i]$$$ and $$$s[j]$$$: $$$(s[i], s[i+1],..., s[j])$$$. If $$$i > j$$$, the $$$s[i, j]$$$ is an empty string.

$$$t$$$: The query string.

We also define some notations that will be clarified in the Part 2:

$$$ok[i,j]$$$: A $$$2D$$$ bool array indicating whether $$$s[i,j]$$$ is valid or not. We will define the word "valid" in Part 2. If $$$s[i,j]$$$ is valid, then $$$ok[i,j]$$$ is true, i.e., $$$1$$$. If $$$s[i,j]$$$ is invalid, then $$$ok[i,j]$$$ is false, i.e., $$$0$$$.

$$$set[i, j]$$$: The required character set to make $$$s[i,j]$$$ a palindrome.

$$$free[i, j]$$$: The number of free places. We will define the terminology "free places" in part 2.

$$$num[i, j]$$$: The number of '?' in the substring $$$s[i, j]$$$. For example, if s[i, j] == "???a", then $$$num[i, j] == 3$$$.

Part 2: ok, set and free

(1)We call a substring $$$s[i,j]$$$ invalid if and only if:

there exists an index $$$x (i \leq x \leq j)$$$ such that s[x] != '?' && s[i+j-x] != '?' && s[x] != s[i+j-x].

For example,

"ab?a" is valid.

"ax?xc" is invalid because the first character 'a' mismatches with the last character 'c'.

"tbct" is invalid because 'b' != 'c'

The validity of a substring is irrelevant to the query subset. For example, if the query set $$$t$$$ does not contain the character 'b', we still call the string "ab?a" valid, although it certainly cannot form a palindrome. We will deal this case using the $$$set$$$ array.

(2) $$$set[i, j]$$$ denotes all the characters needed to make $$$s[i, j]$$$ a palindrome. For example, if s[i, j] == "ab?a", then set[i, j] == {b}, as we need a character 'b' to fill in the '?'. Note that there are at most $$$17$$$ query characters in this problem, i.e., $$$|t| \leq 17$$$, so we can compress $$$set[i, j]$$$ to a $$$32$$$-bit integer to accelerate computation. Don't use std::set!

(3) $$$free[i, j]$$$ means the number of free characters in the substring $$$s[i, j]$$$. For example, in "ax?xc", the middle '?' is a free character as we could replace it with any character in the query string $$$t$$$. In "ab???a", the first and the second '?' count one free character (Warning: not two!!!). The first '?' can be replaced with an arbitrary character from $$$t$$$, and the second '?' has to be the same with the first '?', so only one of them is free. The third '?' is not free because it has to be 'b'.

Part 3: The naive formula

What is the naive formula for each query string $$$t$$$? It is:

$$$ans(t) = \sum\limits_{1 \leq i,j \leq len(s)} ok[i, j] \cdot [set[i, j] \subseteq t] \cdot |t|^{free[i, j] + num[1, i-1] + num[j+1, len(s)]}$$$ (1)

The $$$[set[i, j] \subseteq t]$$$ is like a Kronecker symbol. If $$$set[i, j] \subseteq t$$$ is true, then $$$[set[i, j] \subseteq t]==1$$$, otherwise $$$[set[i, j] \subseteq t]==0$$$. We need to analyze each $$$i, j$$$. If $$$ok[i, j]$$$ is $$$0$$$, it would never be a palindrome no matter how you fill in the '?'. If $$$ok[i, j]$$$ is $$$1$$$, it depends on the query string $$$t$$$. In part 2, I say that "ab?a" is valid even if $$$t$$$ does not contain 'b'. In this case, $$$ok[i, j]==1$$$ but $$$[set[i, j] \subset t] == 0$$$, the contribution of $$$i,j$$$ is still $$$0$$$. Be careful with the third item, how many strings $$$s$$$ can make $$$s[i, j]$$$ a palindrome? If you only count $$$|t|^{free[i, j]}$$$, you are wrong! Because we can use arbitrary characters to fill in the '?' in $$$s[1, i-1]$$$ and $$$s[j+1, len(s)]$$$, that doesn't affect whether $$$s[i, j]$$$ is a palindrome or not! So, we should not forget $$$num[1, i-1]$$$ and $$$num[j+1, len(s)]$$$.

Part 4: Computation

What is the bottleneck of the naive formula Eq.(1)? Obviously, it takes $$$O(n^2)$$$ for every query, which is too slow. We first figure out:

(1) Computing $$$ok,\,set,\,free$$$ requires $$$O(n^2)$$$ time. Possibly there are $$$O(n)$$$ algorithms, but I don't know. Anyway, $$$O(n^2)$$$ is sufficient to pass. The idea is simple. For odd-length palindromes, we extend from one central character. For even-length palindromes, we extend from two adjacent characters. Initialize the $$$ok$$$ array to $$$0$$$, when you extend, set $$$ok[i, j]$$$ to $$$1$$$, and stop extension when you encounter an invalid pair $$$(i, j)$$$, i.e., s[i] != '?' && s[j] != '?' && s[i] != s[j]!

Tags bitmask, #dpsos, combinatorics

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en30 English Aveiro_quanyue 2023-03-20 10:28:40 4 Tiny change: ' j] == 1} |t|^{free[i, ' -> ' j] == 1} k^{free[i, '
en29 English Aveiro_quanyue 2023-03-18 10:51:56 12
en28 English Aveiro_quanyue 2023-03-18 10:43:18 0 (published)
en27 English Aveiro_quanyue 2023-03-18 10:43:03 56 (saved to drafts)
en26 English Aveiro_quanyue 2023-03-18 10:39:40 282 (published)
en25 English Aveiro_quanyue 2023-03-18 10:36:19 58
en24 English Aveiro_quanyue 2023-03-18 10:34:58 764
en23 English Aveiro_quanyue 2023-03-18 10:29:29 218
en22 English Aveiro_quanyue 2023-03-18 10:27:27 252
en21 English Aveiro_quanyue 2023-03-18 10:25:11 717
en20 English Aveiro_quanyue 2023-03-18 10:16:28 786
en19 English Aveiro_quanyue 2023-03-18 10:06:23 525
en18 English Aveiro_quanyue 2023-03-18 09:58:51 154
en17 English Aveiro_quanyue 2023-03-18 09:57:01 364
en16 English Aveiro_quanyue 2023-03-18 09:53:57 527
en15 English Aveiro_quanyue 2023-03-18 09:49:41 23
en14 English Aveiro_quanyue 2023-03-18 09:47:12 316
en13 English Aveiro_quanyue 2023-03-18 09:43:39 56
en12 English Aveiro_quanyue 2023-03-18 09:42:44 568
en11 English Aveiro_quanyue 2023-03-18 09:37:03 391
en10 English Aveiro_quanyue 2023-03-18 09:33:10 449
en9 English Aveiro_quanyue 2023-03-18 09:28:30 77
en8 English Aveiro_quanyue 2023-03-18 09:27:16 6
en7 English Aveiro_quanyue 2023-03-18 09:26:55 55
en6 English Aveiro_quanyue 2023-03-18 09:23:52 165
en5 English Aveiro_quanyue 2023-03-18 09:22:32 215
en4 English Aveiro_quanyue 2023-03-18 09:18:11 313
en3 English Aveiro_quanyue 2023-03-18 09:15:38 154
en2 English Aveiro_quanyue 2023-03-18 09:04:44 13
en1 English Aveiro_quanyue 2023-03-18 09:04:20 126 Initial revision (saved to drafts)