CodeTON Round 7 (Div. 1 + Div. 2, Rated, Prizes!) Editorial

Правка en2, от lanhf, 2023-11-25 11:18:04

1896A - Jagged Swaps

Hint 1

Observe that since we are only allowed to choose $$$i \ge 2$$$ to swap $$$a_i$$$ and $$$a_{i+1}$$$, it means that $$$a_1$$$ cannot be modified by the operation. Hence, $$$a_1 = 1$$$ must hold. In fact, we can prove that as long as $$$a_1 = 1$$$, we will be able to sort the array.

Consider the largest element of the array. Let its index be $$$i$$$. Our objective is to move $$$a_i$$$ to the end of the array. If $$$i = n$$$, it means that the largest element is already at the end. Otherwise, since $$$a_i$$$ is the largest element, this means that $$$a_{i-1} < a_i$$$ and $$$a_i > a_{i+1}$$$. Hence, we can do an operation on index $$$i$$$ and move the largest element one step closer to the end. We repeatedly do the operation until we finally move the largest element to the end of the array. Then, we can pretend that the largest element does not exist and do the same algorithm for the prefix of size $$$n - 1$$$. Hence, we will able to sort the array by doing this repeatedly.

1896B - AB Flipping

Hint 1

If the string consists of only $$$\texttt{A}$$$ or only $$$\texttt{B}$$$, no operations can be done and hence the answer is $$$0$$$. Otherwise, let $$$x$$$ be the smallest index where $$$s_x = \texttt{A}$$$ and $$$y$$$ be the largest index where $$$x_y = \texttt{B}$$$. If $$$x > y$$$, this means that the string is of the form $$$s=\texttt{B}\ldots\texttt{BA}\ldots\texttt{A}$$$. Since all the $$$\texttt{B}$$$ are before the $$$\texttt{A}$$$, no operation can be done and hence the answer is also $$$0$$$.

Now, we are left with the case where $$$x < y$$$. Note that $$$s[1,x-1] = \texttt{B}\ldots\texttt{B}$$$ and $$$s[y+1,n] = \texttt{A}\ldots\texttt{A}$$$ by definition. Since the operation moves $$$\texttt{A}$$$ to the right and $$$\texttt{B}$$$ to the left, this means that $$$s[1,x - 1]$$$ will always consist of all $$$\texttt{B}$$$ and $$$s[y + 1, n]$$$ will always consist of all $$$\texttt{A}$$$. Hence, no operation can be done from index $$$1$$$ to $$$x - 1$$$ as well as from index $$$y$$$ to $$$n - 1$$$.

The remaining indices where an operation could possibly be done are from $$$x$$$ to $$$y - 1$$$. In fact, it can be proven that all $$$y - x$$$ operations can be done if their order is chosen optimally. Let array $$$b$$$ store the indices of $$$s$$$ between $$$x$$$ and $$$y$$$ that contain $$$\texttt{B}$$$ in increasing order. In other words, $$$x < b_1 < b_2 < \ldots < b_k = y$$$ and $$$b_i = \texttt{B}$$$, where $$$k$$$ is the number of occurences of $$$\texttt{B}$$$ between $$$x$$$ and $$$y$$$. For convenience, we let $$$b_0 = x$$$. Then, we do the operations in the following order:

$$$b_1 - 1, b_1 - 2, \ldots, b_0 + 1, b_0,$$$

$$$b_2 - 1, b_2 - 2, \ldots, b_1 + 1, b_1,$$$

$$$b_3 - 1, b_3 - 2, \ldots, b_2 + 1, b_2,$$$

$$$\vdots$$$

$$$b_k - 1, b_k - 2, \ldots, b_{k - 1} + 1, b_k$$$

It can be seen that the above ordering does operation on all indices between $$$x$$$ and $$$y - 1$$$. To see why all of the operations are valid, we look at each row separately. Each row starts with $$$b_i - 1$$$, which is valid as $$$s_{b_i} = \texttt{B}$$$ and $$$s_{b_i - 1} = \texttt{A}$$$ (assuming that it is not the last operation of the row). Then, the following operations in the same row move $$$\texttt{B}$$$ to the left until position $$$b_{i - 1}$$$. To see why the last operation of the row is valid as well, even though $$$s_{b_{i - 1}}$$$ might be equal to $$$\texttt{B}$$$ initially by definition, either $$$i = 1$$$ which means that $$$s_{b_0} = s_x = \texttt{A}$$$, or an operation was done on index $$$b_{i - 1} - 1$$$ in the previous row which moved $$$\texttt{A}$$$ to index $$$b_{i - 1}$$$. Hence, all operations are valid.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en25 Английский lanhf 2023-11-30 00:37:55 14
en24 Английский lanhf 2023-11-30 00:36:26 31
en23 Английский lanhf 2023-11-28 12:15:31 4
en22 Английский lanhf 2023-11-26 21:08:59 120
en21 Английский lanhf 2023-11-26 07:19:48 13
en20 Английский lanhf 2023-11-26 07:16:23 2
en19 Английский maomao90 2023-11-26 07:07:19 2 (published)
en18 Английский lanhf 2023-11-26 05:41:30 485 (saved to drafts)
en17 Английский lanhf 2023-11-26 05:14:28 46
en16 Английский lanhf 2023-11-26 05:10:11 106
en15 Английский lanhf 2023-11-26 05:06:06 4104 Add solution for H
en14 Английский maomao90 2023-11-26 03:42:40 400
en13 Английский lanhf 2023-11-25 21:45:58 128
en12 Английский lanhf 2023-11-25 21:44:55 6983
en11 Английский lanhf 2023-11-25 21:39:16 10543
en10 Английский lanhf 2023-11-25 21:26:10 2
en9 Английский lanhf 2023-11-25 21:08:00 5
en8 Английский lanhf 2023-11-25 21:06:23 2 Tiny change: 'm $v-2$.\n*Proof*:' -> 'm $v-2$.\n\n*Proof*:'
en7 Английский lanhf 2023-11-25 21:05:16 7 (published)
en6 Английский lanhf 2023-11-25 21:04:36 3 Tiny change: '**Claim**: If the rea' -> '**Claim**:\nIf the rea'
en5 Английский lanhf 2023-11-25 21:03:46 42
en4 Английский lanhf 2023-11-25 21:02:21 16965
en3 Английский lanhf 2023-11-25 20:46:33 86
en2 Английский lanhf 2023-11-25 11:18:04 3619 Tiny change: 'brah' -> '## [problem:1896A]'
en1 Английский lanhf 2023-11-08 12:54:38 63 Initial revision (saved to drafts)