A note on CF1679E Typical Party in Dorm (CF791DIV2E)

Revision en7, by Aveiro_quanyue, 2023-03-18 09:26:55

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, if $$$s[i,j]$$$ is invalid, then $$$ok[i,j]$$$ is false.

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

Part 2: ok, set and free

We call a substring $$$s[i,j]$$$ valid if and only if:

For every $$$x$$$ such that $$$i \leq x \leq j$$$, if $$$s[x] \neq '?' && s[i+j-x] \neq '?'$$$, then $$$s[x] = s[i+j-x]$$$.

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)