1798.md (10572B)
1 Source: https://codeforces.com/blog/entry/114208 2 3 Thank you all for participating, I hope you enjoyed the problems! You can rate the problems of the round in the corresponding spoilers. 4 5 [1798A - Showstopper](/contest/1798/problem/A "Codeforces Round 860 (Div. 2)") 6 7 **Hint 1** 8 9 For each index $i$, it makes no sense to perform the operation $\ge 2$ once, since applying the operation with the same index twice does not change anything. 10 11 **Hint 2** 12 13 Condition $a_n = \max(a_1, a_2, \ldots, a_n)$ is equivalent to $a_i \leq a_n$ for all $i$. So for each index $i$ there are only 2 conditions: $a_i \leq a_n$ and $b_i \leq b_n$. 14 15 **Tutorial** 16 17 Tutorial is loading... 18 19 **Solution** 20 21 ``` 22 for _ in range(int(input())): 23 n = int(input()) 24 a = list(map(int, input().split())) 25 b = list(map(int, input().split())) 26 for i in range(n): 27 if a[i] > b[i]: 28 a[i], b[i] = b[i], a[i] 29 if a[-1] == max(a) and b[-1] == max(b): 30 print("YES") 31 else: 32 print("NO") 33 ``` 34 35 **Rate the problem** 36 37 * Didnt solve 38 * Good problem 39 * Average problem 40 * Bad problem 41 42 [1798B - Three Sevens](/contest/1798/problem/B "Codeforces Round 860 (Div. 2)") 43 44 **Hint 1** 45 46 Let the participant with the number $X$ participate in the lottery in days $i_1 \lt i_2 \lt \ldots \lt i_k$. On what days could the participant $X$ be chosen as the winner so as not to break the conditions? 47 48 **Hint 2** 49 50 If there are several candidates for the lottery winner on the day of $i$ (who did not participate in the days from $i+1$ to $m$), does it matter which of them we choose as a winner? 51 52 **Tutorial** 53 54 Tutorial is loading... 55 56 **Solution** 57 58 ``` 59 MAX = 50000 60 last = [0] * (MAX + 777) 61 for _ in range(int(input())): 62 m = int(input()) 63 a_ = [] 64 for day in range(m): 65 n = int(input()) 66 a = list(map(int, input().split())) 67 for x in a: 68 last[x] = day 69 a_.append(a) 70 ans = [-1] * m 71 for day in range(m): 72 for x in a_[day]: 73 if last[x] == day: 74 ans[day] = x 75 if ans[day] == -1: 76 print(-1) 77 break 78 else: 79 print(*ans) 80 ``` 81 82 **Rate the problem** 83 84 * Didnt solve 85 * Good problem 86 * Average problem 87 * Bad problem 88 89 [1798C - Candy Store](/contest/1798/problem/C "Codeforces Round 860 (Div. 2)") 90 91 **Hint 1** 92 93 In which case 1 price tag is enough? 94 95 **Hint 1.1** 96 97 For any positive integers $x, y, z$, the statement ``$x$ is divisible by $y$'' equivalent to the statement ``$xz$ is divisible by $yz$' 98 99 **Hint 1.2** 100 101 Let's denote the total cost of all packs of candies for $cost$. Rewrite all the conditions given in the problem so that they become conditions only for the number $cost$. Hint1.1 will help in this. 102 103 **Hint 2** 104 105 If one price tag is enough for a set of candies, then if you remove any type of candy from this set, one price tag will still be enough. This is a reason to think about greedy. 106 107 **Tutorial** 108 109 Tutorial is loading... 110 111 **Solution** 112 113 ``` 114 from math import gcd 115 116 def lcm(a, b): 117 return a * b // gcd(a, b) 118 119 for _ in range(int(input())): 120 n = int(input()) 121 a = [] 122 b = [] 123 for i in range(n): 124 ai, bi = map(int, input().split()) 125 a.append(ai) 126 b.append(bi) 127 g = 0 128 l = 1 129 ans = 1 130 for i in range(n): 131 g = gcd(g, a[i] * b[i]) 132 l = lcm(l, b[i]) 133 if g % l: 134 ans += 1 135 g = a[i] * b[i] 136 l = b[i] 137 print(ans) 138 ``` 139 140 **Rate the problem** 141 142 * Didnt solve 143 * Good problem 144 * Average problem 145 * Bad problem 146 147 [1798D - Shocking Arrangement](/contest/1798/problem/D "Codeforces Round 860 (Div. 2)") 148 149 **Hint 1** 150 151 Express $\max\limits_{1 \leq l \leq r \leq n} \lvert a_l+a_{l+1}+\ldots+a_r\rvert$ in a simpler way. 152 153 **Hint 1.1** 154 155 Use the prefix sums of the array $a$. 156 157 **Hint 2** 158 159 Build the answer starting from an empty array. If you add numbers to the response so that the prefix sum is always in the half-interval $(\min(a), \max(a)]$, the resulting array will fit the condition. How to do it? Remember that the sum of the array is $0$. 160 161 **Tutorial** 162 163 Tutorial is loading... 164 165 **Solution** 166 167 ``` 168 for _ in range(int(input())): 169 n = int(input()) 170 a = list(map(int, input().split())) 171 if max(a) == 0: 172 print("No") 173 else: 174 print("Yes") 175 prefix_sum = 0 176 pos = [] 177 neg = [] 178 for x in a: 179 if x >= 0: 180 pos.append(x) 181 else: 182 neg.append(x) 183 ans = [] 184 for _ in range(n): 185 if prefix_sum <= 0: 186 ans.append(pos[-1]) 187 pos.pop() 188 else: 189 ans.append(neg[-1]) 190 neg.pop() 191 prefix_sum += ans[-1] 192 print(' '.join(list(map(str, ans)))) 193 ``` 194 195 **Rate the problem** 196 197 * Didnt solve 198 * Good problem 199 * Average problem 200 * Bad problem 201 202 [1798E - Multitest Generator](/contest/1798/problem/E "Codeforces Round 860 (Div. 2)") 203 204 **Hint 1** 205 206 Estimate from above the number of changes for which you can make a multitest from an arbitrary array. 207 208 **Hint 2** 209 210 How to check for each suffix whether it is a multitest by itself (without changes)? 211 212 **Hint 2.1** 213 214 This is done using one-dimensional dynamic programming by suffixes. 215 216 **Hint 3** 217 218 Let's say you want to check if an array can turn into a multitest for $1$ change. Find all the elements that could potentially be changed (all the elements are such that changing them could lead to the array becoming a multitest without being it initially). For each of them, you need to determine whether it is possible to make a change that turns array into multitest. One-dimensional dynamic programming by suffixes will help to take into account all these variants of change. 219 220 **Tutorial** 221 222 Tutorial is loading... 223 224 **Solution** 225 226 ``` 227 N = 300777 228 a = [0] * N 229 go = [0] * N 230 good_chain = [0] * N 231 chain_depth = [0] * N 232 suf_max_chain_depth = [0] * N 233 234 ans = "" 235 for _ in range(int(input())): 236 n = int(input()) 237 a = [0] + list(map(int, input().split())) 238 chain_depth[n + 1] = 0 239 suf_max_chain_depth[n + 1] = 0 240 curr_max_chain_depth = 0 241 for i in range(n, 0, -1): 242 go[i] = i + a[i] + 1 243 if go[i] == n + 1 or (go[i] <= n and good_chain[go[i]]): 244 good_chain[i] = True 245 else: 246 good_chain[i] = False 247 chain_depth[i] = 1 + chain_depth[min(go[i], n + 1)] 248 suf_max_chain_depth[i] = 1 + curr_max_chain_depth 249 if go[i] <= n + 1: 250 suf_max_chain_depth[i] = max(suf_max_chain_depth[i], 1 + suf_max_chain_depth[go[i]]) 251 if good_chain[i]: 252 curr_max_chain_depth = max(curr_max_chain_depth, chain_depth[i]) 253 for i in range(1, n): 254 if good_chain[i + 1] and chain_depth[i + 1] == a[i]: 255 ans += "0 " 256 elif good_chain[i + 1] or suf_max_chain_depth[i + 1] >= a[i]: 257 ans += "1 " 258 else: 259 ans += "2 " 260 ans += '\n' 261 print(ans) 262 ``` 263 264 **Rate the problem** 265 266 * Didnt solve 267 * Good problem 268 * Average problem 269 * Bad problem 270 271 [1798F - Gifts from Grandfather Ahmed](/contest/1798/problem/F "Codeforces Round 860 (Div. 2)") 272 273 **Hint 1** 274 275 Let's say the box you selected will be sent to the largest class. Then if this class has a size of $s$, you can send any $s-1$ from the available boxes there. So you can not worry about this class, and pick boxes for the rest, always having as potential options $s-1$ additional boxes. Plenty of room for maneuver. 276 277 **Hint 2** 278 279 The solution exists for any valid input 280 281 **Hint 3** 282 283 After Hint2 think about some specific inputs. You know, they always have a solution. This should inspire you. 284 285 **Hint 3.1** 286 287 $k = 2, s_1 = s_2$. 288 289 **Hint 4** 290 291 Erdős--Ginzburg--Ziv theorem 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 #define pb push_back 303 // #define int long long 304 #define all(x) x.begin(), x.end() 305 #define ld long double 306 using namespace std; 307 const int N = 210; 308 bool dp[N][N][N]; 309 bool take[N][N][N]; 310 311 signed main() { 312 ios::sync_with_stdio(false); 313 cin.tie(nullptr); 314 cout.tie(nullptr); 315 int n, k; 316 cin >> n >> k; 317 vector<int> a(n), s(k); 318 for (int i = 0; i < n; i++) { 319 cin >> a[i]; 320 } 321 for (int i = 0; i < k; i++) { 322 cin >> s[i]; 323 } 324 vector<pair<int, int>> s2; 325 for (int i = 0; i < k; i++) { 326 s2.pb({s[i], i}); 327 } 328 sort(all(s2)); 329 vector<vector<int>> ans(k); 330 for (int i = 0; i < k - 1; i++) { 331 int class_size = s2[i].first; 332 vector<int> boxes; 333 for (int _ = 0; _ < 2 * class_size - 1; _++) { 334 boxes.pb(a.back()); 335 a.pop_back(); 336 } 337 for (int sz = 0; sz <= class_size; sz++) { 338 for (int r = 0; r < class_size; r++) { 339 dp[0][sz][r] = false; 340 take[0][sz][r] = false; 341 } 342 } 343 dp[0][0][0] = true; 344 dp[0][1][boxes[0] % class_size] = true; 345 take[0][1][boxes[0] % class_size] = true; 346 for (int j = 1; j < (int) boxes.size(); j++) { 347 for (int sz = 0; sz <= class_size; sz++) { 348 for (int r = 0; r < class_size; r++) { 349 dp[j][sz][r] = dp[j - 1][sz][r]; 350 if (sz > 0 && dp[j - 1][sz - 1][(class_size + r - boxes[j] % class_size) % class_size]) { 351 dp[j][sz][r] = true; 352 take[j][sz][r] = true; 353 } else { 354 take[j][sz][r] = false; 355 } 356 } 357 } 358 } 359 vector<bool> used(2 * class_size - 1); 360 int sz = class_size, r = 0; 361 for (int j = (int) boxes.size() - 1; j >= 0; j--) { 362 if (take[j][sz][r]) { 363 used[j] = true; 364 sz--; 365 r += (class_size - boxes[j] % class_size); 366 r %= class_size; 367 } else { 368 used[j] = false; 369 } 370 } 371 vector<int> to_class; 372 for (int j = 0; j < (int) boxes.size(); j++) { 373 if (!used[j]) { 374 a.pb(boxes[j]); 375 } else { 376 to_class.pb(boxes[j]); 377 } 378 } 379 ans[s2[i].second] = to_class; 380 } 381 382 int sum = 0; 383 for (auto x : a) { 384 sum += x; 385 sum %= (int) (a.size() + 1); 386 } 387 int add = (int) (a.size() + 1) - sum; 388 ans[s2[k - 1].second] = a; 389 ans[s2[k - 1].second].pb(add); 390 391 cout << add << '\n'; 392 for (auto arr : ans) { 393 for (auto x : arr) { 394 cout << x << ' '; 395 } 396 cout << '\n'; 397 } 398 } 399 ``` 400 401 **Rate the problem** 402 403 * Didnt solve 404 * Good problem 405 * Average problem 406 * Bad problem