Codeforces Round 972 (Div. 2) Editorial

Revision en2, by Tsovak, 2024-09-12 19:03:33

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.

History

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