A note on CF1679E Typical Party in Dorm (CF791DIV2E)

Правка en25, от Aveiro_quanyue, 2023-03-18 10:36:19

Problem link, link: https://mirror.codeforces.com/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]!

(2) After computing $$$ok,\,set\,free$$$ for each $$$(i, j)$$$, try to use these three arrays to precompute $$$ans$$$. We could brute force the length easily in this manner:

for(i, j){ //O(n^2)
   for(int length = 0; length <= 17; ++length){ //O(18)
       ...
   }
}

that is not very difficult. The key problem is that, when you get a $$$set(i, j)$$$, we should update all its supersets, which might cost $$$O(2^{|t|})$$$ for each $$$(i, j)$$$. We use the "separation of variables trick". We define two $$$dp$$$ arrays, $$$dp1$$$ to solve the original problem and $$$dp2$$$ to solve $$$dp1$$$. The final output is $$$dp2$$$:

$$$dp1[submask][k] := \sum\limits_{1 \leq i,j \leq len(s); set[i, j] == submask; ok[i, j] == 1} |t|^{free[i, j] + num[1, i-1] + num[j+1, len(s)]}$$$. (2)

$$$dp2[mask][k] := \sum\limits_{submask \subseteq mask} dp1[submask][k]$$$. (3)

$$$ans(t) = dp2[t][|t|]$$$. (4)

This trick is important. You can see that $$$dp2$$$ is irrelevant to the original formula. $$$dp1$$$ could be calculated in $$$O(n^2|t|)$$$ time (we need to brute force the length). You might think the computation of $$$dp2$$$ is hard, but we have a powerful for it: The SOSDP! Here is a super good tutorial for SOSDP: https://mirror.codeforces.com/blog/entry/45223. If you don't grasp SOSDP, this problem might be hard for you, because SOSDP costs $$$O(2^{|t|}|t|^2)$$$ times to solve it while the naive method costs $$$O(3^{|t|}|t|)$$$! A clarification: The tutorial says SOSDP is $$$O(2^{|t|}|t|)$$$ and the naive method is $$$O(3^{|t|})$$$. This is definitely right. But in this problem, we needs to brute force the length, so there is another $$$|t|$$$ in both the SOSDP and the naive methods.

Briefly speaking, SOSDP solves this problem in $$$O(|t|2^{|t|})$$$ time, and this is almost exactly the Eq. (3) in the definition of $$$dp2$$$:

Given $$$G$$$ that maps $$$O(2^{|t|})$$$ bitmasks to real numbers, calculate $$$F$$$:

$$$F(mask) := \sum\limits_{submask \subseteq mask} G(submask)$$$.

The code is brief:

memcpy(F, G, sizeof(G)); 
for(int i = 0; i < t; ++i) for(int mask = 0; mask < (1<<t); ++mask){ //O(t2^|t|)
	if(mask & (1<<i)) F[mask] += F[mask^(1<<i)];
}

We also note that SOSDP could be used in place, if we don't need the original G after computation. That means the memcpy step could be omitted. The below algorithm is also correct, because when we calculate G[mask], all the submasks of mask are correctly calculated.

//Here: Original G
for(int i = 0; i < t; ++i) for(int mask = 0; mask < (1<<t); ++mask){ //O(t2^|t|)
	if(mask & (1<<i)) G[mask] += G[mask^(1<<i)];
}
//now G is the F and the original G gets lost!

(3)Overall complexity:

$O(|t|(n^2 + 2^{|t|} + |q|))

Теги bitmask, #dpsos, combinatorics

История

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