codeforces-scrape

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

660.md (16585B)


      1 Source: https://codeforces.com/blog/entry/44259
      2 
      3 ### [660A - Co-prime Array](/contest/660/problem/A "Educational Codeforces Round 11")
      4 
      5 The problem was suggested by Ali Ibrahim [C137](/profile/C137 "Specialist C137").
      6 
      7 Note that we should insert some number between any adjacent not co-prime elements. On other hand we always can insert the number 1.
      8 
      9 **С++ solution**
     10 
     11 ```
     12 const int N = 1010;
     13 
     14 int n, a[N];
     15 
     16 bool read() {
     17 	if (!(cin >> n)) return false;
     18 	forn(i, n) assert(scanf("%d", &a[i]) == 1);
     19 	return true;
     20 }
     21 
     22 void solve() {
     23 	function<int(int, int)> gcd = [&](int a, int b) { return !a ? b : gcd(b % a, a); };
     24 
     25 	vector<int> ans;
     26 	forn(i, n) {
     27 		ans.pb(a[i]);
     28 		if (i + 1 < n && gcd(a[i], a[i + 1]) > 1)
     29 			ans.pb(1);
     30 	}
     31 
     32 	cout << sz(ans) - n << endl;
     33 	forn(i, sz(ans)) {
     34 		if (i) putchar(' ');
     35 		printf("%d", ans[i]);
     36 	}
     37 	puts("");
     38 }
     39 ```
     40 
     41 Complexity: *O*(*nlogn*).
     42 
     43 ### [660B - Seating On Bus](/contest/660/problem/B "Educational Codeforces Round 11")
     44 
     45 The problem was suggested by Srikanth Bhat [bharsi](/profile/bharsi "Expert bharsi").
     46 
     47 In this problem you should simply do what was written in the problem statement. There are no tricks.
     48 
     49 **C++ solution**
     50 
     51 ```
     52 int n, m;
     53 
     54 bool read() {
     55 	return !!(cin >> n >> m);
     56 }
     57 
     58 const int N = 111;
     59 
     60 int a[N][4];
     61 
     62 void solve() {
     63 	forn(i, n) {
     64 		a[i][0] = 2 * i;
     65 		a[i][1] = 2 * (n + i);
     66 		a[i][2] = 2 * (n + i) + 1;
     67 		a[i][3] = 2 * i + 1;
     68 	}
     69 
     70 	vector<int> ans;
     71 	forn(i, n) {
     72 		ans.pb(a[i][1]);
     73 		ans.pb(a[i][0]);
     74 		ans.pb(a[i][2]);
     75 		ans.pb(a[i][3]);
     76 	}
     77 
     78 	nfor(i, sz(ans)) // inverse order
     79 		if (ans[i] >= m)
     80 			ans.erase(ans.begin() + i);
     81 
     82 	forn(i, m) {
     83 		if (i) putchar(' ');
     84 		printf("%d", ans[i] + 1);
     85 	}
     86 	puts("");
     87 }
     88 ```
     89 
     90 Complexity: *O*(*n*).
     91 
     92 ### [660C - Hard Process](/contest/660/problem/C "Educational Codeforces Round 11")
     93 
     94 The problem was suggested by Mohammad Amin Raeisi [Smaug](/profile/Smaug "Newbie Smaug").
     95 
     96 Let's call the segment [*l*, *r*] good if it contains no more than *k* zeroes. Note if segment [*l*, *r*] is good than the segment [*l* + 1, *r*] is also good. So we can use the method of two pointers: the first pointer is *l* and the second is *r*. Let's iterate over *l* from the left to the right and move *r* while we can (to do that we should simply maintain the number of zeroes in the current segment).
     97 
     98 **C++ solution**
     99 
    100 ```
    101 const int N = 1200300;
    102 
    103 int n, k;
    104 int a[N];
    105 
    106 bool read() {
    107 	if (!(cin >> n >> k)) return false;
    108 	forn(i, n) assert(scanf("%d", &a[i]) == 1);
    109 	return true;
    110 }
    111 
    112 void solve() {
    113 	int ansl = 0, ansr = 0;
    114 	int j = 0, cnt = 0;
    115 	forn(i, n) {
    116 		if (j < i) {
    117 			j = i;
    118 			cnt = 0;
    119 		}
    120 
    121 		while (j < n) {
    122 			int ncnt = cnt + !a[j];
    123 			if (ncnt > k) break;
    124 			cnt += !a[j];
    125 			j++;
    126 		}
    127 		
    128 		if (j - i > ansr - ansl)
    129 			ansl = i, ansr = j;
    130 
    131 		if (cnt > 0) cnt -= !a[i];
    132 	}
    133 
    134 	cout << ansr - ansl << endl;
    135 	fore(i, ansl, ansr) a[i] = 1;
    136 	forn(i, n) {
    137 		if (i) putchar(' ');
    138 		printf("%d", a[i]);
    139 	}
    140 	puts("");
    141 }
    142 ```
    143 
    144 Complexity: *O*(*n*).
    145 
    146 ### [660D - Number of Parallelograms](/contest/660/problem/D "Educational Codeforces Round 11")
    147 
    148 The problem was suggested by Sadegh Mahdavi [smahdavi4](/profile/smahdavi4 "Expert smahdavi4").
    149 
    150 It's known that the diagonals of a parallelogram split each other in the middle. Let's iterate over the pairs of points *a*, *b* and consider the middle of the segment ![](https://espresso.codeforces.com/b8e11f7b6d29f4f24aa59c1251b1d40f1255f46d.png): ![](https://espresso.codeforces.com/9d55934b83c2644f988823788da4d774736c9ca9.png). Let's calculate the value *cnt**c* for each middle. *cnt**c* is the number of segments *a*, *b* with the middle *c*. Easy to see that the answer is ![](https://espresso.codeforces.com/5c77b1ab213b3c36ca81fb9547202b5b1ebb7b9b.png).
    151 
    152 **C++ solution**
    153 
    154 ```
    155 const int N = 2020;
    156 
    157 int n;
    158 int x[N], y[N];
    159 
    160 bool read() {
    161 	if (!(cin >> n)) return false;
    162 	forn(i, n)
    163 		assert(scanf("%d%d", &x[i], &y[i]) == 2);
    164 	return true;
    165 }
    166 
    167 inline li C2(li n) { return n * (n - 1) / 2; }
    168 
    169 void solve() {
    170 	map<pti, int> cnt;
    171 
    172 	forn(i, n)
    173 		forn(j, i) {
    174 			int cx = x[i] + x[j];
    175 			int cy = y[i] + y[j];
    176 			cnt[{cx, cy}]++;
    177 		}
    178 
    179 	li ans = 0;
    180 	for (const auto& p : cnt)
    181 		ans += C2(p.y);
    182 	cout << ans << endl;
    183 }
    184 ```
    185 
    186 Complexity: *O*(*n*2*logn*).
    187 
    188 ### [660E - Different Subsets For All Tuples](/contest/660/problem/E "Educational Codeforces Round 11")
    189 
    190 The problem was suggested by Lewin Gan [Lewin](/profile/Lewin "International Master Lewin").
    191 
    192 Let's consider some subsequence with the length *k* > 0 (the empty subsequences we will count separately by adding the valye *m**n* at the end) and count the number of sequences that contains it. We should do that accurately to not count the same sequence multiple times. Let *x*1, *x*2, ..., *x**k* be the fixed subsequence. In the original sequence before the element *x*1 can be some other elements, but none of them can be equal to *x*1 (because we want to count the subsequence exactly one time). So we have *m* - 1 variants for each of the elements before *x*1. Similarly between elements *x*1 and *x*2 can be other elements and we have *m* - 1 choices for each of them. And so on. After the element *x**k* can be some elements (suppose there are *j* such elements) with no additional constraints (so we have *m* choices for each of them). We fixed the number of elements at the end *j*, so we should distribute *n* - *k* - *j* numbers between numbers before *x*1, between *x*1 and *x*2, \ldots, between *x**k* - 1 and *x**k*. Easy to see that we have ![](https://espresso.codeforces.com/01756fb3e393e01cf08877a829bcbe00e67c011b.png) choices to do that (it's simply binomial coefficient with allowed repititions). The number of sequences *x*1, *x*2, ..., *x**k* equals to *m**k*. So the answer is ![](https://espresso.codeforces.com/4b55e4cf4a7d74cf7bea9b02e02d949129e251d7.png). Easy to transform the last sum to the sum ![](https://espresso.codeforces.com/06d571e1c1538431ad79e4defb259dd48f819474.png). Note the last inner sum can be calculating using the formula for parallel summing: ![](https://espresso.codeforces.com/287cdf0de8944a322bb656266d8df247cc4e55b8.png). So the answer equals to ![](https://espresso.codeforces.com/7fa7a7b8b86a7e0831e3cdd950a0b44e1f7cf5c2.png). Also we can get the closed formula for the last sum to get logarithmic solution, but it is not required in the problem.
    193 
    194 **C++ solution**
    195 
    196 ```
    197 int n, m;
    198 
    199 bool read() {
    200 	return !!(cin >> n >> m);
    201 }
    202 
    203 const int N = 1200300;
    204 
    205 const int mod = 1000 * 1000 * 1000 + 7;
    206 
    207 int gcd(int a, int b, int& x, int& y) {
    208 	if (!a) {
    209 		x = 0, y = 1;
    210 		return b;
    211 	}
    212 	int xx, yy, g = gcd(b % a, a, xx, yy);
    213 	x = yy - b / a * xx;
    214 	y = xx;
    215 	return g;
    216 }
    217 
    218 inline int inv(int a) {
    219 	int x, y;
    220 	assert(gcd(a, mod, x, y) == 1);
    221 	x %= mod;
    222 	return x < 0 ? x + mod : x;
    223 }
    224 
    225 inline int mul(int a, int b) { return int(a * 1ll * b % mod); }
    226 inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
    227 inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
    228 
    229 inline void inc(int& a, int b) { a = add(a, b); }
    230 
    231 int fact[N], ifact[N];
    232 
    233 inline int C(int n, int k) {
    234 	if (k < 0 || k > n) return 0;
    235 	return mul(fact[n], mul(ifact[k], ifact[n - k]));
    236 }
    237 
    238 int pm[N], pm1[N];
    239 
    240 void solve() {
    241 	const int N = n + 1;
    242 
    243 	fact[0] = 1; fore(i, 1, N) fact[i] = mul(fact[i - 1], i);
    244 	forn(i, N) ifact[i] = inv(fact[i]);
    245 
    246 	pm[0] = 1; fore(i, 1, N) pm[i] = mul(pm[i - 1], m);
    247 	pm1[0] = 1; fore(i, 1, N) pm1[i] = mul(pm1[i - 1], sub(m, 1));
    248 
    249 	int ans = pm[n];
    250 	fore(s, 1, n + 1) {
    251 		int cur = 1;
    252 		cur = mul(cur, pm[s]);
    253 		cur = mul(cur, pm1[n - s]);
    254 		cur = mul(cur, C(n, s - 1));
    255 		inc(ans, cur);
    256 	}
    257 	cout << ans << endl;
    258 }
    259 ```
    260 
    261 Complexity: *O*((*n* + *m*)*log* *MOD*), где *MOD* = 109 + 7.
    262 
    263 ### [660F - Bear and Bowling 4](/contest/660/problem/F "Educational Codeforces Round 11")
    264 
    265 The problem was prepared by Kamil Debowski [Errichto](/profile/Errichto "International Grandmaster Errichto"). The problem analysis is also prepared by him.
    266 
    267 The key is to use divide and conquer. We need a recursive function `f(left, right)` that runs `f(left, mid)` and `f(mid+1, right)` (where *mid* = (*left* + *right*) / 2) and also considers all intervals going through *mid*. We will eventually need a convex hull of lines (linear functions) and let's see how to achieve it.
    268 
    269 For variables *L*, *R* (![](https://espresso.codeforces.com/1d78f44ba5768a4df8edf7e4b59c265f8a87389c.png), ![](https://espresso.codeforces.com/cd2fb7090e51225360a36da986ca18efb1d61ee8.png)) we will try to write the score of interval [*L*, *R*] as a linear function. It would be good to get something close to *a**L*·*x**R* + *b**L* where *a**L* and *b**L* depend on *L*, and *x**R* depends on *R* only.
    270 
    271 ![](https://espresso.codeforces.com/4ec86b3a840ed7af817682e2b51b493f7db78b4f.png)
    272 
    273 For each *L* we should find a linear function *f**L*(*x*) = *a**L*·*x* + *b**L* where *a**L*, *b**L* should fit the equation ( * ):
    274 
    275 ![](https://espresso.codeforces.com/a66bb453b128c5c77f02b6c4f417d36c0eca1c93.png)
    276 
    277 Now we have a set of linear functions representing all possible left endpoints *L*. For each right endpoint *R* we should find *x**R* and *const**R* to fit equation ( * ) again. With value of *x**R* we can iterate over functions *f**L* to find the one maximizing value of *b**L* + *a**L*·*x**R*. And (still for fixed *R*) we should add *const**R* to get the maximum possible score of interval ending in *R*.
    278 
    279 **Brute Force with functions**
    280 
    281 ```
    282 #include<bits/stdc++.h>
    283 using namespace std;
    284 typedef long long ll;
    285 const int nax = 1e6 + 5;
    286 ll ans;
    287 ll t[nax];
    288 
    289 struct Fun {
    290 	ll a, b;
    291 	ll getValue(ll x) { return a * x + b; }
    292 };
    293 
    294 void rec(int first, int last) {
    295 	if(first == last) {
    296 		ans = max(ans, t[first]);
    297 		return;
    298 	}
    299 	int mid = (first + last) / 2;
    300 	
    301 	rec(first, mid); // the left half is [first, mid]
    302 	rec(mid+1, last); // the right half is [mid+1, last]
    303 	
    304 	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
    305 	
    306 	vector<Fun> functions;
    307 	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
    308 	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
    309 	for(int i = mid; i >= first; --i) {
    310 		sum_so_far += t[i];
    311 		score_so_far += sum_so_far;
    312 		functions.push_back(Fun{mid - i + 1, score_so_far});
    313 	}
    314 	
    315 	sum_so_far = 0;
    316 	score_so_far = 0;
    317 	for(int i = mid+1; i <= last; ++i) {
    318 		sum_so_far += t[i];
    319 		score_so_far += t[i] * (i - mid);
    320 		for(Fun & f : functions) {
    321 			ll score = score_so_far + f.getValue(sum_so_far);
    322 			ans = max(ans, score);
    323 		}
    324 	}
    325 }
    326 
    327 int main() {
    328 	int n;
    329 	scanf("%d", &n);
    330 	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
    331 	rec(1, n);
    332 	printf("%lldn", ans);
    333 	return 0;
    334 }
    335 ```
    336 
    337 Now let's make it faster. After finding a set of linear functions *f**L* we should build a convex hull of them (note that they're already sorted by slope). To achieve it we need something to compare 3 functions and decide whether one of them is unnecessary because it's always below one of other two functions. Note that in standard convex hull of points you also need something similar (but for 3 points). Below you can find an almost-fast-enough solution with a useful function `bool is_middle_needed(f1, f2, f3)`. You may check that numbers calculated there do fit in `long long`.
    338 
    339 **Almost fast enough**
    340 
    341 ```
    342 #include<bits/stdc++.h>
    343 using namespace std;
    344 typedef long long ll;
    345 const int nax = 1e6 + 5;
    346 ll ans;
    347 ll t[nax];
    348 
    349 struct Fun {
    350 	ll a, b;
    351 	ll getValue(ll x) { return a * x + b; }
    352 };
    353 
    354 bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
    355 	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
    356 	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
    357 	
    358 	// where is the intersection of f1 and f2?
    359 	// f1.a * x + f1.b = f2.a * x + f2.b
    360 	// x * (f2.a - f1.a) = f1.b - f2.b
    361 	// x = (f1.b - f2.b) / (f2.a - f1.a)
    362 	ll p1 = f1.b - f2.b;
    363 	ll q1 = f2.a - f1.a;
    364 	// and the intersection of f1 and f3
    365 	ll p2 = f1.b - f3.b;
    366 	ll q2 = f3.a - f1.a;
    367 	assert(q1 > 0 && q2 > 0);
    368 	// return p1 / q1 < p2 / q2
    369 	return p1 * q2 < q1 * p2;
    370 }
    371 
    372 void rec(int first, int last) {
    373 	if(first == last) {
    374 		ans = max(ans, t[first]);
    375 		return;
    376 	}
    377 	int mid = (first + last) / 2;
    378 	
    379 	rec(first, mid); // the left half is [first, mid]
    380 	rec(mid+1, last); // the right half is [mid+1, last]
    381 	
    382 	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
    383 	
    384 	vector<Fun> functions;
    385 	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
    386 	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
    387 	for(int i = mid; i >= first; --i) {
    388 		sum_so_far += t[i];
    389 		score_so_far += sum_so_far;
    390 		Fun f = Fun{mid - i + 1, score_so_far};
    391 		while(true) {
    392 			int s = functions.size();
    393 			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
    394 				functions.pop_back();
    395 			else
    396 				break;
    397 		}
    398 		functions.push_back(f);
    399 	}
    400 	
    401 	sum_so_far = 0;
    402 	score_so_far = 0;
    403 	for(int i = mid+1; i <= last; ++i) {
    404 		sum_so_far += t[i];
    405 		score_so_far += t[i] * (i - mid);
    406 		for(Fun & f : functions) {
    407 			ll score = score_so_far + f.getValue(sum_so_far);
    408 			ans = max(ans, score);
    409 		}
    410 	}
    411 }
    412 
    413 int main() {
    414 	int n;
    415 	scanf("%d", &n);
    416 	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
    417 	rec(1, n);
    418 	printf("%lldn", ans);
    419 	return 0;
    420 }
    421 ```
    422 
    423 Finally, one last thing is needed to make it faster than *O*(*n*2). We should use the fact that we have built a convex hull of functions (lines). For each *R* you should binary search optimal function. Alternatively, you can sort pairs (*x**R*, *const**R*) and then use the two pointers method — check the implementation in my solution below. It gives complexity ![](https://espresso.codeforces.com/cdf9a62d7c773804cca40da3bf2427fc504eb3e7.png) because we sort by *x**R* inside of a recursive function. I think it's possible to get rid of this by sorting prefixes ![](https://espresso.codeforces.com/2d534cfbdbee8ea500c195993d353d632f8d324f.png) in advance because it's equivalent to sorting by *x**R*. And we should use the already known order when we run a recursive function for smaller intervals. So, I think ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png) is possible this way — anybody implemented it?
    424 
    425 **Intended solution with two pointers**
    426 
    427 ```
    428 // O(n log^2(n))
    429 #include<bits/stdc++.h>
    430 using namespace std;
    431 typedef long long ll;
    432 const int nax = 1e6 + 5;
    433 ll ans;
    434 ll t[nax];
    435 
    436 struct Fun {
    437 	ll a, b;
    438 	ll getValue(ll x) { return a * x + b; }
    439 };
    440 
    441 bool is_middle_needed(const Fun & f1, const Fun & f2, const Fun & f3) {
    442 	// we ask if for at least one 'x' there is f2(x) > max(f1(x), f3(x))
    443 	assert(0 < f1.a && f1.a < f2.a && f2.a < f3.a);
    444 	
    445 	// where is the intersection of f1 and f2?
    446 	// f1.a * x + f1.b = f2.a * x + f2.b
    447 	// x * (f2.a - f1.a) = f1.b - f2.b
    448 	// x = (f1.b - f2.b) / (f2.a - f1.a)
    449 	ll p1 = f1.b - f2.b;
    450 	ll q1 = f2.a - f1.a;
    451 	// and the intersection of f1 and f3
    452 	ll p2 = f1.b - f3.b;
    453 	ll q2 = f3.a - f1.a;
    454 	assert(q1 > 0 && q2 > 0);
    455 	// return p1 / q1 < p2 / q2
    456 	return p1 * q2 < q1 * p2;
    457 }
    458 
    459 void rec(int first, int last) {
    460 	if(first == last) {
    461 		ans = max(ans, t[first]);
    462 		return;
    463 	}
    464 	int mid = (first + last) / 2;
    465 	
    466 	rec(first, mid); // the left half is [first, mid]
    467 	rec(mid+1, last); // the right half is [mid+1, last]
    468 	
    469 	// we must consider all intervals starting in [first,mid] and ending in [mid+1, last]
    470 	
    471 	vector<Fun> functions;
    472 	ll sum_so_far = 0; // t[i]+t[i+1]+...+t[mid]
    473 	ll score_so_far = 0; // t[i]*1 + t[i+1]*2 + ... + t[mid]*(mid-i+1)
    474 	for(int i = mid; i >= first; --i) {
    475 		sum_so_far += t[i];
    476 		score_so_far += sum_so_far;
    477 		Fun f = Fun{mid - i + 1, score_so_far};
    478 		while(true) {
    479 			int s = functions.size();
    480 			if(s >= 2 && !is_middle_needed(functions[s-2], functions[s-1], f))
    481 				functions.pop_back();
    482 			else
    483 				break;
    484 		}
    485 		functions.push_back(f);
    486 	}
    487 	
    488 	vector<pair<ll, ll>> points;
    489 	sum_so_far = 0;
    490 	score_so_far = 0;
    491 	for(int i = mid+1; i <= last; ++i) {
    492 		sum_so_far += t[i];
    493 		score_so_far += t[i] * (i - mid);
    494 		points.push_back({sum_so_far, score_so_far});
    495 		/*for(Fun & f : functions) {
    496 			ll score = score_so_far + f.getValue(sum_so_far);
    497 			ans = max(ans, score);
    498 		}*/
    499 	}
    500 	
    501 	sort(points.begin(), points.end());
    502 	int i = 0; // which function is the best
    503 	for(pair<ll, ll> p : points) {
    504 		sum_so_far = p.first;
    505 		score_so_far = p.second;
    506 		while(i + 1 < (int) functions.size()
    507 			&& functions[i].getValue(sum_so_far) <= functions[i+1].getValue(sum_so_far))
    508 				++i;
    509 		ans = max(ans, score_so_far + functions[i].getValue(sum_so_far));
    510 	}
    511 }
    512 
    513 int main() {
    514 	int n;
    515 	scanf("%d", &n);
    516 	for(int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
    517 	rec(1, n);
    518 	printf("%lldn", ans);
    519 	return 0;
    520 }
    521 ```
    522 
    523 Complexity: *O*(*nlog*2*n*).