codeforces-scrape

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

1861.md (11864B)


      1 Source: https://codeforces.com/blog/entry/119964
      2 
      3 [1861A - Prime Deletion](/contest/1861/problem/A "Educational Codeforces Round 154 (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 #include<bits/stdc++.h>
     15  
     16 using namespace std;
     17  
     18 int main()
     19 {
     20 	int t;
     21 	cin >> t;
     22 	for(int i = 0; i < t; i++)
     23 	{
     24 		string s;
     25 		cin >> s;
     26 		if(s.find("1") < s.find("3"))
     27 			cout << 13;
     28 		else
     29 			cout << 31;
     30 		cout << endl;
     31 	}
     32 }
     33 ```
     34 
     35 [1861B - Two Binary Strings](/contest/1861/problem/B "Educational Codeforces Round 154 (Rated for Div. 2)")
     36 
     37 Idea: [Roms](/profile/Roms "Master Roms")
     38 
     39 **Tutorial**
     40 
     41 Tutorial is loading...
     42 
     43 **Solution (Roms)**
     44 
     45 ```
     46 #include <bits/stdc++.h>
     47  
     48 using namespace std;
     49  
     50 int main() {
     51     int t;
     52     cin >> t;
     53     for (int tc = 0; tc < t; ++tc) {
     54         string a, b;
     55         cin >> a >> b;
     56         bool ok = false;
     57         for (int i = 0; i + 1 < a.size(); ++i) {
     58             if (a[i] == b[i] && a[i] == '0' && a[i + 1] == b[i + 1] && a[i + 1] == '1') {
     59                 ok = true;
     60             }
     61         }
     62         
     63         if (ok) 
     64             puts("YES");
     65         else
     66             puts("NO");
     67     }
     68     return 0;
     69 }
     70 ```
     71 
     72 [1861C - Queries for the Array](/contest/1861/problem/C "Educational Codeforces Round 154 (Rated for Div. 2)")
     73 
     74 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     75 
     76 **Tutorial**
     77 
     78 Tutorial is loading...
     79 
     80 **Solution 1 (Roms)**
     81 
     82 ```
     83 #include <bits/stdc++.h>
     84  
     85 using namespace std;
     86  
     87 const int N = 200000;
     88  
     89 int main() {
     90     int t;
     91     cin >> t;
     92     for (int tc = 0; tc < t; ++tc) {
     93         string s;
     94         cin >> s;
     95         int maxSortedPref = 0;
     96         int minNotSortedPref = 0;
     97         int bal = 0;
     98         bool good = true;
     99         
    100         for (auto c : s) {
    101             if (c == '+') {
    102                 ++bal;
    103             } else if (c == '-') {
    104                 --bal;
    105                 maxSortedPref = min(maxSortedPref, bal);
    106                 if (bal < minNotSortedPref)
    107                     minNotSortedPref = 0;
    108             } else if (c == '1') {
    109                 maxSortedPref = max(maxSortedPref, bal);
    110             } else {
    111                 if (bal <= 1) {
    112                     good = false;
    113                     break;
    114                 }
    115                 if (minNotSortedPref == 0 || minNotSortedPref > bal)
    116                     minNotSortedPref = bal;
    117             }
    118             if(minNotSortedPref <= maxSortedPref && minNotSortedPref != 0) {
    119                 good = false;
    120                 break;
    121             }
    122         }
    123         
    124         if (good)
    125             puts("YES");
    126         else
    127             puts("NO");
    128     }
    129     return 0;
    130 }
    131 ```
    132 
    133 **Solution 2 (BledDest)**
    134 
    135 ```
    136 #include<bits/stdc++.h>
    137  
    138 using namespace std;
    139  
    140 vector<int> has0, has1;
    141 vector<vector<int>> g;
    142  
    143 bool ans;
    144  
    145 bool dfs(int x, int d)
    146 {
    147 	if(has0[x] && (has1[x] || d <= 1))
    148 		ans = false;
    149 	bool res = false;
    150 	for(auto y : g[x])
    151 		res |= dfs(y, d + 1);
    152 	if(has0[x] && res)
    153 		ans = false;
    154 	return res || has1[x];
    155 }
    156  
    157 void solve()
    158 {
    159 	ans = true;
    160 	has0.push_back(0);
    161 	has1.push_back(0);
    162 	g.push_back(vector<int>());
    163 	int ts = 1;
    164 	
    165 	string s;
    166 	cin >> s;
    167 	vector<int> st = {0};
    168 	for(auto x : s)
    169 	{
    170 		int cur = st.back();
    171 		if(x == '0')
    172 			has0[cur] = 1;
    173 		if(x == '1')
    174 			has1[cur] = 1;
    175 		if(x == '+')
    176 		{
    177 			g[cur].push_back(ts);
    178 			st.push_back(ts);
    179 			ts++;
    180 			has0.push_back(0);
    181 			has1.push_back(0);
    182 			g.push_back(vector<int>());
    183 		}
    184 		if(x == '-')
    185 			st.pop_back();
    186 	}
    187 	
    188 	dfs(0, 0);
    189 	cout << (ans ? "YES\n" : "NO\n");
    190 	
    191 	has0.clear();
    192 	has1.clear();
    193 	g.clear();
    194 }
    195  
    196 int main()
    197 {
    198 	ios_base::sync_with_stdio(0);
    199 	cin.tie(0);
    200 	int t;
    201 	cin >> t;
    202 	for(int i = 0; i < t; i++)
    203 		solve();
    204 }
    205 ```
    206 
    207 [1861D - Sorting By Multiplication](/contest/1861/problem/D "Educational Codeforces Round 154 (Rated for Div. 2)")
    208 
    209 Idea: [Roms](/profile/Roms "Master Roms")
    210 
    211 **Tutorial**
    212 
    213 Tutorial is loading...
    214 
    215 **Solution (Roms)**
    216 
    217 ```
    218 #include <bits/stdc++.h>
    219  
    220 using namespace std;
    221  
    222 const int N = 200 * 1000 + 5;
    223  
    224 int t;
    225 int n;
    226 int a[N];
    227  
    228 int main() {
    229     cin >> t;
    230     for (int tc = 0; tc < t; ++tc){
    231     	cin >> n;
    232     	for (int i = 0; i < n; ++i)
    233     	    cin >> a[i];
    234     	
    235     	int cnt = 0;
    236     	for (int i = 1; i < n; ++i)
    237     	    cnt += (a[i - 1] >= a[i]);
    238     	    
    239     	int res = n, cnt2 = 0;
    240         for (int i = 0; i <= n; ++i) {
    241             bool isMultipliedByNegative = (i > 0);
    242             res = min(res, isMultipliedByNegative + cnt + cnt2);
    243             
    244             if (i + 1 < n)
    245                 cnt -= (a[i] >= a[i + 1]);
    246             if (i > 0)
    247                 cnt2 += (a[i - 1] <= a[i]);
    248         }
    249         
    250         cout << res << endl;
    251     }
    252 }
    253 ```
    254 
    255 [1861E - Non-Intersecting Subpermutations](/contest/1861/problem/E "Educational Codeforces Round 154 (Rated for Div. 2)")
    256 
    257 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    258 
    259 **Tutorial**
    260 
    261 Tutorial is loading...
    262 
    263 **Solution (BledDest)**
    264 
    265 ```
    266 #include<bits/stdc++.h>
    267  
    268 using namespace std;
    269  
    270 const int MOD = 998244353;
    271  
    272 int add(int x, int y)
    273 {
    274 	x += y;
    275 	while(x >= MOD) x -= MOD;
    276 	while(x < 0) x += MOD;
    277 	return x;
    278 }
    279  
    280 int sub(int x, int y)
    281 {
    282 	return add(x, -y);
    283 }
    284  
    285 int mul(int x, int y)
    286 {
    287 	return (x * 1ll * y) % MOD;
    288 }
    289  
    290 int binpow(int x, int y)
    291 {
    292 	int z = 1;
    293 	while(y > 0)
    294 	{
    295 		if(y & 1) z = mul(z, x);
    296 		x = mul(x, x);
    297 		y /= 2;
    298 	}
    299 	return z;
    300 }
    301  
    302 int main()
    303 {
    304 	int n, k;
    305 	cin >> n >> k;
    306 	int ans = 0;
    307 	vector<vector<int>> dp(n + 1, vector<int>(k, 0));
    308 	dp[0][0] = 1;
    309 	for(int i = 0; i < n; i++)
    310 	{
    311 		int cur = 0;
    312 		for(int j = k - 1; j >= 1; j--)
    313 		{
    314 			cur = add(cur, dp[i][j]);
    315 			dp[i + 1][j] = cur;
    316 		}
    317 		for(int j = k - 1; j >= 0; j--)
    318 		{
    319 			int nxt = (j + 1) % k;
    320 			dp[i + 1][nxt] = add(dp[i + 1][nxt], mul(dp[i][j], k - j));
    321 		}
    322 		ans = add(ans, mul(dp[i + 1][0], binpow(k, n - (i + 1))));
    323 	}
    324 	cout << ans << endl;
    325 }
    326 ```
    327 
    328 [1861F - Four Suits](/contest/1861/problem/F "Educational Codeforces Round 154 (Rated for Div. 2)")
    329 
    330 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    331 
    332 **Tutorial**
    333 
    334 Tutorial is loading...
    335 
    336 **Solution (BledDest)**
    337 
    338 ```
    339 #include<bits/stdc++.h>
    340  
    341 using namespace std;
    342  
    343 const int K = 4;
    344 const int N = 2 * int(1e6) + 43;
    345  
    346 pair<long long, long long> operator+(const pair<long long, long long>& a, const pair<long long, long long>& b)
    347 {
    348 	return make_pair(a.first + b.first, a.second + b.second);
    349 }
    350  
    351 pair<long long, long long> operator-(const pair<long long, long long>& a, const pair<long long, long long>& b)
    352 {
    353 	return make_pair(a.first - b.first, a.second - b.second);
    354 }
    355  
    356 // prefix sums for an array of pairs
    357 vector<pair<long long, long long>> pref_sums(const vector<pair<long long, long long>>& a)
    358 {
    359 	int n = a.size();
    360 	vector<pair<long long, long long>> ans(n);
    361 	ans[0] = a[0];
    362 	for(int i = 1; i < n; i++)
    363 		ans[i] = ans[i - 1] + a[i];
    364 	return ans;
    365 }
    366  
    367 // for an array of pairs denoting linear functions, evaluate
    368 // them in the corresponding points
    369 vector<long long> eval(const vector<pair<long long, long long>>& a)
    370 {
    371 	int n = a.size();
    372 	vector<long long> ans(n);
    373 	for(int i = 0; i < n; i++)
    374 		ans[i] = a[i].first * i + a[i].second;
    375 	return ans;
    376 }
    377  
    378 void solve()
    379 {
    380 	int n;
    381 	scanf("%d", &n);
    382 	vector<vector<int>> a(n, vector<int>(K));
    383 	for(int i = 0; i < n; i++)
    384 		for(int j = 0; j < K; j++)
    385 			scanf("%d", &a[i][j]);
    386 	vector<int> b(K);
    387 	for(int i = 0; i < K; i++)
    388 		scanf("%d", &b[i]);
    389 	
    390 	int deck_size = 0;
    391 	for(int i = 0; i < K; i++)
    392 		deck_size += b[i];
    393 	
    394 	// calculate the remaining number of cards for each player
    395 	long long full = deck_size;
    396 	for(int i = 0; i < n; i++)
    397 		for(int j = 0; j < K; j++)
    398 			full += a[i][j];
    399 	vector<int> remain(n, full / n);
    400 	for(int i = 0; i < n; i++)
    401 		for(int j = 0; j < K; j++)
    402 			remain[i] -= a[i][j];
    403 	
    404 	// for every player, calculate the maximum number of cards
    405 	// they already have among all suits
    406 	// and store it in a multiset
    407 	vector<int> min_val(n);
    408 	for(int i = 0; i < n; i++)
    409 		min_val[i] = *max_element(a[i].begin(), a[i].end());
    410 	multiset<int> min_vals;
    411 	for(int i = 0; i < n; i++)
    412 		min_vals.insert(min_val[i]);
    413 	
    414 	// for every mask of suits and every player, calculate
    415 	// the number of cards in those suits they already have
    416 	vector<vector<int>> already_has(1 << K, vector<int>(n));
    417 	for(int mask = 0; mask < (1 << K); mask++)
    418 		for(int i = 0; i < n; i++)
    419 			for(int j = 0; j < K; j++)
    420 				if(mask & (1 << j))
    421 					already_has[mask][i] += a[i][j];
    422 	// for every mask of suits and every player, calculate the
    423 	// maximum value of x such that if that player can receive 
    424 	// no more than x cards in each suit, the vertex of that
    425 	// player should belong to T in the cut
    426 	vector<vector<int>> max_x(1 << K, vector<int>(n));
    427 	for(int mask = 0; mask < (1 << K); mask++)
    428 		for(int i = 0; i < n; i++)
    429 		{
    430 			int suits = __builtin_popcount(mask);
    431 			if (suits == 0) max_x[mask][i] = N - 2;
    432 			else
    433 			{
    434 				// incoming edges have capacity of
    435 				// x - a[i][j]
    436 				int incoming = -already_has[mask][i];
    437 				// outgoing edge has capacity of remain[i]
    438 				// find the maximum x such that
    439 				// suits * x + incoming < remains[i]
    440 				int x = (remain[i] - incoming) / suits;
    441 				x = min(x, N - 2);
    442 				max_x[mask][i] = x;
    443 			}
    444 		}
    445 	
    446 	// for every mask and for all players, calculate the sum of 
    447 	// values they add to the cut if they can have no more than
    448 	// x cards of each suit in the mask
    449 	vector<vector<long long>> add_to_cut(1 << K, vector<long long>(N));
    450 	for(int mask = 0; mask < (1 << K); mask++)
    451 	{
    452 		int suits = __builtin_popcount(mask);
    453 		vector<pair<long long, long long>> aux(N);
    454 		for(int i = 0; i < n; i++)
    455 		{
    456 			// for the i-th player, they add remains[i] to
    457 			// the minimum cut if x > max_x[mask][i]
    458 			// otherwise, they add
    459 			// suits * x - already_has[mask][i]
    460 			int incoming = -already_has[mask][i];
    461 			// add [suits * x - incoming] on segment [0, max_x]
    462 			int x = max_x[mask][i];
    463 			pair<long long, long long> f1 = {suits, incoming};
    464 			aux[0] = aux[0] + f1;
    465 			aux[x + 1] = aux[x + 1] - f1;
    466 			// add remain[i] on [max_x + 1, N)
    467 			pair<long long, long long> f2 = {0, remain[i]};
    468 			aux[x + 1] = aux[x + 1] + f2;
    469 			aux[N - 1] = aux[N - 1] - f2;
    470 		}
    471 		// sum up those functions and evaluate them
    472 		add_to_cut[mask] = eval(pref_sums(aux));
    473 	}
    474 	
    475 	// now we're ready to solve the problem!
    476 	vector<int> ans(n);
    477 	// iterate on the player we want to maximize
    478 	for(int i = 0; i < n; i++)
    479 	{
    480 		// iterate on the suits they will maximize
    481 		for(int j = 0; j < K; j++)
    482 		{
    483 			int d = min(remain[i], b[j]);
    484 			int max_cards = a[i][j] + d;
    485 			b[j] -= d;
    486 			// find the maximum current score over all others
    487 			min_vals.erase(min_vals.find(min_val[i]));
    488 			int max_rival = *min_vals.rbegin();
    489 			min_vals.insert(min_val[i]);
    490 			if(max_rival >= max_cards)
    491 				ans[i] = max(ans[i], 0);
    492 			else
    493 			{
    494 				// binary search on the maximum cards over all
    495 				// opponents
    496 				int L = max_rival - 1;
    497 				int R = max_cards;
    498 				while(R - L > 1)
    499 				{
    500 					int mid = (L + R) / 2;
    501 					long long min_cut = 1e18;
    502 					long long req_flow = deck_size - remain[i];
    503 					// iterate on the mask of suit vertices
    504 					// which belong to S
    505 					for(int mask = 0; mask < (1 << K); mask++)
    506 					{
    507 						int suits = __builtin_popcount(mask);
    508 						long long cur_cut = 0;
    509 						for(int z = 0; z < K; z++)
    510 							if(!(mask & (1 << z)))
    511 								cur_cut += b[z];
    512 						cur_cut += add_to_cut[mask][mid];
    513 						// don't forget to discard our player
    514 						// from the flow network!
    515 						if(mid > max_x[mask][i])
    516 							cur_cut -= remain[i];
    517 						else
    518 						{
    519 							long long add = mid * suits - already_has[mask][i];
    520 							cur_cut -= add;
    521 						}
    522 						min_cut = min(min_cut, cur_cut);
    523 					}
    524 					if(min_cut < req_flow)
    525 						L = mid;
    526 					else
    527 						R = mid;
    528 				}
    529 				ans[i] = max(ans[i], max_cards - R);
    530 			}
    531 			b[j] += d;
    532 		}
    533 	}
    534 	
    535 	for(int i = 0; i < n; i++)
    536 		printf("%d ", ans[i]);
    537 	puts("");
    538 }
    539  
    540 int main()
    541 {
    542 	int t = 1;
    543 	for(int i = 0; i < t; i++) solve();
    544 }
    545 ```