1741.md (8782B)
1 Source: https://codeforces.com/blog/entry/107908 2 3 [1741A - Compare T-Shirt Sizes](/contest/1741/problem/A "Codeforces Round 826 (Div. 3)") 4 5 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution** 12 13 ``` 14 #include <bits/stdc++.h> 15 16 using namespace std; 17 18 #define forn(i, n) for (int i = 0; i < int(n); i++) 19 #define sz(v) (int)v.size() 20 #define all(v) v.begin(),v.end() 21 #define eb emplace_back 22 23 24 void ct(char c) { 25 cout << c << '\n'; 26 } 27 28 void solve() { 29 string a,b; cin >> a >> b; 30 char ca = a.back(); 31 char cb = b.back(); 32 if (ca == cb) { 33 if (sz(a) == sz(b)) cout << '='; 34 else if (ca == 'S') { 35 cout << (sz(a) < sz(b) ? '>' : '<'); 36 } else { 37 cout << (sz(a) < sz(b) ? '<' : '>'); 38 } 39 }else cout << (ca < cb ? '>' : '<'); 40 cout << '\n'; 41 } 42 43 int main() { 44 int t; 45 cin >> t; 46 47 forn(tt, t) { 48 solve(); 49 } 50 } 51 ``` 52 53 [1741B - Funny Permutation](/contest/1741/problem/B "Codeforces Round 826 (Div. 3)") 54 55 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 56 57 **Tutorial** 58 59 Tutorial is loading... 60 61 **Solution** 62 63 ``` 64 #include "bits/stdc++.h" 65 using namespace std; 66 67 void solve(){ 68 int n; 69 cin >> n; 70 if(n == 3){ 71 cout << -1 << endl; 72 } 73 else{ 74 for(int i = 3; i <= n; i++) cout << i << ' '; 75 cout << 2 << ' ' << 1 << endl; 76 } 77 } 78 79 int main(){ 80 int t; 81 cin >> t; 82 while(t--){ 83 solve(); 84 } 85 } 86 ``` 87 88 [1741C - Minimize the Thickness](/contest/1741/problem/C "Codeforces Round 826 (Div. 3)") 89 90 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 91 92 **Tutorial** 93 94 Tutorial is loading... 95 96 **Solution** 97 98 ``` 99 #include <bits/stdc++.h> 100 101 using namespace std; 102 103 const int MAXN = 2020; 104 105 int n; 106 int arr[MAXN]; 107 108 int go(int i, int sum) { 109 if (i == n) return 0; 110 for (int j = i + 1, cur = 0; j <= n; ++j) { 111 cur += arr[j - 1]; 112 if (cur > sum) return n; 113 if (cur == sum) return max(j - i, go(j, sum)); 114 } 115 return n; 116 } 117 118 int solve() { 119 int ans = n; 120 for (int len = 1, sum = 0; len < n; ++len) { 121 sum += arr[len - 1]; 122 ans = min(ans, go(0, sum)); 123 } 124 return ans; 125 } 126 127 int main() { 128 int t; cin >> t; 129 while (t--) { 130 cin >> n; 131 for (int i = 0; i < n; ++i) 132 cin >> arr[i]; 133 cout << solve() << endl; 134 } 135 } 136 ``` 137 138 [1741D - Masha and a Beautiful Tree](/contest/1741/problem/D "Codeforces Round 826 (Div. 3)") 139 140 Idea: [Gornak40](/profile/Gornak40 "Expert Gornak40") 141 142 **Tutorial** 143 144 Tutorial is loading... 145 146 **Solution** 147 148 ``` 149 #include <bits/stdc++.h> 150 151 using namespace std; 152 153 const int MAXM = 300300; 154 155 int n, m; 156 int arr[MAXM]; 157 158 int solve(int l, int r) { 159 if (r - l == 1) return 0; 160 int mid = (l + r) >> 1; 161 int mal = *max_element(arr + l, arr + mid); 162 int mar = *max_element(arr + mid, arr + r); 163 int ans = 0; 164 if (mal > mar) { 165 ++ans; 166 for (int i = 0; i < (mid - l); ++i) 167 swap(arr[l + i], arr[mid + i]); 168 } 169 return solve(l, mid) + solve(mid, r) + ans; 170 } 171 172 int solve() { 173 int ans = solve(0, m); 174 if (is_sorted(arr, arr + m)) 175 return ans; 176 return -1; 177 } 178 179 int main() { 180 int t; cin >> t; 181 while (t--) { 182 cin >> m; 183 for (int i = 0; i < m; ++i) 184 cin >> arr[i]; 185 cout << solve() << endl; 186 } 187 } 188 ``` 189 190 [1741E - Sending a Sequence Over the Network](/contest/1741/problem/E "Codeforces Round 826 (Div. 3)") 191 192 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov") 193 194 **Tutorial** 195 196 Tutorial is loading... 197 198 **Solution** 199 200 ``` 201 #include <bits/stdc++.h> 202 203 using namespace std; 204 205 #define forn(i, n) for (int i = 0; i < int(n); i++) 206 #define sz(v) (int)v.size() 207 #define all(v) v.begin(),v.end() 208 #define eb emplace_back 209 210 void solve() { 211 int n; cin >> n; 212 vector<int> a(n+1); 213 for (int i = 1; i <= n; ++i) { 214 cin >> a[i]; 215 } 216 217 vector<bool> dp(n+1, false); 218 dp[0] = true; 219 for (int i = 1; i <= n; ++i) { 220 if (i + a[i] <= n && dp[i-1]) dp[i + a[i]] = true; 221 if (i - a[i] - 1 >= 0 && dp[i - a[i] - 1]) dp[i] = true; 222 } 223 cout << (dp[n] ? "YES" : "NO") << '\n'; 224 } 225 226 int main() { 227 int t; 228 cin >> t; 229 230 forn(tt, t) { 231 solve(); 232 } 233 } 234 ``` 235 236 [1741F - Multi-Colored Segments](/contest/1741/problem/F "Codeforces Round 826 (Div. 3)") 237 238 Idea: [MikeMirzayanov](/profile/MikeMirzayanov "Headquarters, MikeMirzayanov"), [ibraevdmitriy](/profile/ibraevdmitriy "Master ibraevdmitriy") 239 240 **Tutorial** 241 242 Tutorial is loading... 243 244 **Solution** 245 246 ``` 247 #include <iostream> 248 #include <vector> 249 #include <algorithm> 250 #include <set> 251 #include <queue> 252 253 using namespace std; 254 255 int n; 256 257 vector<int> calc(vector<vector<int>> a) { 258 vector<pair<int, int>> l(n), r(n); 259 for (int i = 0; i < n; ++i) { 260 l[i] = {a[i][0], i}; 261 r[i] = {a[i][1], i}; 262 } 263 sort(l.begin(), l.end()); 264 sort(r.begin(), r.end()); 265 vector<vector<pair<int, int>>> suf(n); 266 vector<pair<int, int>> curr; 267 for (int i0 = n - 1; i0 >= 0; --i0) { 268 int xr = r[i0].first; 269 int i = r[i0].second; 270 int xl = a[i][0]; 271 int c = a[i][2]; 272 if (curr.empty()) { 273 curr.emplace_back(xl, c); 274 } else if (curr.size() == 1) { 275 if (curr[0].second == c) { 276 curr[0].first = min(curr[0].first, xl); 277 } else { 278 curr.emplace_back(xl, c); 279 } 280 } else { 281 if (curr[0].second == c) { 282 curr[0].first = min(curr[0].first, xl); 283 } else if (curr[1].second == c) { 284 curr[1].first = min(curr[1].first, xl); 285 } else { 286 curr.emplace_back(xl, c); 287 } 288 } 289 sort(curr.begin(), curr.end()); 290 if (curr.size() == 3) { 291 curr.pop_back(); 292 } 293 suf[i0] = curr; 294 } 295 vector<int> ans(n, 1e9); 296 int j = 0; 297 for (int i0 = 0; i0 < n; ++i0) { 298 int xl = l[i0].first, i = l[i0].second; 299 int xr = a[i][1], c = a[i][2]; 300 while (j < n && r[j].first < xl) { 301 j++; 302 } 303 if (j < n) { 304 vector<pair<int, int>> s = suf[j]; 305 if (s[0].second != c) { 306 ans[i] = min(ans[i], max(0, s[0].first - xr)); 307 } else if (s.size() == 2) { 308 ans[i] = min(ans[i], max(0, s[1].first - xr)); 309 } 310 } 311 } 312 return ans; 313 } 314 315 const int K = 1e9 + 1; 316 317 void solve() { 318 cin >> n; 319 vector<vector<int>> a(n, vector<int>(3)), b(n, vector<int>(3)); 320 vector<pair<int, int>> l(n), r(n); 321 for (int i = 0; i < n; ++i) { 322 for (int j = 0; j < 3; ++j) { 323 cin >> a[i][j]; 324 if (j == 2) { 325 b[i][j] = a[i][j]; 326 } else { 327 b[i][1 - j] = K - a[i][j]; 328 } 329 } 330 } 331 vector<int> ans1 = calc(a), ans2 = calc(b); 332 for (int i = 0; i < n; ++i) { 333 cout << min(ans1[i], ans2[i]) << ' '; 334 } 335 cout << '\n'; 336 } 337 338 int main() { 339 ios_base::sync_with_stdio(0); 340 cin.tie(0), cout.tie(0); 341 int t = 1; 342 cin >> t; 343 for (int it = 0; it < t; ++it) { 344 solve(); 345 } 346 return 0; 347 } 348 ``` 349 350 [1741G - Kirill and Company](/contest/1741/problem/G "Codeforces Round 826 (Div. 3)") 351 352 Idea: [Vladosiya](/profile/Vladosiya "Expert Vladosiya") 353 354 **Tutorial** 355 356 Tutorial is loading... 357 358 **Solution** 359 360 ``` 361 from collections import deque 362 363 364 def solve(): 365 n, m = map(int, input().split()) 366 sl = [[] for _ in range(n)] 367 for _ in range(m): 368 u, v = map(int, input().split()) 369 u -= 1 370 v -= 1 371 sl[u] += [v] 372 sl[v] += [u] 373 f = int(input()) 374 h = [int(x) - 1 for x in input().split()] 375 mask = [0] * n 376 k = int(input()) 377 p = [int(x) - 1 for x in input().split()] + [-1] 378 for i in range(k): 379 mask[h[p[i]]] += 1 << i 380 vars = [set() for _ in range(n)] 381 dist = [-1] * n 382 dist[0] = 0 383 vars[0].add(mask[0]) 384 q = deque([0]) 385 while len(q) > 0: 386 v = q.popleft() 387 for u in sl[v]: 388 if dist[u] == -1: 389 dist[u] = dist[v] + 1 390 q.append(u) 391 if dist[u] == dist[v] + 1: 392 for msk in vars[v]: 393 vars[u].add(msk | mask[u]) 394 backpack = [False] * (1 << k) 395 backpack[0] = True 396 j = 0 397 for i in range(f): 398 if i == p[j]: 399 j += 1 400 continue 401 nw = backpack.copy() 402 for msk in range(1 << k): 403 if not backpack[msk]: 404 continue 405 for var in vars[h[i]]: 406 nw[msk | var] = True 407 backpack, nw = nw, backpack 408 mn = k 409 for msk in range(1 << k): 410 if not backpack[msk]: 411 continue 412 ans = 0 413 for b in range(k): 414 if msk & (1 << b) == 0: 415 ans += 1 416 mn = min(mn, ans) 417 print(mn) 418 419 420 t = int(input()) 421 for _ in range(t): 422 solve() 423 ```