A note on CF1679E Typical Party in Dorm (CF791DIV2E)

Правка en12, от Aveiro_quanyue, 2023-03-18 09:42:44

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

Part 1: Notations

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

$$$s[i,j] (i \leq j)$$$: The substring including $$$s[i]$$$ and $$$s[j]$$$: $$$(s[i], s[i+1],..., s[j])$$$.

$$$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

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