Codeforces Round 972 (Div. 2) Editorial

Правка en1, от Tsovak, 2024-09-12 19:01:54

There are 2 observstions needed to solve the problem. 1) Let's say we have fixed the number if vowels. Define them by $$$a_{0\cdots4}$$$. Obviously, $$$a_0 + \cdots a_4 = n$$$ First, let's not consider the empty string as it doesn't change anything. Then, the number of palindrome subsequences will be at least $$$A = 2^{a_0} + \cdots + 2^{a_4} - 5$$$. Now, notice that if we put the same characters consecutively then the answer would be exactly A, and that would be the best possible answer for that fixed numbers (there can't be other palindrome subsequences because if the first and last characters are the same, then all the middle part will be the same as well). 2) Now, we need to find the best array $$$a$$$. To do this, let's assume there are 2 mumbers $$$x$$$ and $$$y$$$ in the array such that $$$x + 2 \leq y$$$. Then, $$$2^x + 2^y \big 2 \times 2^{y-1} \beq 2^{x+1} + 2^{y-1}$$$. This means, that replacing $$$x$$$ and $$$y$$$ with $$$x+1$$$ and $$$y-1$$$ will not change the sum of the array $$$a$$$ but will make the number of palindrome subsequences smaller. We can do this replacing process untill no two numbers in $$$a$$$ have difference bigger than $$$1$$$. Finally, there is only one such array (not considering its permutations). It contains

Unable to parse markup [type=CF_MATHJAX]

$$$n/5$$$-s and

Unable to parse markup [type=CF_MATHJAX]

$$$(n/5)+1$$$-s.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en85 Английский BiNARyBeastt 2024-09-16 18:51:36 2
en84 Английский BiNARyBeastt 2024-09-16 18:50:59 2 Tiny change: 'oblem/D)\n\nCheck [t' -> 'oblem/D)\nCheck [t'
en83 Английский BiNARyBeastt 2024-09-16 18:50:28 2 Tiny change: 'lem/D)\n\n\nCheck ' -> 'lem/D)\n\nCheck '
en82 Английский BiNARyBeastt 2024-09-16 18:49:33 5 Tiny change: 'oblem/D)\nCheck [t' -> 'oblem/D)\n\n\nCheck [t' (published)
en81 Английский BiNARyBeastt 2024-09-16 18:48:58 127 (saved to drafts)
en80 Английский BiNARyBeastt 2024-09-16 18:43:40 38
en79 Английский BiNARyBeastt 2024-09-15 14:12:22 223
en78 Английский BiNARyBeastt 2024-09-15 12:51:31 3 Tiny change: ' if (n <= 20) { // sl' -> ' if (n <= 300) { // sl'
en77 Английский Tsovak 2024-09-15 11:45:51 0 (published)
en76 Английский Tsovak 2024-09-15 11:45:26 2 Tiny change: 'iminate $k $from the s' -> 'iminate $k$ from the s'
en75 Английский Tsovak 2024-09-15 11:43:42 4 (saved to drafts)
en74 Английский BiNARyBeastt 2024-09-15 11:35:54 5 Tiny change: 'ting from index +1 or even e' -> 'ting from $ind+1$ or even e'
en73 Английский BiNARyBeastt 2024-09-15 10:46:01 224
en72 Английский BiNARyBeastt 2024-09-15 10:42:59 161
en71 Английский Tsovak 2024-09-15 01:06:19 0 (published)
en70 Английский Tsovak 2024-09-15 01:05:40 224 Tiny change: 'y even $x$ $dp_{x,i,' -> 'y even $x$, $dp_{x,i,'
en69 Английский Tsovak 2024-09-15 00:53:34 1630
en68 Английский Tsovak 2024-09-15 00:51:28 1191 (saved to drafts)
en67 Английский Tsovak 2024-09-15 00:34:10 0 (published)
en66 Английский Tsovak 2024-09-15 00:33:49 1448
en65 Английский Tsovak 2024-09-15 00:33:17 1446
en64 Английский Tsovak 2024-09-15 00:31:58 13 Tiny change: 'oiler>\n\n~~~~~\n#' -> 'oiler>\n\n<spoiler summary="Code (E1)">\n~~~~~\n#'
en63 Английский Tsovak 2024-09-15 00:28:41 2 Tiny change: 'r summary=Hint 5">\n' -> 'r summary="Hint 5">\n'
en62 Английский Tsovak 2024-09-15 00:27:36 1242
en61 Английский Tsovak 2024-09-15 00:20:42 18
en60 Английский Tsovak 2024-09-15 00:12:09 2 Tiny change: 'pend on $a-1$. One of' -> 'pend on $a_1$. One of'
en59 Английский Tsovak 2024-09-15 00:08:45 1 Tiny change: 'Finalizing**\n\nBut ' -> 'Finalizing.**\n\nBut '
en58 Английский Tsovak 2024-09-15 00:08:16 6 Tiny change: '\approx O(\cdot 10^9)$. It' -> '\approx O(10^9)$. It'
en57 Английский Tsovak 2024-09-15 00:07:54 4 Tiny change: '\approx O(5\tcdot 10^8)$. It is ' -> '\approx O(\cdot 10^9)$. It is '
en56 Английский Tsovak 2024-09-15 00:05:42 5243
en55 Английский Tsovak 2024-09-14 23:36:39 5356 Tiny change: ' $\gcd$-s.\n\nLet's ' -> ' $\gcd$-s.**\n\nLet's ' (saved to drafts)
en54 Английский Tsovak 2024-09-14 20:28:37 0 (published)
en53 Английский Tsovak 2024-09-14 20:28:24 2 Tiny change: 'ty: $O(n*m*7)$.\n\n</s' -> 'ty: $O(n*m)$.\n\n</s' (saved to drafts)
en52 Английский Tsovak 2024-09-14 20:14:13 254
en51 Английский Tsovak 2024-09-14 20:07:44 0 (published)
en50 Английский Tsovak 2024-09-14 20:06:32 32 Tiny change: 'm*7)$.\n\nMemory complexity: $O(n*m*7)$.\n</spoile' -> 'm*7)$.\n\n</spoile'
en49 Английский Tsovak 2024-09-14 20:05:33 3053 (saved to drafts)
en48 Английский Tsovak 2024-09-14 19:44:05 0 (published)
en47 Английский Tsovak 2024-09-14 19:43:33 1 Tiny change: 'roblem/E1)\n[E2 &mda' -> 'roblem/E1),\n[E2 &mda'
en46 Английский Tsovak 2024-09-14 19:43:01 9373 Tiny change: 'the matrix.\n</spoile' -> 'the matrix?\n</spoile'
en45 Английский BiNARyBeastt 2024-09-14 19:12:15 4652
en44 Английский BiNARyBeastt 2024-09-14 19:07:26 2870 Reverted to en41
en43 Английский BiNARyBeastt 2024-09-14 19:04:03 2895
en42 Английский BiNARyBeastt 2024-09-14 18:58:54 4623
en41 Английский Tsovak 2024-09-13 21:49:10 288
en40 Английский Tsovak 2024-09-13 21:36:59 401 Tiny change: 't most $\leg(M)$). Al' -> 't most $\log(M)$). Al'
en39 Английский Tsovak 2024-09-13 21:19:34 934 Tiny change: 'ddle part. Then, we c' -> 'ddle part.\n\nThen, we c'
en38 Английский Tsovak 2024-09-13 21:03:58 112
en37 Английский Tsovak 2024-09-13 21:01:58 2 Tiny change: 'e exactly A, and that' -> 'e exactly $A$, and that'
en36 Английский Tsovak 2024-09-13 21:01:05 1523
en35 Английский Tsovak 2024-09-13 20:47:10 20
en34 Английский Tsovak 2024-09-13 20:37:22 83
en33 Английский Tsovak 2024-09-13 20:34:06 742 Tiny change: 'summary="HIint>\nLet'' -> 'summary="Hint>\nLet''
en32 Английский Tsovak 2024-09-13 19:59:19 163
en31 Английский Tsovak 2024-09-13 19:51:12 552 Tiny change: ' of $a$.\nLet's de' -> ' of $a$.\n\nLet's de'
en30 Английский Tsovak 2024-09-13 18:45:05 1383
en29 Английский Tsovak 2024-09-13 18:42:32 1153
en28 Английский Tsovak 2024-09-13 18:37:58 22
en27 Английский Tsovak 2024-09-13 18:15:53 243
en26 Английский Tsovak 2024-09-13 18:11:48 6
en25 Английский Tsovak 2024-09-13 18:10:32 87 Tiny change: ' + counted\textunderscorescore$.\n\' -> ' + counted \textunderscore score$.\n\'
en24 Английский Tsovak 2024-09-13 18:01:01 33 Tiny change: '-\infty$. We loop through the $n$ strings. For the ' -> '-\infty$. For the '
en23 Английский Tsovak 2024-09-13 17:59:35 148
en22 Английский Tsovak 2024-09-13 17:53:06 1657 Tiny change: ' = dp_4 = $\infty$. W' -> ' = dp_4 = \infty$. W'
en21 Английский Tsovak 2024-09-13 17:27:12 90
en20 Английский Tsovak 2024-09-13 17:25:54 214
en19 Английский Tsovak 2024-09-13 17:20:21 745 Tiny change: 'blem/B1)\n\n[B2 &mda' -> 'blem/B1)\n[B2 &mda'
en18 Английский Tsovak 2024-09-13 17:19:03 20
en17 Английский Tsovak 2024-09-12 21:32:15 18
en16 Английский Tsovak 2024-09-12 21:31:07 454
en15 Английский Tsovak 2024-09-12 21:22:15 41
en14 Английский Tsovak 2024-09-12 21:21:16 90 Tiny change: 'picked as a middle cell) of two t' -> 'picked as the middle) of two t'
en13 Английский Tsovak 2024-09-12 21:18:18 82
en12 Английский Tsovak 2024-09-12 21:17:19 1077 Tiny change: 'n\n[2005A &mdash; Simple Pa' -> 'n\n[2005A - Simple Pa'
en11 Английский Tsovak 2024-09-12 20:46:42 402
en10 Английский Tsovak 2024-09-12 20:41:59 2 Tiny change: 'ontest/2009/problem/A' -> 'ontest/2005/problem/A'
en9 Английский Tsovak 2024-09-12 20:41:29 632 Tiny change: 'oblem/A)\n<spoiler' -> 'oblem/A)\n\n<spoiler'
en8 Английский Tsovak 2024-09-12 20:22:14 671 Tiny change: ' 2^y > 2 \times 2^{y-1} \' -> ' 2^y > 2 \cdot 2^{y-1} \'
en7 Английский Tsovak 2024-09-12 19:54:08 1 Reverted to en5
en6 Английский BiNARyBeastt 2024-09-12 19:39:55 1 Tiny change: '\n\n<spoiler' -> '\n<spoiler'
en5 Английский Tsovak 2024-09-12 19:38:17 80 Tiny change: '\n<spoiler s' -> '<spoiler s'
en4 Английский Tsovak 2024-09-12 19:10:33 214 Tiny change: 'he problem.\n\n1. Let's say w' -> 'he problem:\n\n1. Firstly, let's say w'
en3 Английский Tsovak 2024-09-12 19:05:09 13 Tiny change: 'problem.\n1. Let'' -> 'problem.\n\n\n1. aaa\n2. bbb\n\n\n1. Let''
en2 Английский Tsovak 2024-09-12 19:03:33 6
en1 Английский Tsovak 2024-09-12 19:01:54 1293 Initial revision (saved to drafts)