codeforces-scrape

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

1982.md (9566B)


      1 Source: https://codeforces.com/blog/entry/130839
      2 
      3 Thank you for participating! I hope you enjoyed the tasks.
      4 
      5 One of the testers ([redpanda](/profile/redpanda "Expert redpanda")) did a wonderful [video analysis](https://youtu.be/-btzjr-u4dM) tasks A-C, I highly recommend watching it.
      6 
      7 [1982A - Soccer](/contest/1982/problem/A "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
      8 
      9 **Tutorial**
     10 
     11 Tutorial is loading...
     12 
     13 **Solution (74TrAkToR)**
     14 
     15 ```
     16 t = int(input())
     17 for T in range(t):
     18 	la, lb = map(int, input().split())
     19 	ra, rb = map(int, input().split())
     20 	if la > lb:
     21 		la, lb, ra, rb = lb, la, rb, ra
     22 	if la < lb and rb < ra:
     23 		print("NO")
     24 	else:
     25 		print("YES")
     26 ```
     27 
     28 [1982B - Collatz Conjecture](/contest/1982/problem/B "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (FelixArg)**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38  
     39 using namespace std;
     40  
     41 void solve(){
     42 	long long x, y, k;
     43 	cin >> x >> y >> k;
     44 	while (k > 0 && x != 1) {
     45 		long long ost = (x / y + 1) * y - x;
     46                 ost = max(1ll, ost);
     47                 ost = min(ost, k);
     48                 x += ost;
     49 		while (x % y == 0) {
     50 			x /= y;
     51 		}
     52 		k -= ost;
     53 	}
     54 	cout << x + k % (y - 1) << '\n';
     55 }
     56  
     57 int main()
     58 {
     59 #ifdef FELIX
     60 	auto _clock_start = chrono::high_resolution_clock::now();
     61 #endif
     62 	ios_base::sync_with_stdio(false);
     63 	cin.tie(0);
     64 	cout.tie(0);
     65  
     66 	int tests = 1;
     67 	cin >> tests;
     68 	for (int test = 0; test < tests; test++){
     69 		solve();
     70 	}
     71  
     72 #ifdef FELIX
     73 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
     74 		chrono::high_resolution_clock::now()
     75 			- _clock_start).count() << "ms." << endl;
     76 #endif
     77 	return 0;
     78 }
     79 ```
     80 
     81 [1982C - Boring Day](/contest/1982/problem/C "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
     82 
     83 **Hint 1**
     84 
     85 All the numbers $a_{i}$ are positive, can it help somehow?
     86 
     87 **Hint 2**
     88 
     89 Try using dynamic programming.
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution 1 (FelixArg)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99  
    100 using namespace std;
    101  
    102 const int inf = 1000000007;
    103  
    104 void solve(){
    105 	int n, l, r;
    106 	cin >> n >> l >> r;
    107 	vector<int> a(n);
    108 	for (int i = 0; i < n; i++){
    109 		cin >> a[i];
    110 	}
    111  
    112 	vector<long long> pref(n + 1);
    113 	for (int i = 0; i < n; i++){
    114 		pref[i + 1] = pref[i] + a[i];
    115 	}
    116  
    117 	vector<int> dp(n + 1);
    118 	int s = 0;
    119 	int j = -1;
    120 	for (int i = 0; i < n; i++){
    121 		dp[i + 1] = max(dp[i + 1], dp[i]);
    122 		if (j < i){
    123 			j = i;
    124 			s = 0;
    125 		}
    126 		while(j < n && s < l){
    127 			s += a[j++];
    128 		}
    129 		if (s >= l && s <= r){
    130 			dp[j] = max(dp[j], dp[i] + 1);
    131 		}
    132 		s -= a[i];
    133 	}
    134  
    135 	cout << dp[n] << '\n';
    136 }
    137  
    138 int main()
    139 {
    140 #ifdef FELIX
    141 	auto _clock_start = chrono::high_resolution_clock::now();
    142 #endif
    143 	ios_base::sync_with_stdio(false);
    144 	cin.tie(0);
    145 	cout.tie(0);
    146 	int tests = 1;
    147 	cin >> tests;
    148 	for (int test = 0; test < tests; test++){
    149 		solve();
    150 	}
    151 #ifdef FELIX
    152 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    153 		chrono::high_resolution_clock::now()
    154 			- _clock_start).count() << "ms." << endl;
    155 #endif
    156 	return 0;
    157 }
    158 ```
    159 
    160 **Solution 2 (74TrAkToR)**
    161 
    162 ```
    163 t = int(input())
    164 for T in range(t):
    165 	n, l, r = map(int, input().split())
    166 	a = [int(x) for x in input().split()]
    167 	ans = 0
    168 	cur = 0
    169 	L, R = 0, 0
    170 	while L < n:
    171 		while R < n and cur < l:
    172 			cur += a[R]
    173 			R += 1
    174 		if l <= cur and cur <= r:
    175 			ans += 1
    176 			L = R
    177 			cur = 0
    178 		else:
    179 			cur -= a[L]
    180 			L += 1
    181 	print(ans)
    182 ```
    183 
    184 [1982D - Beauty of the mountains](/contest/1982/problem/D "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
    185 
    186 **Hint 1**
    187 
    188 How does the difference between heights change if we choose a specific submatrix?
    189 
    190 **Hint 2**
    191 
    192 It is worth reducing the problem to a mathematical construction. Maybe something from number theory can help?
    193 
    194 **Tutorial**
    195 
    196 Tutorial is loading...
    197 
    198 **Solution (FelixArg)**
    199 
    200 ```
    201 import math
    202  
    203 def solve():
    204     n, m, k = map(int, input().split())
    205     a = [[int(x) for x in input().split()] for j in range(n)]
    206     s = [input() for i in range(n)]
    207     pref = [[0 for i in range(m + 1)] for j in range(n + 1)]
    208     diff = 0
    209     for i in range(n):
    210         cur = 0
    211         for j in range(m):
    212             if s[i][j] == '1':
    213                 cur += 1
    214                 diff += a[i][j]
    215             else:
    216                 diff -= a[i][j]
    217             pref[i + 1][j + 1] = pref[i][j + 1] + cur
    218     if diff == 0:
    219         print("YES")
    220         return
    221     g = 0
    222     for i in range(n - k + 1):
    223         for j in range(m - k + 1):
    224             f = pref[i + k][j + k] - pref[i + k][j] - pref[i][j + k] + pref[i][j]
    225             f = abs(k * k - 2 * f)
    226             g = math.gcd(g, f)
    227     if g == 0 or diff % g != 0:
    228         print("NO")
    229     else:
    230         print("YES")
    231  
    232  
    233 if __name__ == "__main__":
    234     t = int(input())
    235     for _ in range(t):
    236         solve()
    237 ```
    238 
    239 [1982E - Number of k-good subarrays](/contest/1982/problem/E "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
    240 
    241 **Hint**
    242 
    243 Try using the divide-and-conquer approach.
    244 
    245 **Tutorial**
    246 
    247 Tutorial is loading...
    248 
    249 **Solution (FelixArg)**
    250 
    251 ```
    252 #include <bits/stdc++.h>
    253  
    254 using namespace std;
    255  
    256 const int MOD = 1000000007;
    257  
    258 map<pair<long long, int>, tuple<int, long long, long long>> mem;
    259  
    260 tuple<int, long long, long long> calc(long long n, int k){
    261 	if (k < 0){
    262 		return tuple{0, 0ll, 0ll};
    263 	}
    264 	if (n == 1){
    265 		return tuple{1, 1ll, 1ll};
    266 	}
    267 	int bit = 63 - __builtin_clzll(n);
    268 	long long mid = (1ll << bit);
    269 	if (mid == n){
    270 		mid >>= 1;
    271 		if (mem.count({n, k})){
    272 			return mem[{n, k}];
    273 		}
    274 	}
    275 	auto [f1, s1, e1] = calc(mid, k);
    276 	auto [f2, s2, e2] = calc(n - mid, k - 1);
    277  
    278 	int sub1 = (e1 % MOD) * ((e1 + 1) % MOD) % MOD * 500000004 % MOD;
    279 	f1 = (f1 * 1ll - sub1 + MOD) % MOD;
    280 	int sub2 = (s2 % MOD) * ((s2 + 1) % MOD) % MOD * 500000004 % MOD;
    281 	f2 = (f2 * 1ll - sub2 + MOD) % MOD;
    282  
    283 	long long p = (e1 + s2) % MOD;
    284 	int f_cur = (f1 * 1ll + f2 + (p * 1ll * ((p + 1) % MOD) % MOD * 500000004 % MOD)) % MOD;
    285 	long long s_cur = s1;
    286 	long long e_cur = e2;
    287 	if (s1 == e1 && s1 != 0){
    288 		s_cur = (s1 + s2);
    289 	}
    290 	if (s2 == e2 && s2 != 0){
    291 		e_cur = (e1 + e2);
    292 	}
    293 	if ((mid << 1) == n){
    294 		mem[{n, k}] = tuple{f_cur, s_cur, e_cur};
    295 	}
    296 	return tuple{f_cur, s_cur, e_cur};
    297 };
    298  
    299 void solve(){
    300 	long long n;
    301 	int k;
    302 	cin >> n >> k;
    303 	cout << get<0>(calc(n, k)) << '\n';
    304 }
    305  
    306 int main()
    307 {
    308 #ifdef FELIX
    309 	auto _clock_start = chrono::high_resolution_clock::now();
    310 #endif
    311 	ios_base::sync_with_stdio(false);
    312 	cin.tie(0);
    313 	cout.tie(0);
    314  
    315 	int tests = 1;
    316 	cin >> tests;
    317 	for (int test = 0; test < tests; test++){
    318 		solve();
    319 	}
    320  
    321 #ifdef FELIX
    322 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    323 		chrono::high_resolution_clock::now()
    324 			- _clock_start).count() << "ms." << endl;
    325 #endif
    326 	return 0;
    327 }
    328 ```
    329 
    330 [1982F - Sorting Problem Again](/contest/1982/problem/F "Codeforces Round 955 (Div. 2, with prizes from NEAR!)")
    331 
    332 **Hint**
    333 
    334 If you maintain a set of such indexes $i$ that $a_{i} \lt a_{i - 1}$, then can this help in any way?
    335 
    336 **Tutorial**
    337 
    338 Tutorial is loading...
    339 
    340 **Solution (FelixArg)**
    341 
    342 ```
    343 #include <bits/stdc++.h>
    344  
    345 using namespace std;
    346  
    347 const int inf = 1000000007;
    348  
    349 struct SegTree{
    350 	vector<int> mn, mx;
    351 	int n;
    352 	SegTree(int _n): n(_n){
    353 		mx.assign(2 * n, -inf);
    354 		mn.resize(2 * n, inf);
    355 	}
    356  
    357 	void upd(int pos, int val){
    358 		mx[pos + n] = val;
    359 		mn[pos + n] = val;
    360 		pos = (pos + n) >> 1;
    361 		for (;pos > 0; pos >>= 1){
    362 			mx[pos] = max(mx[pos << 1], mx[(pos << 1) | 1]);
    363 			mn[pos] = min(mn[pos << 1], mn[(pos << 1) | 1]);
    364 		}
    365 	}
    366  
    367 	pair<int,int> get(int l, int r){
    368 		pair<int,int> res = {-inf, inf};
    369 		l += n;
    370 		r += n + 1;
    371 		for (;l < r; l >>= 1, r >>= 1){
    372 			if (l & 1) {
    373 				res.first = max(res.first, mx[l]);
    374 				res.second = min(res.second, mn[l++]);
    375 			}
    376 			if (r & 1) {
    377 				res.first = max(res.first, mx[--r]);
    378 				res.second = min(res.second, mn[r]);
    379 			}			
    380 		}
    381 		return res;
    382 	}
    383 };
    384  
    385 void solve(){
    386 	int n;
    387 	cin >> n;
    388 	vector<int> a(n);
    389 	for (int i = 0; i < n; i++){
    390 		cin >> a[i];
    391 	}
    392  
    393 	SegTree tree(n);
    394 	set<int> st;
    395 	for (int i = 0; i < n; i++){
    396 		tree.upd(i, a[i]);
    397 		if (i > 0 && a[i] < a[i - 1]){
    398 			st.insert(i);
    399 		}
    400 	}
    401  
    402 	function<int(int, int)> find_pref = [&](int pos, int x){
    403 		if (pos < 0){
    404 			return 0;
    405 		}
    406 		int l = 0, r = pos;
    407 		while(l <= r){
    408 			int m = l + (r - l) / 2;
    409 			if (a[m] > x){
    410 				r = m - 1;
    411 			}
    412 			else{
    413 				l = m + 1;
    414 			}
    415 		}
    416 		return r + 1;
    417 	};
    418  
    419 	function<int(int, int)> find_suff = [&](int pos, int x){
    420 		if (pos >= n){
    421 			return n - 1;
    422 		}
    423 		int l = pos, r = n - 1;
    424 		while(l <= r){
    425 			int m = l + (r - l) / 2;
    426 			if (a[m] >= x){
    427 				r = m - 1;
    428 			}
    429 			else{
    430 				l = m + 1;
    431 			}
    432 		}
    433 		return r;
    434 	};
    435  
    436 	function<void()> query = [&](){
    437 		if (st.empty()){
    438 			cout << -1 << ' ' << -1 << '\n';
    439 			return;
    440 		}
    441 		int l = *st.begin() - 1;
    442 		int r = *(--st.end());
    443  
    444 		auto [mx, mn] = tree.get(l, r);
    445  
    446 		cout << find_pref(l - 1, mn) + 1 << ' ' << find_suff(r + 1, mx) + 1 << '\n';
    447 	};
    448  
    449 	query();
    450 	int q;
    451 	cin >> q;
    452 	for (int i = 0; i < q; i++){
    453 		int pos, val;
    454 		cin >> pos >> val;
    455 		pos--;
    456 		if (pos > 0 && a[pos] < a[pos - 1]){
    457 			st.erase(pos);
    458 		}
    459 		if (pos + 1 < n && a[pos + 1] < a[pos]){
    460 			st.erase(pos + 1);
    461 		}
    462 		a[pos] = val;
    463 		tree.upd(pos, val);
    464 		if (pos > 0 && a[pos] < a[pos - 1]){
    465 			st.insert(pos);
    466 		}
    467 		if (pos + 1 < n && a[pos + 1] < a[pos]){
    468 			st.insert(pos + 1);
    469 		}
    470 		query();
    471 	}
    472 }
    473  
    474 int main()
    475 {
    476 #ifdef FELIX
    477 	auto _clock_start = chrono::high_resolution_clock::now();
    478 #endif
    479 	ios_base::sync_with_stdio(false);
    480 	cin.tie(0);
    481 	cout.tie(0);
    482 	int tests = 1;
    483 	cin >> tests;
    484 	for (int test = 0; test < tests; test++){
    485 		solve();
    486 	}
    487 #ifdef FELIX
    488 	cerr << "Executed in " << chrono::duration_cast<chrono::milliseconds>(
    489 		chrono::high_resolution_clock::now()
    490 			- _clock_start).count() << "ms." << endl;
    491 #endif
    492 	return 0;
    493 }
    494 ```