codeforces-scrape

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

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 ```