codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

2085.md (15206B)


      1 Source: https://codeforces.com/blog/entry/140933
      2 
      3 **Fun Fact 0**
      4 
      5 [Attention is all you need](https://arxiv.org/abs/1706.03762).
      6 
      7 **Fun Fact 1**
      8 
      9 The current problems are the original A A B C D E, respectively.
     10 
     11 **Fun Fact 2**
     12 
     13 The idea for problem D came up after eating at Sushiro, and the idea for problem E came up after eating at McDonald's. However, Sushiro is not a buffet restaurant. :(
     14 
     15 **Fun Fact 3**
     16 
     17 The intended solutions are short.
     18 
     19 **Fun Fact 4**
     20 
     21 Some (very) strong testers couldn't solve E when testing, and that's why we gave E so much score.
     22 
     23 **Fun Fact suggested by testers**
     24 
     25 ![...](/predownloaded/61/a0/61a03f0e26b325e41dd12a2aa483b30b9e9e7c30.png)
     26 
     27 #### [2085A - Serval and String Theory](/contest/2085/problem/A "Codeforces Round 1011 (Div. 2)")
     28 
     29 **Hint 1**
     30 
     31 When $s$ is lexicographically equal to or greater than the reversal of $s$, is it possible to make $s$ *universal* by performing the operations?
     32 
     33 **Hint 2**
     34 
     35 If possible, what is the minimum number of the operations required to make $s$ *universal*?
     36 
     37 **Solution**
     38 
     39 **Case 1.** If $s$ contains only one kind of letter, the answer will be `NO`.
     40 
     41 **Case 2.** If $s$ is *universal* already, no operation is needed, and the answer will be `YES`.
     42 
     43 Otherwise, $s$ falls into the following **Case 3**.
     44 
     45 **Case 3.1.** When $s$ is not a palindrome, one can make $s$ *universal* in one operation by swapping the first pair of different letters of $s$ and its reversal.
     46 
     47 $ \left.\begin{aligned} s ={}& \texttt{s}{\color{red}{\underline{\texttt{t}}}}\texttt{rings} \\ \text{reversal of } s ={}& \texttt{s}{\color{red}{\underline{\texttt{g}}}}\texttt{nirts} \end{aligned}\;\right\} \xrightarrow{\text{swap}} \boxed{\texttt{sgrints}} $
     48 
     49 **Case 3.2.** When $s$ is a palindrome, swapping any two distinct letters will make $s$ no longer a palindrome. Note that the reversal of $s$ after the swap can be obtained by swapping the letters in the symmetric positions of the original $s$. Since either $s$ or its reversal is *universal*, the original $s$ can be made *universal* in one operation.
     50 
     51 $ s = \texttt{l}{\color{red}{\underline{\texttt{e}}}}{\color{blue}{\underline{\texttt{v}}}}\texttt{el} \xrightarrow{\text{swap}} \left\{\;\begin{aligned} s' ={}& \texttt{l}{\color{blue}{\underline{\texttt{v}}}}{\color{red}{\underline{\texttt{e}}}}\texttt{el} \\ \text{reversal of } s' ={}& \texttt{le}{\color{red}{\underline{\texttt{e}}}}{\color{blue}{\underline{\texttt{v}}}}\texttt{l} \end{aligned}\;\right\} \;\boxed{\texttt{leevl}} $
     52 
     53 Thus, for **Case 3**, the answer will be `NO` if no operation can be performed; otherwise, the answer will be `YES`.
     54 
     55 **Code (Python)**
     56 
     57 ```
     58 getint = lambda: int(input())
     59 getints = lambda: map(int, input().split())
     60 
     61 def solve():
     62 	n, k = getints()
     63 	s = input().strip()
     64 	if s < s[::-1] or (k >= 1 and min(s) != max(s)):
     65 		print('YES')
     66 	else:
     67 		print('NO')
     68 
     69 t = getint()
     70 for _ in range(t):
     71 	solve()
     72 ```
     73 
     74 #### [2085B - Serval and Final MEX](/contest/2085/problem/B "Codeforces Round 1011 (Div. 2)")
     75 
     76 **Hint 1**
     77 
     78 Before the last operation, what should the array be to obtain $0$?
     79 
     80 **Hint 2**
     81 
     82 How to make all the elements in the array non-zero?
     83 
     84 **Solution**
     85 
     86 Note that before the last operation, all the integers in the array should be positive. Thus, we aim to turn the zeroes in $a$ into non-zeroes. To achieve this, we split the given array $a$ into two halves and perform the operations on the halves that contain zeroes. After that, there will be no zeroes in either of the two halves. The final $0$ can be obtained by performing the last operation on the entire array.
     87 
     88 $ [{\color{red}{\underline{1, 0, 1, 1}}}, {\color{blue}{2, 0, 8, 5}}] \to [{\color{red}{2}}, {\color{blue}{\underline{2, 0, 8, 5}}}] \to [\underline{{\color{red}{2}}, {\color{blue}{1}}}] \to [0] $
     89 
     90 **Another Hint**
     91 
     92 In fact, the final element can be $0$ after the operations for any array of length $4$. Can you solve the problem under the constraint of $n=4$?
     93 
     94 **Another Solution**
     95 
     96 When $n \gt 4$, you can perform the operation on any subarray of length $(n-3)$. After the operation, the array $a$ will contain only $4$ integers, which can be solved by brute force.
     97 
     98 **Code (Python)**
     99 
    100 ```
    101 getint = lambda: int(input())
    102 getints = lambda: map(int, input().split())
    103 
    104 def solve():
    105 	n = getint()
    106 	a = list(getints())
    107 	op = []
    108 	mid, r = n // 2, n
    109 	if 0 in a[mid:]:
    110 		op.append([mid + 1, n])
    111 		r -= n - mid - 1
    112 	if 0 in a[:mid]:
    113 		op.append([1, mid])
    114 		r -= mid - 1
    115 	op.append([1, r])
    116 	print(len(op))
    117 	for o in op:
    118 		print(*o)
    119 
    120 t = getint()
    121 for _ in range(t):
    122 	solve()
    123 ```
    124 
    125 #### [2085C - Serval and The Formula](/contest/2085/problem/C "Codeforces Round 1011 (Div. 2)")
    126 
    127 **Hint 1**
    128 
    129 The formula $(x+k) + (y+k) = (x+k) \oplus (y+k)$ is equivalent to $(x+k) \mathbin{\&} (y+k) = 0$, where $\&$ denotes the bitwise AND operation.
    130 
    131 **Hint 2**
    132 
    133 Note that a power of $2$ shares no common bits with any positive integer less than it.
    134 
    135 **Solution**
    136 
    137 It can be shown that such an non-negative integer $k$ does not exist when $x=y$.
    138 
    139 When $x\neq y$, one can show that $k = 2^n - \max(x, y)$ is a possible answer, where $2^n$ is a power of $2$ that is sufficiently large.
    140 
    141 **Code (Python)**
    142 
    143 ```
    144 getint = lambda: int(input())
    145 getints = lambda: map(int, input().split())
    146 
    147 def solve():
    148 	x, y = getints()
    149 	if x == y:
    150 		print(-1)
    151 	else:
    152 		print(2 ** 48 - max(x, y))
    153 
    154 t = getint()
    155 for _ in range(t):
    156 	solve()
    157 ```
    158 
    159 #### [2085D - Serval and Kaitenzushi Buffet](/contest/2085/problem/D "Codeforces Round 1011 (Div. 2)")
    160 
    161 **Hint 1**
    162 
    163 Do not go for DP.
    164 
    165 **Hint 2**
    166 
    167 How many plates of sushi can be taken?
    168 
    169 **Hint 3**
    170 
    171 What are the constraints on the time of taking plates of sushi?
    172 
    173 **Solution**
    174 
    175 Note that the last $i$-th time taking a plate of sushi should be no later than the $(n - i\cdot(k+1) + 1)$-th minute. This constraint limits the time that a taking action can be performed. Therefore, we enumerate the $n$ minutes in chronological order, and greedily take the untaken plates delivered before with the greatest *deliciousness* when we reach a constraint, i.e., the current minute is the $(n - i\cdot(k+1) + 1)$-th minute for a certain $i$. The *deliciousnesses* of the untaken plates can be maintained by a heap. The total complexity is $O(n \log n)$.
    176 
    177 **Code (C++)**
    178 
    179 ```
    180 #include <cstdio>
    181 #include <queue>
    182 
    183 using namespace std;
    184 
    185 const int N = 2e5 + 5;
    186 
    187 int n, k;
    188 int d[N];
    189 long long ans;
    190 
    191 void solve() {
    192 	scanf("%d%d", &n, &k);
    193 	ans = 0;
    194 	priority_queue <int> q;
    195 	for (int i = 1; i <= n; i++) {
    196 		scanf("%d", &d[i]);
    197 		q.push(d[i]);
    198 		if ((n - i + 1) % (k + 1) == 0) {
    199 			ans += q.top();
    200 			q.pop();
    201 		}
    202 	}
    203 	printf("%lld\n", ans);
    204 }
    205 
    206 int main() {
    207 	int t;
    208 	scanf("%d", &t);
    209 	while (t--)
    210 		solve();
    211 	return 0;
    212 }
    213 ```
    214 
    215 #### [2085E - Serval and Modulo](/contest/2085/problem/E "Codeforces Round 1011 (Div. 2)")
    216 
    217 **Hint 1**
    218 
    219 What happens when an integer $a_i$ mods $k$?
    220 
    221 **Hint 2**
    222 
    223 Note that the difference between $a_i$ and $b_i$ is a multiple of $k$.
    224 
    225 **Hint 3**
    226 
    227 The same holds for the difference between the sum of $a_i$ and the sum of $b_i$.
    228 
    229 **Hint 4**
    230 
    231 Notice that $d(n) \leq 2304$ holds for all $n \leq 10^{10}$, where $d(n)$ denotes the number of divisors of $n$.
    232 
    233 **Solution**
    234 
    235 Note that if such a magic number $k$ exists, it will be a divisor of $\Delta = \sum a_i - \sum b_i$ when $\Delta \neq 0$, or it can be any integer greater than all the $a_i$. Thus, we can check all the divisors of $\Delta$, resulting in a solution of $O\left(\sum (n \cdot d(\sum a_i) + \sqrt{\sum a_i})\right)$ time, where $d(n)$ denotes the number of divisors of $n$.
    236 
    237 **Code (C++)**
    238 
    239 ```
    240 #include <cstdio>
    241 
    242 using namespace std;
    243 
    244 const int N = 1e4 + 5;
    245 const int C = 1e6 + 5;
    246 
    247 int n;
    248 int a[N], b[N];
    249 int cnt[C];
    250 long long s;
    251 
    252 bool check(int k) {
    253 	for (int i = 1; i <= n; i++)
    254 		cnt[a[i] % k]++;
    255 	for (int i = 1; i <= n; i++)
    256 		if (--cnt[b[i]] < 0) {
    257 			cnt[b[i]] = 0;
    258 			for (int i = 1; i <= n; i++)
    259 				cnt[a[i] % k] = 0;
    260 			return 0;
    261 		}
    262 	return 1;
    263 }
    264 
    265 void solve() {
    266 	scanf("%d", &n);
    267 	s = 0;
    268 	for (int i = 1; i <= n; i++) {
    269 		scanf("%d", &a[i]);
    270 		s += a[i];
    271 	}
    272 	for (int i = 1; i <= n; i++) {
    273 		scanf("%d", &b[i]);
    274 		s -= b[i];
    275 	}
    276 	if (s == 0) {
    277 		printf("%d\n", check(0xc0ffee) ? 0xc0ffee : -1);
    278 		return;
    279 	}
    280 	for (int i = 1; 1ll * i * i <= s; i++)
    281 		if (s % i == 0) {
    282 			if (check(i)) {
    283 				printf("%d\n", i);
    284 				return;
    285 			}
    286 			if (i < C && check(s / i)) {
    287 				printf("%d\n", (int)(s / i));
    288 				return;
    289 			}
    290 		}
    291 	printf("-1\n");
    292 }
    293 
    294 int main() {
    295 	int t;
    296 	scanf("%d", &t);
    297 	while (t--)
    298 		solve();
    299 	return 0;
    300 }
    301 ```
    302 
    303 #### [2085F1 - Serval and Colorful Array (Easy Version)](/contest/2085/problem/F1 "Codeforces Round 1011 (Div. 2)")
    304 
    305 **Hint 1**
    306 
    307 Consider the integers in the *colorful* subarray after swapping.
    308 
    309 **Hint 2**
    310 
    311 How to gather these integers together, forming a *colorful* subarray, with the minimum number of swaps?
    312 
    313 **Hint 3**
    314 
    315 Consider the middle one among all the the elements in the *colorful* subarray.
    316 
    317 **Solution**
    318 
    319 Consider the elements in the *colorful* subarray after swapping. The first observation is as follows.
    320 
    321 **Observation.** Mark the elements in the *colorful* subarray. Before swapping, to make these marked elements continuous, gathering them toward the middle one among them minimizes the number of swaps.
    322 
    323 **Proof.** It is not optimal to swap two marked elements. Thus, the leftmost $x$ elements will move to their right, and the rightmost $(k-x)$ elements will move to their left. They will meet at some point between the $x$-th element and the $(x+1)$-th element. If $x \lt {k\over 2}$, adjusting the meeting point to its right reduces $(k-x)-x \gt 0$ swaps. If $x \gt {k\over 2}$, we can adjust it to its left and reduce the number of swaps similarly. Therefore, one can show that setting the meeting point to the middle of them is optimal through adjustments. $\square$
    324 
    325 From the observation we can also conclude that, the minimum number of swaps required to make the marked elements continuous is the difference between the sum of the distances from each marked element to the middle position before swapping and that sum after swapping, if the marked elements are swapped toward the middle position. Notice that the latter sum is a fixed constant only related to $k$.
    326 
    327 Focusing on the middle position of the *colorful* subarray, we enumerate all the positions in the array as possible middle positions. For each possible middle position $p$, to form the *colorful* subarray whose middle position is $p$, we should choose ${k\over 2}$ distinct integers from its left and the other $k\over 2$ from its right. The rounding of $k\over 2$ will not affect the correctness as long as the sum of the rounded numbers is $k$.
    328 
    329 For each $1\leq i\leq k$, we should determine whether $i$ should be chosen from the left side of $p$ or the right side of $p$. Let the distance from $p$ to the rightmost integer $i$ on its left be $l_i$, and the distance for the right side be $r_i$. We should choose either $l_i$ or $r_i$ for each $i$ under the constraint that both the number of chosen $l_i$ and that of $r_i$ are $k\over 2$, minimizing the sum of the distances we choose. This can be done by first forcing to choose all the $l_i$, and then choosing the smallest $k\over 2$ elements of $(r_i-l_i)$ greedily.
    330 
    331 In implementation, when enumerating the middle position $p$, both $l_i$ and $r_i$ can be simply calculated in $O(n)$ time, and then sort $(r_i - l_i)$ in $O(n\log n)$ time. The total complexity is $O(n^2\log n)$.
    332 
    333 **Code (C++)**
    334 
    335 ```
    336 #include <cstdio>
    337 #include <algorithm>
    338 
    339 using namespace std;
    340 
    341 const int N = 3005;
    342 const long long oo = 1e18;
    343 
    344 int n, k;
    345 int a[N], l[N], r[N], d[N];
    346 long long ans;
    347 
    348 void solve() {
    349 	scanf("%d%d", &n, &k);
    350 	for (int i = 1; i <= n; i++)
    351 		scanf("%d", &a[i]);
    352 	ans = oo;
    353 	for (int i = 1; i <= n; i++) {
    354 		for (int j = 1; j <= k; j++)
    355 			l[j] = r[j] = n + 1;
    356 		for (int j = i; j; j--)
    357 			l[a[j]] = min(l[a[j]], i - j);
    358 		for (int j = i; j <= n; j++)
    359 			r[a[j]] = min(r[a[j]], j - i);
    360 		long long s = 0;
    361 		for (int j = 1; j <= k; j++) {
    362 			s += l[j];
    363 			d[j] = r[j] - l[j];
    364 		}
    365 		sort(d + 1, d + k + 1);
    366 		for (int j = 1; j <= (k + 1) / 2; j++)
    367 			s += d[j];
    368 		ans = min(ans, s);
    369 	}
    370 	for (int i = 1; i <= k; i++)
    371 		ans -= abs(i - (k + 1) / 2);
    372 	printf("%lld\n", ans);
    373 }
    374 
    375 int main() {
    376 	int T;
    377 	scanf("%d", &T);
    378 	while (T--)
    379 		solve();
    380 	return 0;
    381 }
    382 ```
    383 
    384 #### [2085F2 - Serval and Colorful Array (Hard Version)](/contest/2085/problem/F2 "Codeforces Round 1011 (Div. 2)")
    385 
    386 **Hint 1**
    387 
    388 Is it possible to simplify the constraints?
    389 
    390 **Hint 2**
    391 
    392 Is it possible to remove the constraint that exactly $k\over 2$ elements should be chosen from both sides of the enumerated position?
    393 
    394 **Solution**
    395 
    396 Optimizing the solution of F1 using (possibly, heavy) data structures results in a $O(n\log n)$ solution.
    397 
    398 Here we introduce a linear approach for F2 came up by [Error_Yuan](/profile/Error_Yuan "Grandmaster Error_Yuan"). In fact, the following proposition holds.
    399 
    400 **Proposition.** The answer obtained is still correct without the constraint that exactly $k\over 2$ elements should be chosen from both sides of the enumerated position.
    401 
    402 Without the constraint, when enumerating the position $p$, we can directly choose the smaller one between $l_i$ and $r_i$ for each $1\leq i\leq k$.
    403 
    404 **Proof.** On the one hand, notice that the distance sum will not be smaller when $p$ is not the middle position among the chosen elements. On the other hand, consider the *colorful* subarray that produces the optimal answer, and mark the elements in it first. When $p$ enumerates to the middle position of the marked elements before swapping, the minimal distance sum without the constraint is no greater than that under the constraint. Therefore, all the considered candidates are no less than the real answer, and the real answer can be reached, completing the proof. $\square$
    405 
    406 In implementation, we consider the contribution to each position $p$ for each integer $1\leq i\leq k$. For a certain $i$, it can be shown that the delta of the contribution will be one of $-1$, $0$, or $+1$ when $p$ moves to an adjacent position. The delta of the contribution remains unchanged for most positions, and only changes either at the position where $i$ placed, or at the midpoint between two adjacent $i$. By pre-calculating the changes of contribution deltas over all the $i$ and performing the prefix sum on the array twice, we can obtain the distance sums, resulting in an $O(n)$ solution.
    407 
    408 **Code (C++)**
    409 
    410 ```
    411 #include <cstdio>
    412 #include <algorithm>
    413 
    414 using namespace std;
    415 
    416 const int N = 4e5 + 5;
    417 const long long oo = 1e18;
    418 
    419 int n, k;
    420 int a[N];
    421 int last[N], dd[N];
    422 long long s, d, ans;
    423 
    424 void solve() {
    425 	scanf("%d%d", &n, &k);
    426 	for (int i = 1; i <= n; i++)
    427 		last[i] = dd[i] = 0;
    428 	s = 0;
    429 	for (int i = 1; i <= n; i++) {
    430 		scanf("%d", &a[i]);
    431 		if (!last[a[i]])
    432 			s += i - 1;
    433 		else {
    434 			int pre = last[a[i]];
    435 			int mid = (pre + i) / 2;
    436 			if ((pre + i) & 1) {
    437 				dd[mid]--;
    438 				dd[mid + 1]--;
    439 			} else
    440 				dd[mid] -= 2;
    441 		}
    442 		dd[i] += 2;
    443 		last[a[i]] = i;
    444 	}
    445 	ans = oo;
    446 	d = -k;
    447 	for (int i = 1; i <= n; i++) {
    448 		ans = min(ans, s);
    449 		d += dd[i];
    450 		s += d;
    451 	}
    452 	for (int i = 1; i <= k; i++)
    453 		ans -= abs(i - (k + 1) / 2);
    454 	printf("%lld\n", ans);
    455 }
    456 
    457 int main() {
    458 	int T;
    459 	scanf("%d", &T);
    460 	while (T--)
    461 		solve();
    462 	return 0;
    463 }
    464 ```