codeforces-scrape

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

390.md (15270B)


      1 Source: https://codeforces.com/blog/entry/64453
      2 
      3 *Since the original data has been lost during the dark days of Codeforces, no version of the editorial has been re-released, and I feel the round itself is quite educational, so I decided to give a try.*
      4 
      5 ## [390A - Inna and Alarm Clock](/contest/390/problem/A "Codeforces Round 229 (Div. 2)")
      6 
      7 **Approach**
      8 
      9 The criterion shows that we can only use either vertical segments or horizontal segments.  
     10 Since there is no limit on the segments' length, we can see that it's always optimal to use a segment with infinite length (or may be known as a line).
     11 
     12 We can see that the vertical line *x* = *a* will span through every alarm clocks standing at positions with x-coordinate being equal to *a*. In a similar manner, the horizontal line *y* = *b* will span through every alarm clocks standing at positions with y-coordinate being equal to *b*.
     13 
     14 So, if we use vertical lines, the number of segments used will be the number of distinct values of x-coordinates found in the data. Similarly, the number of horizontal segments used will be the number of distinct values of y-coordinates found.
     15 
     16 The process can be implemented by a counting array, or a map.
     17 
     18 Time complexity: ![](https://espresso.codeforces.com/e98e669660e295d23c96117b197140d3a3709707.png) for regular arrays, or ![](https://espresso.codeforces.com/df2dace9ef526732e09735cc52a919faad47f167.png) for maps.
     19 
     20 **Solution 1 (Map)**
     21 
     22 Submission link: [48214007](/contest/390/submission/48214007 "Submission 48214007 by AkiLotus")
     23 
     24 **Source code in plain text**
     25 
     26 ```
     27 #pragma GCC optimize("Ofast")
     28 
     29 #include <bits/stdc++.h>
     30 using namespace std;
     31 
     32 #define endl '\n'
     33 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
     34 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
     35 
     36 int main(int argc, char* argv[]) {
     37 	ios_base::sync_with_stdio(0); cin.tie(NULL);
     38 	
     39 	int n; cin >> n;
     40 	
     41 	map<int, int> cntx, cnty;
     42 	
     43 	while (n--) {
     44 		int x, y;
     45 		cin >> x >> y;
     46 		cntx[x]++; cnty[y]++;
     47 	}
     48 	
     49 	cout << min(cntx.size(), cnty.size()) << endl;
     50 	
     51 	return 0;
     52 }
     53 ```
     54 
     55 **Solution 2 (Array)**
     56 
     57 Submission link: [48213984](/contest/390/submission/48213984 "Submission 48213984 by AkiLotus")
     58 
     59 **Source code in plain text**
     60 
     61 ```
     62 #pragma GCC optimize("Ofast")
     63 
     64 #include <bits/stdc++.h>
     65 using namespace std;
     66 
     67 #define endl '\n'
     68 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
     69 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
     70 
     71 int main(int argc, char* argv[]) {
     72 	ios_base::sync_with_stdio(0); cin.tie(NULL);
     73 	
     74 	int n; cin >> n;
     75 	
     76 	vector<int> cntx(101, 0);
     77 	vector<int> cnty(101, 0);
     78 	
     79 	while (n--) {
     80 		int x, y;
     81 		cin >> x >> y;
     82 		cntx[x]++; cnty[y]++;
     83 	}
     84 	
     85 	int distinctx = 0, distincty = 0;
     86 	for (int i=0; i<101; i++) {
     87 	    distinctx += (cntx[i] > 0);
     88 	    distincty += (cnty[i] > 0);
     89 	}
     90 	
     91 	cout << min(distinctx, distincty) << endl;
     92 	
     93 	return 0;
     94 }
     95 ```
     96 
     97 ## [390B - Inna, Dima and Song](/contest/390/problem/B "Codeforces Round 229 (Div. 2)")
     98 
     99 **Approach**
    100 
    101 From the constraints given, for the *i*-th song, provided there exists corresponding *x**i* and *y**i* values, then the following inequality must hold: 2 ≤ *x**i* + *y**i* ≤ 2·*a**i*.  
    102 Thus, if any *b**i* is either lower than 2 or higher than 2·*a**i*, then no *x**i* and *y**i* can be found, thus, Sereja's joy will surely decrease by 1.
    103 
    104 Amongst all pairs of ![](https://espresso.codeforces.com/cb276cd4dc36f23b69b51abe41e17841282ed42c.png) that *x**i* + *y**i* = *b**i*, the pair with the highest value of *x**i*·*y**i* will be one with the equal value of *x**i* = *y**i* (this can be proven by the famous AM-GM inequality).  
    105 Thus, if *b**i* is divisible by 2, we can easily pick ![](https://espresso.codeforces.com/4ebbc716337dc5b987bc678f95685e3b6e874bfa.png).  
    106 Also, from this, we can see (either intuitively or with static proofs) that the lower the difference between *x**i* and *y**i* is, the higher the value *x**i*·*y**i* will be. Thus, in case *b**i* being odd, the most optimal pair will be ![](https://espresso.codeforces.com/4bc158af48fdad3d0dba7ead977ad08c6efd4343.png) or ![](https://espresso.codeforces.com/443272cf5829fac4b5f9b1d92d3319449b0a967a.png) (the order doesn't matter here).
    107 
    108 Time complexity: ![](https://espresso.codeforces.com/e50d121c611e249696d85ac98167ee3dfa4ba3f3.png).
    109 
    110 **Solution**
    111 
    112 Submission link: [48212208](/contest/390/submission/48212208 "Submission 48212208 by AkiLotus")
    113 
    114 **Source code in plain text**
    115 
    116 ```
    117 #pragma GCC optimize("Ofast")
    118 
    119 #include <bits/stdc++.h>
    120 using namespace std;
    121 
    122 #define endl '\n'
    123 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
    124 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
    125 
    126 int main(int argc, char* argv[]) {
    127 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    128 	
    129 	int n; cin >> n;
    130 	
    131 	vector<int> a(n), b(n);
    132 	for (auto &z: a) cin >> z;
    133 	for (auto &z: b) cin >> z;
    134 	
    135 	long long Joy = 0;
    136 	for (int i=0; i<n; i++) {
    137 		if (b[i] < 2 || b[i] > a[i] * 2) {Joy--; continue;}
    138 		int x = b[i] / 2, y = b[i] - x;
    139 		Joy += 1LL * x * y;
    140 	}
    141 	cout << Joy << endl;
    142 	
    143 	return 0;
    144 }
    145 ```
    146 
    147 ## [390C - Inna and Candy Boxes](/contest/390/problem/C "Codeforces Round 229 (Div. 2)")
    148 
    149 **Approach**
    150 
    151 The query content looks pretty confusing at first, to be honest.  
    152 Since *k* is static throughout a scenario, we can group the boxes into *k* groups, the *z*-th box (in this editorial let's assume that the indices of the boxes start from 0) falls into group number ![](https://espresso.codeforces.com/78bea9063020ea155fff32a481842014c32d98ba.png).
    153 
    154 Then, each query can be simplified as this: "Is that true that among the boxes with numbers from *l**i* to *r**i*, inclusive, the candies lie **only** in boxes of group ![](https://espresso.codeforces.com/d252f9b61b64c0b830c9c0c1c3cda0fca9d00085.png)?
    155 
    156 To make sure the answer for a query being "Yes", Dima has to remove candies from all candied-box in all groups other than ![](https://espresso.codeforces.com/d252f9b61b64c0b830c9c0c1c3cda0fca9d00085.png), while in that exact group, fill every empty box with a candy. Obviously, we'll consider boxes with indices between *l**i* and *r**i* inclusively only.
    157 
    158 We can make *k* lists, the *t*-th (0-indexed) list stores the indices of candied boxes in group *t*.
    159 
    160 We'll process with each query as the following:
    161 
    162 * Obviously, given from the criteria, each range will consist of exactly ![](https://espresso.codeforces.com/830bdc9804371cb3a60ae9359bb9fe58149ae26d.png) boxes per each group. Let's denote ![](https://espresso.codeforces.com/0220b561b0de8bb761315bed9f765526b1a82a12.png).
    163 * Traverse all groups, for the *t*-th group (again, 0-indexed), let's denote *x**t* as the number of candied boxes of group *t* in the given range. This value can be calculated quickly through binary searching the constructed lists above.
    164 * If group *t* is not the group being demanded to have candies (group ![](https://espresso.codeforces.com/d252f9b61b64c0b830c9c0c1c3cda0fca9d00085.png)), we'll need to perform *x**t* actions (removing candies). Otherwise, we'll need to perform *A* - *x**t* actions (adding candies to empty boxes).
    165 
    166 Time complexity: ![](https://espresso.codeforces.com/83fab29132fa3970fad25e1e222dfe177167bae6.png).
    167 
    168 **Solution**
    169 
    170 Submission link: [48213932](/contest/390/submission/48213932 "Submission 48213932 by AkiLotus")
    171 
    172 **Source code in plain text**
    173 
    174 ```
    175 #pragma GCC optimize("Ofast")
    176 
    177 #include <bits/stdc++.h>
    178 using namespace std;
    179 
    180 #define endl '\n'
    181 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
    182 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
    183 
    184 int main(int argc, char* argv[]) {
    185 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    186 	
    187 	int n, k, w; string s;
    188 	cin >> n >> k >> w >> s;
    189 	
    190 	vector< vector<int> > CandyGrp(k);
    191 	
    192 	for (int i=0; i<n; i++) {
    193 	    if (s[i] == '0') continue;
    194 	    CandyGrp[i % k].push_back(i);
    195 	}
    196 	
    197 	while (w--) {
    198 	    int l, r;
    199 		cin >> l >> r; l--; r--;
    200 		
    201 		int res = 0;
    202 		int demandedGroup = (l + k - 1) % k;
    203 		int BoxesPerGroup = (r - l + 1) / k;
    204 		
    205 		for (int id=0; id<k; id++) {
    206 		    
    207 			int x = lower_bound(CandyGrp[id].begin(), CandyGrp[id].end(), l) - CandyGrp[id].begin();
    208 			int y = upper_bound(CandyGrp[id].begin(), CandyGrp[id].end(), r) - CandyGrp[id].begin();
    209 			
    210 			if (id == demandedGroup) {
    211 			    res += (BoxesPerGroup - (y - x));
    212 			}
    213 			else res += (y - x);
    214 		}
    215 		
    216 		cout << res << endl;
    217 	}
    218 	
    219 	return 0;
    220 }
    221 ```
    222 
    223 ## [390D - Inna and Sweet Matrix](/contest/390/problem/D "Codeforces Round 229 (Div. 2)")
    224 
    225 **Approach**
    226 
    227 We can see that the most optimal placement will be choosing *k* cells being nearest to cell (1, 1) (yup, including (1, 1) itself).  
    228 To find these *k* points, we can simply do a BFS starting from (1, 1), with traceback feature to construct the paths to get to those cells.  
    229 However, keep in mind that any cell being candied will later on become obstacles for the following paths. Thus, to avoid blocking yourself, you should transfer candies to the farthest cells first, then getting closer. Thus, cell (1, 1) will be the last one being filled with candy.
    230 
    231 Time complexity: ![](https://espresso.codeforces.com/464cbb240e8ae8db0420805250b0ac00f29c8f7b.png) or ![](https://espresso.codeforces.com/be7d2fc31b8207bf6178bb14a23b362773fd4c75.png), based on implementation (I myself did ![](https://espresso.codeforces.com/be7d2fc31b8207bf6178bb14a23b362773fd4c75.png), since the difference isn't too much).
    232 
    233 **Solution**
    234 
    235 Submission link: [48213856](/contest/390/submission/48213856 "Submission 48213856 by AkiLotus")
    236 
    237 **Source code in plain text**
    238 
    239 ```
    240 #pragma GCC optimize("Ofast")
    241 
    242 #include <bits/stdc++.h>
    243 using namespace std;
    244 
    245 #define endl '\n'
    246 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
    247 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
    248 
    249 int dx[] = {-1, +0, +0, +1};
    250 int dy[] = {+0, -1, +1, +0};
    251 pair<int, int> Default = {-1, -1};
    252 
    253 int main(int argc, char* argv[]) {
    254 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    255 	
    256 	int n, m, k; cin >> n >> m >> k;
    257 	
    258 	vector<vector<int>> Dist(n+2, vector<int>(m+2, 4444));
    259 	vector<vector<pair<int, int>>> Last(n+2, vector<pair<int, int>>(m+2, Default));
    260     
    261 	stack<pair<int, int>> Cells;
    262 	int cost = 0;
    263 	
    264 	queue<pair<int, int>> Q;
    265 	Q.push({1, 1}); Dist[1][1] = 1;
    266 	
    267 	while (!Q.empty() && Cells.size() < k) {
    268 		pair<int, int> C = Q.front(); Q.pop();
    269 		Cells.push(C); int x = C.first, y = C.second;
    270 		
    271 		cost += Dist[x][y];
    272 		
    273 		for (int dir=0; dir<4; dir++) {
    274 			if (x + dx[dir] < 1 || x + dx[dir] > n) continue;
    275 			if (y + dy[dir] < 1 || y + dy[dir] > m) continue;
    276 			
    277 			if (Dist[x+dx[dir]][y+dy[dir]] != 4444) continue;
    278 			
    279 			Dist[x+dx[dir]][y+dy[dir]] = Dist[x][y] + 1;
    280 			Q.push({x + dx[dir], y + dy[dir]});
    281 			Last[x+dx[dir]][y+dy[dir]] = C;
    282 		}
    283 	}
    284 	
    285 	cout << cost << endl;
    286 	
    287 	while (!Cells.empty()) {
    288 		int x = Cells.top().first, y = Cells.top().second; Cells.pop();
    289 		stack<pair<int, int>> Traceback;
    290 		
    291 		while (x != -1 && y != -1) {
    292 			Traceback.push({x, y});
    293 			pair<int, int> NextCell = Last[x][y];
    294 			x = NextCell.first; y = NextCell.second;
    295 		}
    296 		
    297 		while (!Traceback.empty()) {
    298 			pair<int, int> CurCell = Traceback.top();
    299 			Traceback.pop();
    300 			cout << "(" << CurCell.first << ", " << CurCell.second << ") ";
    301 		}
    302 		cout << endl;
    303 	}
    304 	
    305 	return 0;
    306 }
    307 ```
    308 
    309 ## [390E - Inna and Large Sweet Matrix](/contest/390/problem/E "Codeforces Round 229 (Div. 2)")
    310 
    311 **Approach**
    312 
    313 Let's denote *A* as the total number of candies on the board, *R**i* as the total number of candies on the *i*-th row (1 ≤ *i* ≤ *n*), *C**j* as the total number of candies on the *j*-th column (1 ≤ *j* ≤ *m*).
    314 
    315 Also, let's denote ![](https://espresso.codeforces.com/b38d7b9a33912f8ddf2960acee5927b6bfd14cb9.png) and ![](https://espresso.codeforces.com/01d697cc3de45d71c1ae7efa08207ea0fbe4c73b.png).
    316 
    317 Let's considered the 2nd type of query first. Denoting the answer for the query as *f*(*x*1, *y*1, *x*2, *y*2), we can see that *f*(*x*1, *y*1, *x*2, *y*2) = *R*(*x*1, *x*2) + *C*(*y*1, *y*2) - *A* (you can draw a simple diagram and validate this function).
    318 
    319 Thus, the problem is now reduced to calculating *R*(*x*1, *x*2), *C*(*y*1, *y*2) and *A*:
    320 
    321 * *A* can be easily calculated. After each query of the 1st type with parameters *x*1, *y*1, *x*2, *y*2, *v*; *A* will be increased by *v*·(*x*2 - *x*1 + 1)·(*y*2 - *y*1 + 1).
    322 * The calculation of *R*(*x*1, *x*2) and *C*(*y*1, *y*2) makes us thinking about some kinds of data structures that support range sum update and range sum query. Segment trees and Fenwick trees can both work on that. Personally I used segment trees, they fit in just right for the memory limit (I implemented it by vectors, regular arrays will obviously be safer).
    323 
    324 Time complexity: ![](https://espresso.codeforces.com/88dba0191e24dada9126d8d5b164d4ade4f556d6.png).
    325 
    326 **Solution**
    327 
    328 Submission link: [48213830](/contest/390/submission/48213830 "Submission 48213830 by AkiLotus")
    329 
    330 **Source code in plain text**
    331 
    332 ```
    333 #pragma GCC optimize("Ofast")
    334 
    335 #include <bits/stdc++.h>
    336 using namespace std;
    337 
    338 #define endl '\n'
    339 mt19937 rng32(chrono::steady_clock::now().time_since_epoch().count());
    340 mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
    341 
    342 struct SegTree_Sum {
    343 	int n; vector<long long> Tree, Lazy;
    344 	SegTree_Sum() {}
    345 	SegTree_Sum(int _n) {
    346 		n = _n;
    347 		Tree.resize(n*4);
    348 		Lazy.resize(n*4);
    349 	}
    350 	
    351 	void Propagate(int node, int st, int en) {
    352 		if (Lazy[node] == 0) return;
    353 		Tree[node] += Lazy[node] * (en - st + 1);
    354 		if (st != en) {
    355 			Lazy[node*2+1] += Lazy[node];
    356 			Lazy[node*2+2] += Lazy[node];
    357 		}
    358 		Lazy[node] = 0;
    359 	}
    360 	
    361 	void Update(int node, int st, int en, int L, int R, long long val) {
    362 		Propagate(node, st, en);
    363 		if (en < st || R < st || en < L) return;
    364 		if (L <= st && en <= R) {
    365 			Lazy[node] += val;
    366 			Propagate(node, st, en); return;
    367 		}
    368 		Update(node*2+1, st, (st+en)/2+0, L, R, val);
    369 		Update(node*2+2, (st+en)/2+1, en, L, R, val);
    370 		Tree[node] = Tree[node*2+1] + Tree[node*2+2];
    371 	}
    372 	
    373 	long long Sum(int node, int st, int en, int L, int R) {
    374 		Propagate(node, st, en);
    375 		if (en < st || R < st || en < L) return 0LL;
    376 		if (L <= st && en <= R) return Tree[node];
    377 		long long p1 = Sum(node*2+1, st, (st+en)/2+0, L, R);
    378 		long long p2 = Sum(node*2+2, (st+en)/2+1, en, L, R);
    379 		return (p1 + p2);
    380 	}
    381 	
    382 	void RangeUpdate(int L, int R, long long val) {
    383 		Update(0, 0, n-1, L, R, val);
    384 	}
    385 	
    386 	long long RangeSum(int L, int R) {
    387 		return Sum(0, 0, n-1, L, R);
    388 	}
    389 };
    390 
    391 int main(int argc, char* argv[]) {
    392 	ios_base::sync_with_stdio(0); cin.tie(NULL);
    393 	
    394 	int n, m, w; cin >> n >> m >> w;
    395 	
    396 	long long TotalCandies = 0;
    397 	
    398 	SegTree_Sum TreeRow = SegTree_Sum(n);
    399 	SegTree_Sum TreeCol = SegTree_Sum(m);
    400 	
    401 	while (w--) {
    402 		int t, x1, y1, x2, y2;
    403 		cin >> t >> x1 >> y1 >> x2 >> y2;
    404 		
    405 		if (t == 0) {
    406 			int v; cin >> v;
    407 			
    408 			TotalCandies += 1LL * (x2 - x1 + 1) * (y2 - y1 + 1) * v;
    409 			
    410 			TreeRow.RangeUpdate(x1, x2, 1LL * v * (y2 - y1 + 1));
    411 			TreeCol.RangeUpdate(y1, y2, 1LL * v * (x2 - x1 + 1));
    412 		}
    413 		else if (t == 1) {
    414 			long long res = 0;
    415 			
    416 			res += TreeRow.RangeSum(x1, x2);
    417 			res += TreeCol.RangeSum(y1, y2);
    418 			res -= TotalCandies;
    419 			
    420 			cout << res << endl;
    421 		}
    422 	}
    423 	
    424 	return 0;
    425 }
    426 ```