codeforces-scrape

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

2075.md (8557B)


      1 Source: https://codeforces.com/blog/entry/140781
      2 
      3 [2075A - To Zero](/contest/2075/problem/A "Educational Codeforces Round 176 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (BledDest)**
     12 
     13 ```
     14 t = int(input())
     15 for i in range(t):
     16     n, k = map(int, input().split())
     17     ans = 0
     18     if n % 2 == 1:
     19         n -= k
     20         ans = 1
     21     k -= 1
     22     ans += (n + k - 1) // k
     23     print(ans)
     24 ```
     25 
     26 [2075B - Array Recoloring](/contest/2075/problem/B "Educational Codeforces Round 176 (Rated for Div. 2)")
     27 
     28 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     29 
     30 **Tutorial**
     31 
     32 Tutorial is loading...
     33 
     34 **Solution (Neon)**
     35 
     36 ```
     37 #include <bits/stdc++.h>
     38  
     39 using namespace std;
     40  
     41 int main() {
     42   int t;
     43   cin >> t;
     44   while (t--) {
     45     int n, k;
     46     cin >> n >> k;
     47     vector<int> a(n);
     48     for (auto &x : a) cin >> x;
     49     long long ans = 0;
     50     if (k > 1) {
     51       sort(a.begin(), a.end(), greater<int>());
     52       ans = accumulate(a.begin(), a.begin() + k + 1, 0LL);
     53     } else {
     54       int l = *max_element(a.begin(), a.end() - 1);
     55       int r = *max_element(a.begin() + 1, a.end());
     56       ans = max(l + a.back(), r + a[0]);
     57     }
     58     cout << ans << '\n';
     59   }
     60 }
     61 ```
     62 
     63 [2075C - Two Colors](/contest/2075/problem/C "Educational Codeforces Round 176 (Rated for Div. 2)")
     64 
     65 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm")
     66 
     67 **Tutorial**
     68 
     69 Tutorial is loading...
     70 
     71 **Solution (awoo)**
     72 
     73 ```
     74 from bisect import bisect_left
     75 
     76 for _ in range(int(input())):
     77     n, m = map(int, input().split())
     78     a = sorted(list(map(int, input().split())))
     79     ans = 0
     80     for k in range(1, n):
     81         x = m - bisect_left(a, k)
     82         y = m - bisect_left(a, n - k)
     83         ans += x * y - min(x, y)
     84     print(ans)
     85 ```
     86 
     87 [2075D - Equalization](/contest/2075/problem/D "Educational Codeforces Round 176 (Rated for Div. 2)")
     88 
     89 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     90 
     91 **Tutorial**
     92 
     93 Tutorial is loading...
     94 
     95 **Solution (Neon)**
     96 
     97 ```
     98 #include <bits/stdc++.h>
     99  
    100 using namespace std;
    101 
    102 using li = long long;
    103 
    104 const int B = 60;
    105 const li INF = 1e18;
    106 
    107 int main() {
    108   ios::sync_with_stdio(false); cin.tie(0);
    109   array<array<li, B>, B> dp;
    110   for (int i = 0; i < B; ++i) {
    111     for (int j = 0; j < B; ++j) {
    112       dp[i][j] = INF;
    113     }
    114   }
    115   dp[0][0] = 0;
    116   for (int x = 0; x < B; ++x) {
    117     for (int i = B - 1; i >= 0; --i) {
    118       for (int j = B - 1; j >= 0; --j) {
    119         if (dp[i][j] == INF) continue;
    120         if (i + x < B) dp[i + x][j] = min(dp[i + x][j], dp[i][j] + (1LL << x));
    121         if (j + x < B) dp[i][j + x] = min(dp[i][j + x], dp[i][j] + (1LL << x));
    122       }
    123     }
    124   }
    125   int t;
    126   cin >> t;
    127   while (t--) {
    128     li x, y;
    129     cin >> x >> y;
    130     li ans = INF;
    131     for (int i = 0; i < B; ++i) {
    132       for (int j = 0; j < B; ++j) {
    133         if ((x >> i) == (y >> j)) ans = min(ans, dp[i][j]);
    134       }
    135     }
    136     cout << ans << '\n';
    137   }
    138 }
    139 ```
    140 
    141 [2075E - XOR Matrix](/contest/2075/problem/E "Educational Codeforces Round 176 (Rated for Div. 2)")
    142 
    143 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    144 
    145 **Tutorial**
    146 
    147 Tutorial is loading...
    148 
    149 **Solution (BledDest)**
    150 
    151 ```
    152 #include <bits/stdc++.h>
    153  
    154 using namespace std;
    155  
    156 const int MOD = 998244353;
    157 const int K = 31;
    158  
    159 int add(int x, int y)
    160 {
    161     x += y;
    162     while(x >= MOD) x -= MOD;
    163     while(x < 0) x += MOD;
    164     return x;
    165 }
    166  
    167 int sub(int x, int y)
    168 {
    169     return add(x, -y);
    170 }
    171  
    172 int mul(int x, int y)
    173 {
    174     return (x * 1ll * y) % MOD;
    175 }
    176  
    177 int binpow(int x, int y)
    178 {
    179     int z = 1;
    180     while(y)
    181     {
    182         if(y & 1) z = mul(z, x);
    183         x = mul(x, x);
    184         y >>= 1;
    185     }
    186     return z;
    187 }
    188  
    189 int dp[K][2][2][2];
    190  
    191 int choose2(int n)
    192 {
    193     return mul(n, mul(sub(n, 1), binpow(2, MOD - 2)));
    194 }   
    195  
    196 void solve()
    197 {
    198     int n, m, A, B;
    199     cin >> n >> m >> A >> B;
    200  
    201     memset(dp, 0, sizeof dp);
    202     dp[0][0][0][0] = 1;
    203     for(int i = 0; i + 1 < K; i++)
    204         for(int f1 = 0; f1 <= 1; f1++)
    205             for(int f2 = 0; f2 <= 1; f2++)
    206                 for(int fx = 0; fx <= 1; fx++)
    207                 {
    208                     int d = dp[i][f1][f2][fx];
    209                     if(!d) continue;
    210                     int j = K - 2 - i;
    211                     int curA = (A >> j) & 1;
    212                     int curB = (B >> j) & 1;
    213                     for(int bit_a = 0; bit_a <= 1; bit_a++)
    214                         for(int bit_b = 0; bit_b <= 1; bit_b++)
    215                             for(int bit_x = 0; bit_x <= 1; bit_x++)
    216                             {
    217                                 if(f1 == 0 && bit_a == 1 && curA == 0) continue;
    218                                 if(f2 == 0 && bit_b == 1 && curB == 0) continue;
    219                                 if(fx == 0 && bit_x == 1 && (bit_a == 0 || bit_b == 0)) continue;
    220                                 int nf1 = max(f1, bit_a ^ curA);
    221                                 int nf2 = max(f2, bit_b ^ curB);
    222                                 int nfx = max(fx, bit_x);
    223                                 int& d2 = dp[i + 1][nf1][nf2][nfx];
    224                                 d2 = add(d2, d);
    225                             }
    226                 }
    227     int pairs_of_pairs = 0;
    228     for(int i = 0; i <= 1; i++)
    229         for(int j = 0; j <= 1; j++)
    230             pairs_of_pairs = add(pairs_of_pairs, dp[K - 1][i][j][1]);
    231  
    232     int comb_a = sub(binpow(2, n), 2);
    233     int comb_b = sub(binpow(2, m), 2);
    234  
    235     int ans = mul(pairs_of_pairs, mul(comb_a, comb_b));
    236     ans = add(ans, mul(add(A, 1), add(B, 1)));
    237     ans = add(ans, mul(add(A, 1), mul(comb_b, choose2(add(B, 1)))));
    238     ans = add(ans, mul(add(B, 1), mul(comb_a, choose2(add(A, 1)))));
    239     cout << ans << endl;
    240 }
    241  
    242 int main()
    243 {
    244     int t;
    245     cin >> t;
    246     for(int i = 0; i < t; i++) solve();    
    247 }
    248 ```
    249 
    250 [2075F - Beautiful Sequence Returns](/contest/2075/problem/F "Educational Codeforces Round 176 (Rated for Div. 2)")
    251 
    252 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    253 
    254 **Tutorial**
    255 
    256 Tutorial is loading...
    257 
    258 **Solution (adedalic)**
    259 
    260 ```
    261 #include<bits/stdc++.h>
    262  
    263 using namespace std;
    264  
    265 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    266 #define sz(a) int((a).size())
    267  
    268 typedef long long li;
    269 typedef pair<int, int> pt;
    270  
    271 const int INF = int(1e9);
    272 const li INF64 = li(1e18);
    273  
    274 vector<int> Tadd, Tmax;
    275  
    276 int getmax(int v) {
    277 	return Tmax[v] + Tadd[v];
    278 }
    279 void push(int v) {
    280 	Tadd[2 * v + 1] += Tadd[v];
    281 	Tadd[2 * v + 2] += Tadd[v];
    282 	Tadd[v] = 0;
    283 }
    284 void upd(int v) {
    285 	Tmax[v] = max(getmax(2 * v + 1), getmax(2 * v + 2));
    286 }
    287 void addVal(int v, int l, int r, int lf, int rg, int val) {
    288 	if (l == lf && r == rg) {
    289 		Tadd[v] += val;
    290 		return;
    291 	}
    292 	push(v);
    293 	int mid = (l + r) >> 1;
    294 	if (lf < mid)
    295 		addVal(2 * v + 1, l, mid, lf, min(mid, rg), val);
    296 	if (rg > mid)
    297 		addVal(2 * v + 2, mid, r, max(lf, mid), rg, val);
    298 	upd(v);
    299 }
    300  
    301 int n;
    302 vector<int> a;
    303  
    304 inline bool read() {
    305 	if(!(cin >> n))
    306 		return false;
    307 	a.resize(n);
    308 	fore (i, 0, n)
    309 		cin >> a[i];
    310 	return true;
    311 }
    312  
    313 inline void solve() {
    314 	vector<int> ask(n, 0);
    315 	int mx = -1;
    316 	for (int i = n - 1; i >= 0; i--) {
    317 		if (a[i] > mx) {
    318 			ask[i] = 1;
    319 			mx = a[i];
    320 		}
    321 	}
    322 	vector<int> left;
    323 	fore (i, 0, n) {
    324 		if (left.empty() || a[left.back()] > a[i])
    325 			left.push_back(i);
    326 	}
    327  
    328 	vector<pt> seg(n);
    329 	fore (i, 0, n) {
    330 		int lf = upper_bound(left.begin(), left.end(), i, [&left](int v, int i) {
    331 			return a[v] > a[i];
    332 		}) - left.begin();
    333 		int rg = lower_bound(left.begin(), left.end(), i) - left.begin();
    334 		seg[i] = {lf, rg};
    335 	}
    336  
    337 	Tadd.assign(4 * n, 0);
    338 	Tmax.assign(4 * n, 0);
    339  
    340 	vector<int> ordToAdd(n);
    341 	iota(ordToAdd.begin(), ordToAdd.end(), 0);
    342 	sort(ordToAdd.begin(), ordToAdd.end(), [](int i, int j) {
    343 		return a[i] < a[j];
    344 	});
    345  
    346 	auto addToSeg = [&left, &seg](int id, int val) {
    347 		auto [lf, rg] = seg[id];
    348 		if (lf < rg)
    349 			addVal(0, 0, sz(left), lf, rg, val);
    350 	};
    351  
    352 	int ans = 0;
    353 	int pos = 0;
    354 	vector<int> added(n, 0);
    355 	for (int i = n - 1; i >= 0; i--) {
    356 		while (pos < n && a[ordToAdd[pos]] < a[i]) {
    357 			if (ordToAdd[pos] <= i) {
    358 				addToSeg(ordToAdd[pos], 1);
    359 				added[ordToAdd[pos]] = 1;
    360 			}
    361 			pos++;
    362 		}
    363 		if (ask[i]) {
    364 			auto [lf, rg] = seg[i];
    365 			ans = max(ans, 1 + (lf < rg ? 1 + getmax(0) : 0));
    366 		}
    367 		if (added[i]) {
    368 			addToSeg(i, -1);
    369 			added[i] = 0;
    370 		}
    371 	}
    372 	cout << ans << endl;
    373 }
    374  
    375 int main() {
    376 #ifdef _DEBUG
    377 	freopen("input.txt", "r", stdin);
    378 	int tt = clock();
    379 #endif
    380 	ios_base::sync_with_stdio(false);
    381 	cin.tie(0), cout.tie(0);
    382 	cout << fixed << setprecision(15);
    383 	
    384 	int t; cin >> t;
    385 	while(t--) {
    386 		(read());
    387 		solve();
    388 		
    389 #ifdef _DEBUG
    390 		cerr << "TIME = " << clock() - tt << endl;
    391 		tt = clock();
    392 #endif
    393 	}
    394 	return 0;
    395 }
    396 ```