1420.md (11764B)
1 Source: https://codeforces.com/blog/entry/82978 2 3 [1420A - Cubes Sorting](/contest/1420/problem/A "Codeforces Round 672 (Div. 2)") 4 5 **Hint** 6 7 Any array can be sorted using no more than $\frac{n(n-1)}2$ operations. Think or guess when we need exactly $\frac{n(n-1)}2$ operations. 8 9 **Solution** 10 11 Tutorial is loading... 12 13 **Code in C++ (Wind_Eagle)** 14 15 ``` 16 #include<iostream> 17 18 using namespace std; 19 20 int a[1000000+5]; 21 22 int main() 23 { 24 ios_base::sync_with_stdio(false); 25 cin.tie(0); 26 cout.tie(0); 27 int t; 28 cin>>t; 29 while (t--) 30 { 31 int n; 32 cin>>n; 33 for (int i=0; i<n; i++) 34 { 35 cin>>a[i]; 36 } 37 bool can=false; 38 for (int i=1; i<n; i++) 39 { 40 if (a[i]>=a[i-1]) 41 { 42 can=true; 43 break; 44 } 45 } 46 if (can) cout<<"YES"<<'\n'; 47 else cout<<"NO"<<'\n'; 48 } 49 } 50 ``` 51 52 [1420B - Rock and Lever](/contest/1420/problem/B "Codeforces Round 672 (Div. 2)") 53 54 **Hint** 55 56 Think of a simple criteria when `a_i & a_j >= a_i ^ a_j` by considering the bits from highest to lowest. Apply your observations to calculate the answer fast. 57 58 **Solution** 59 60 Tutorial is loading... 61 62 **Code in C++ (Wind_Eagle)** 63 64 ``` 65 #include<iostream> 66 #include<vector> 67 #include<algorithm> 68 #include<ctime> 69 #include<random> 70 71 using namespace std; 72 73 mt19937 rnd(time(NULL)); 74 75 int a[1000000+5]; 76 77 int main() 78 { 79 ios_base::sync_with_stdio(false); 80 cin.tie(0); 81 cout.tie(0); 82 int t; 83 cin>>t; 84 while (t--) 85 { 86 int n; 87 cin>>n; 88 for (int i=0; i<n; i++) 89 { 90 cin>>a[i]; 91 } 92 int64_t ans=0; 93 for (int j=29; j>=0; j--) 94 { 95 int64_t cnt=0; 96 for (int i=0; i<n; i++) 97 { 98 if (a[i]>=(1<<j)&&a[i]<(1<<(j+1))) 99 { 100 cnt++; 101 } 102 } 103 ans+=cnt*(cnt-1)/2; 104 } 105 cout<<ans<<'\n'; 106 } 107 } 108 ``` 109 110 [1420C1 - Pokémon Army (easy version)](/contest/1420/problem/C1 "Codeforces Round 672 (Div. 2)") 111 112 **Hint** 113 114 Use dynamic programming. 115 116 **Solution** 117 118 Tutorial is loading... 119 120 **Code in C++ (gepardo)** 121 122 ``` 123 #include <iostream> 124 #include <vector> 125 126 using namespace std; 127 128 inline int64_t calc(const vector<int> &a) { 129 int n = a.size(); 130 vector<int64_t> d1(n+1), d2(n+1); 131 d1[0] = -static_cast<int64_t>(1e18); 132 d2[0] = 0; 133 for (int i = 0; i < n; ++i) { 134 d1[i+1] = max(d1[i], d2[i] + a[i]); 135 d2[i+1] = max(d2[i], d1[i] - a[i]); 136 } 137 return max(d1.back(), d2.back()); 138 } 139 140 int main() { 141 ios_base::sync_with_stdio(false); 142 int t; cin >> t; 143 while (t--) { 144 int n, q; cin >> n >> q; 145 vector<int> a(n); 146 for (int i = 0; i < n; ++i) { 147 cin >> a[i]; 148 } 149 cout << calc(a) << "\n"; 150 for (int i = 0; i < q; ++i) { 151 int l, r; cin >> l >> r; --l; --r; 152 swap(a[l], a[r]); 153 cout << calc(a) << "\n"; 154 } 155 } 156 return 0; 157 } 158 ``` 159 160 [1420C2 - Pokémon Army (hard version)](/contest/1420/problem/C2 "Codeforces Round 672 (Div. 2)") 161 162 **Hint** 163 164 The dynamic programming doesn't work here. Consider taking only local minima and maxima and think whether we need to take something else. 165 166 **Solution** 167 168 Tutorial is loading... 169 170 **Code in Java (gepardo)** 171 172 ``` 173 import java.io.*; 174 import java.util.*; 175 176 public class C2_Java { 177 int[] a; 178 int n; 179 long ans; 180 181 void add(int i, int sign) { 182 if (i == 0 || i == n+1) return; 183 if (a[i-1] < a[i] && a[i] > a[i+1]) ans += sign * a[i]; 184 if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= sign * a[i]; 185 } 186 187 void addTwo(int l, int r, int sign) { 188 if (l == r) return; 189 if (l+1 == r) { 190 add(l-1, sign); 191 add(l, sign); 192 add(r, sign); 193 add(r+1, sign); 194 return; 195 } 196 add(l-1, sign); 197 add(l, sign); 198 add(l+1, sign); 199 if (l+2 != r) add(r-1, sign); 200 add(r, sign); 201 add(r+1, sign); 202 } 203 204 public void run() throws IOException { 205 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 206 BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); 207 208 StringTokenizer tok = new StringTokenizer(in.readLine()); 209 int t = Integer.parseInt(tok.nextToken()); 210 while (t --> 0) { 211 tok = new StringTokenizer(in.readLine()); 212 n = Integer.parseInt(tok.nextToken()); 213 int q = Integer.parseInt(tok.nextToken()); 214 a = new int[n + 2]; 215 tok = new StringTokenizer(in.readLine()); 216 for (int i = 1; i <= n; ++i) { 217 a[i] = Integer.parseInt(tok.nextToken()); 218 } 219 a[0] = -1; 220 a[n+1] = -1; 221 ans = 0; 222 StringBuilder builder = new StringBuilder(); 223 for (int i = 1; i <= n; ++i) { 224 if (a[i-1] < a[i] && a[i] > a[i+1]) ans += a[i]; 225 if (a[i-1] > a[i] && a[i] < a[i+1]) ans -= a[i]; 226 } 227 builder.append(ans).append("\n"); 228 while (q --> 0) { 229 tok = new StringTokenizer(in.readLine()); 230 int l = Integer.parseInt(tok.nextToken()); 231 int r = Integer.parseInt(tok.nextToken()); 232 if (l == r) { 233 builder.append(ans).append("\n"); 234 continue; 235 } 236 addTwo(l, r, -1); 237 int tmp = a[l]; 238 a[l] = a[r]; 239 a[r] = tmp; 240 addTwo(l, r, +1); 241 builder.append(ans).append("\n"); 242 } 243 out.write(builder.toString()); 244 } 245 246 in.close(); 247 out.close(); 248 } 249 250 public static void main(String[] args) throws IOException { 251 (new C2_Java()).run(); 252 } 253 } 254 ``` 255 256 **Code in C++ (Wind_Eagle)** 257 258 ``` 259 #include<iostream> 260 261 using namespace std; 262 263 #define int long long 264 265 int a[1000000+5]; 266 267 int n; 268 269 int ans=0; 270 271 inline void insert(int i) 272 { 273 if (i==0||i==n+1) return; 274 if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i]; 275 if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i]; 276 } 277 278 inline void erase(int i) 279 { 280 if (i==0||i==n+1) return; 281 if (a[i-1]<a[i]&&a[i]>a[i+1]) ans-=a[i]; 282 if (a[i-1]>a[i]&&a[i]<a[i+1]) ans+=a[i]; 283 } 284 285 int32_t main() 286 { 287 ios_base::sync_with_stdio(false); 288 cin.tie(0); 289 cout.tie(0); 290 int t; 291 cin>>t; 292 while (t--) 293 { 294 int q; 295 cin>>n>>q; 296 for (int i=1; i<=n; i++) 297 { 298 cin>>a[i]; 299 } 300 a[0]=-1; 301 a[n+1]=-1; 302 ans=0; 303 for (int i=1; i<=n; i++) 304 { 305 if (a[i-1]<a[i]&&a[i]>a[i+1]) ans+=a[i]; 306 if (a[i-1]>a[i]&&a[i]<a[i+1]) ans-=a[i]; 307 } 308 cout<<ans<<'\n'; 309 while (q--) 310 { 311 int l,r; 312 cin>>l>>r; 313 erase(l-1); 314 erase(l); 315 erase(l+1); 316 if (l!=r) 317 { 318 if (r-1!=l+1&&r-1!=l) erase(r-1); 319 if (r!=l+1) erase(r); 320 erase(r+1); 321 } 322 swap(a[l],a[r]); 323 insert(l-1); 324 insert(l); 325 insert(l+1); 326 if (l!=r) 327 { 328 if (r-1!=l+1&&r-1!=l) insert(r-1); 329 if (r!=l+1) insert(r); 330 insert(r+1); 331 } 332 cout<<ans<<'\n'; 333 } 334 } 335 } 336 ``` 337 338 [1420D - Rescue Nibel!](/contest/1420/problem/D "Codeforces Round 672 (Div. 2)") 339 340 **Hint** 341 342 The intersection of any $k$ segments is either empty or is a segment. Let's fix the left bound of the intersection and calculate the number of sets of $k$ segments such that their intersection starts in this left bound. 343 344 **Solution** 345 346 Tutorial is loading... 347 348 **Code in Java (gepardo)** 349 350 ``` 351 import java.io.*; 352 import java.util.*; 353 354 public class D_Java { 355 public static final int MOD = 998244353; 356 357 public static int mul(int a, int b) { 358 return (int)((long)a * (long)b % MOD); 359 } 360 361 int[] f; 362 int[] rf; 363 364 public int C(int n, int k) { 365 return (k < 0 || k > n) ? 0 : mul(f[n], mul(rf[n-k], rf[k])); 366 } 367 368 public static int pow(int a, int n) { 369 int res = 1; 370 while (n != 0) { 371 if ((n & 1) == 1) { 372 res = mul(res, a); 373 } 374 a = mul(a, a); 375 n >>= 1; 376 } 377 return res; 378 } 379 380 static void shuffleArray(int[] a) { 381 Random rnd = new Random(); 382 for (int i = a.length-1; i > 0; i--) { 383 int index = rnd.nextInt(i + 1); 384 int tmp = a[index]; 385 a[index] = a[i]; 386 a[i] = tmp; 387 } 388 } 389 390 public static int inv(int a) { 391 return pow(a, MOD-2); 392 } 393 394 public void doIt() throws IOException { 395 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); 396 397 StringTokenizer tok = new StringTokenizer(in.readLine()); 398 int n = Integer.parseInt(tok.nextToken()); 399 int k = Integer.parseInt(tok.nextToken()); 400 401 f = new int[n+42]; 402 rf = new int[n+42]; 403 f[0] = rf[0] = 1; 404 for (int i = 1; i < f.length; ++i) { 405 f[i] = mul(f[i-1], i); 406 rf[i] = mul(rf[i-1], inv(i)); 407 } 408 409 int[] events = new int[2*n]; 410 for (int i = 0; i < n; ++i) { 411 tok = new StringTokenizer(in.readLine()); 412 int le = Integer.parseInt(tok.nextToken()); 413 int ri = Integer.parseInt(tok.nextToken()); 414 events[i] = le*2; 415 events[i + n] = ri*2 + 1; 416 } 417 shuffleArray(events); 418 Arrays.sort(events); 419 420 int ans = 0; 421 int balance = 0; 422 for (int r = 0; r < 2*n;) { 423 int l = r; 424 while (r < 2*n && events[l] == events[r]) { 425 ++r; 426 } 427 int added = r - l; 428 if (events[l] % 2 == 0) { 429 // Open event 430 ans += C(balance + added, k); 431 if (ans >= MOD) ans -= MOD; 432 ans += MOD - C(balance, k); 433 if (ans >= MOD) ans -= MOD; 434 balance += added; 435 } else { 436 // Close event 437 balance -= added; 438 } 439 } 440 441 in.close(); 442 System.out.println(ans); 443 } 444 445 public static void main(String[] args) throws IOException { 446 (new D_Java()).doIt(); 447 } 448 } 449 ``` 450 451 [1420E - Battle Lemmings](/contest/1420/problem/E "Codeforces Round 672 (Div. 2)") 452 453 **Hint 1** 454 455 Let's keep the number of zeroes between any pair consecutive ones instead of the original array of zeroes and ones. How will the swap operation look in this case. How to calculate the protection? 456 457 **Hint 2** 458 459 Suppose we have the initial array and the final array. Think of the number of operations you need to make the first one equal to the second one. 460 461 **Hint 3** 462 463 Join all your observations together and use DP. 464 465 **Solution** 466 467 Tutorial is loading... 468 469 **Code in C++ (gepardo)** 470 471 ``` 472 #include <cassert> 473 #include <climits> 474 #include <iostream> 475 #include <vector> 476 #include <numeric> 477 478 using namespace std; 479 480 template<typename T> 481 inline void umin(T &a, const T &b) { 482 a = min(a, b); 483 } 484 485 template<typename T> 486 inline void umax(T &a, const T &b) { 487 a = max(a, b); 488 } 489 490 int main() { 491 ios_base::sync_with_stdio(false); 492 493 int n; cin >> n; 494 vector<int> a(n); 495 for (int &x : a) { 496 cin >> x; 497 } 498 a.push_back(1); 499 500 vector<int> gg; 501 for (int i = 0; i <= n; ++i) { 502 int s = i; 503 while (a[i] == 0) ++i; 504 gg.push_back(i - s); 505 } 506 507 vector<int> p = gg; 508 partial_sum(begin(p), end(p), begin(p)); 509 510 constexpr int mx = 103; 511 constexpr int dx = mx + 1, dy = mx + 1, dz = mx * (mx + 1) / 2 + 1; 512 static int dp[dx][dy][dz] = {}; 513 514 for (int i = 0; i < dx; ++i) { 515 for (int j = 0; j < dy; ++j) { 516 for (int k = 0; k < dz; ++k) { 517 dp[i][j][k] = INT_MAX; 518 } 519 } 520 } 521 dp[0][0][0] = 0; 522 523 int k = gg.size(), l = p.back(); 524 for (int i = 0; i < k; ++i) { 525 for (int j = 0; j <= l; ++j) { 526 for (int s = 0; s <= n * (n-1) / 2; ++s) { 527 if (dp[i][j][s] == INT_MAX) continue; 528 for (int q = j; q <= l; ++q) { 529 umin(dp[i+1][q][s + abs(q - p[i])], dp[i][j][s] + (q-j)*(q-j)); 530 } 531 } 532 } 533 } 534 535 int mn = INT_MAX; 536 for (int s = 0; s <= n * (n-1) / 2; ++s) { 537 umin(mn, dp[k][l][s]); 538 int val = l*l - mn; 539 assert(val % 2 == 0); 540 cout << val/2 << " "; 541 } 542 cout << endl; 543 544 return 0; 545 } 546 ```