A note on CF1679E Typical Party in Dorm (CF791DIV2E)

Правка en17, от Aveiro_quanyue, 2023-03-18 09:57:01

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)]}$$$

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 call 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)]$$$.

Теги 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)