codeforces-scrape

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

1574.md (8125B)


      1 Source: https://codeforces.com/blog/entry/95188
      2 
      3 [1574A - Regular Bracket Sequences](/contest/1574/problem/A "Educational Codeforces Round 114 (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 = int(input())
     17     for j in range(n):
     18         print("()" * j + "(" * (n - j) + ")" * (n - j))
     19 ```
     20 
     21 [1574B - Combinatorics Homework](/contest/1574/problem/B "Educational Codeforces Round 114 (Rated for Div. 2)")
     22 
     23 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     24 
     25 **Tutorial**
     26 
     27 Tutorial is loading...
     28 
     29 **Solution (awoo)**
     30 
     31 ```
     32 for _ in range(int(input())):
     33 	a, b, c, m = map(int, input().split())
     34 	a, b, c = sorted([a, b, c])
     35 	print("YES" if c - (a + b + 1) <= m <= a + b + c - 3 else "NO")
     36 ```
     37 
     38 [1574C - Slay the Dragon](/contest/1574/problem/C "Educational Codeforces Round 114 (Rated for Div. 2)")
     39 
     40 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     41 
     42 **Tutorial**
     43 
     44 Tutorial is loading...
     45 
     46 **Solution (Neon)**
     47 
     48 ```
     49 #include <bits/stdc++.h>
     50 
     51 using namespace std;
     52 
     53 using li = long long;
     54 
     55 int main() {
     56   ios_base::sync_with_stdio(false);
     57   cin.tie(NULL); 
     58   int n;
     59   cin >> n;
     60   vector<li> a(n);
     61   for (auto &x : a) cin >> x;
     62   sort(a.begin(), a.end());
     63   li sum = accumulate(a.begin(), a.end(), 0LL);
     64   int m;
     65   cin >> m;
     66   while (m--) {
     67     li x, y;
     68     cin >> x >> y;
     69     int i = lower_bound(a.begin(), a.end(), x) - a.begin();
     70     li ans = 2e18;
     71     if (i > 0) ans = min(ans, (x - a[i - 1]) + max(0LL, y - sum + a[i - 1]));
     72     if (i < n) ans = min(ans, max(0LL, y - sum + a[i]));
     73     cout << ans << '\n';
     74   }
     75 }
     76 ```
     77 
     78 [1574D - The Strongest Build](/contest/1574/problem/D "Educational Codeforces Round 114 (Rated for Div. 2)")
     79 
     80 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     81 
     82 **Tutorial**
     83 
     84 Tutorial is loading...
     85 
     86 **Solution (awoo)**
     87 
     88 ```
     89 #include <bits/stdc++.h>
     90 
     91 #define forn(i, n) for (int i = 0; i < int(n); i++)
     92 
     93 using namespace std;
     94 
     95 int n;
     96 vector<vector<int>> a;
     97 int m;
     98 vector<vector<int>> b;
     99 
    100 int main() {
    101 	scanf("%d", &n);
    102 	a.resize(n);
    103 	forn(i, n){
    104 		int c;
    105 		scanf("%d", &c);
    106 		a[i].resize(c);
    107 		forn(j, c) scanf("%d", &a[i][j]);
    108 	}
    109 	scanf("%d", &m);
    110 	b.resize(m);
    111 	forn(i, m){
    112 		b[i].resize(n);
    113 		forn(j, n){
    114 			scanf("%d", &b[i][j]);
    115 			--b[i][j];
    116 		}
    117 	}
    118 	sort(b.begin(), b.end());
    119 	vector<int> ult(n);
    120 	forn(i, n) ult[i] = int(a[i].size()) - 1;
    121 	if (!binary_search(b.begin(), b.end(), ult)){
    122 		forn(i, n) printf("%d ", ult[i] + 1);
    123 		puts("");
    124 		return 0;
    125 	}
    126 	int mx = 0;
    127 	vector<int> ans(n, -1);
    128 	forn(i, m){
    129 		vector<int> tmp = b[i];
    130 		int sum = 0;
    131 		forn(j, n) sum += a[j][tmp[j]];
    132 		forn(j, n) if (tmp[j] != 0){
    133 			--tmp[j];
    134 			if (!binary_search(b.begin(), b.end(), tmp) && sum - a[j][tmp[j] + 1] + a[j][tmp[j]] > mx){
    135 				mx = sum - a[j][tmp[j] + 1] + a[j][tmp[j]];
    136 				ans = tmp;
    137 			}
    138 			++tmp[j];
    139 		}
    140 	}
    141 	forn(i, n){
    142 		printf("%d ", ans[i] + 1);
    143 	}
    144 	puts("");
    145 }
    146 ```
    147 
    148 [1574E - Coloring](/contest/1574/problem/E "Educational Codeforces Round 114 (Rated for Div. 2)")
    149 
    150 Idea: [Roms](/profile/Roms "Master Roms")
    151 
    152 **Tutorial**
    153 
    154 Tutorial is loading...
    155 
    156 **Solution (Roms)**
    157 
    158 ```
    159 #include <bits/stdc++.h>
    160 
    161 using namespace std;
    162 
    163 const int MOD = 998244353;
    164 const int N = 1'000'009;
    165 
    166 int sum (int a, int b) {
    167     int res = a + b;
    168     if (res < 0) res += MOD;
    169     if (res >= MOD) res -= MOD;
    170     return res;
    171 }
    172 
    173 int n, m, k;
    174 map <pair <int, int>, char> c;
    175 int cntr[N][2], cntc[N][2];
    176 int cntx[2];
    177 set <int> badr, badc;
    178 set<int> ur, uc;
    179 int p2[N];
    180 
    181 void upd2(int pos, int col, int add, int cnt[N][2], set <int> &bad, set<int> &u) {
    182     cnt[pos][col] += add;
    183     assert(cnt[pos][col] >= 0);
    184     
    185     if (cnt[pos][0] > 0 && cnt[pos][1] > 0){
    186         if (!bad.count(pos))
    187             bad.insert(pos);
    188     } else {
    189         if (bad.count(pos))
    190             bad.erase(pos);
    191     }
    192     
    193     if (cnt[pos][0] > 0 || cnt[pos][1] > 0){
    194         if (!u.count(pos))
    195             u.insert(pos);
    196     } else {
    197         if (u.count(pos))
    198             u.erase(pos);
    199     }
    200 }
    201 
    202 void upd(int x, int y, int t) {
    203     int col = (x & 1) ^ (y & 1);
    204     if (c.count({x, y})) {
    205         int ncol = col ^ c[{x, y}];
    206         --cntx[ncol];
    207         upd2(x, ncol, -1, cntr, badr, ur);
    208         upd2(y, ncol, -1, cntc, badc, uc);
    209         c.erase({x, y});
    210     }
    211     
    212     if (t == -1)
    213         return;
    214         
    215     int ncol = col ^ t;
    216     ++cntx[ncol];
    217     upd2(x, ncol, 1, cntr, badr, ur);
    218     upd2(y, ncol, 1, cntc, badc, uc);
    219     c[{x, y}] = t;
    220 }
    221 
    222 int main(){
    223     p2[0] = 1;
    224     for (int i = 1; i < N; ++i)
    225         p2[i] = sum(p2[i - 1], p2[i - 1]);
    226         
    227     scanf("%d%d%d", &n, &m, &k);
    228     for (int i = 0; i < k; ++i) {
    229         int x, y, t;
    230         scanf("%d %d %d", &x, &y, &t);
    231         --x, --y;
    232         upd(x, y, t);
    233         
    234         int res = 0;
    235         if(badr.size() > 0 && badc.size() > 0) {
    236             res = 0;
    237         } else if (badr.size() > 0) {
    238             assert(m - uc.size() >= 0);
    239             res = p2[m - uc.size()];
    240         } else if (badc.size() > 0) {
    241             assert(n - ur.size() >= 0);
    242             res = p2[n - ur.size()];
    243         } else {
    244             if (ur.size() == 0 && uc.size() == 0)
    245                 res = sum(sum(p2[n], p2[m]), -2);
    246             else {
    247                 assert(m - uc.size() >= 0);
    248                 res = sum(res, p2[m - uc.size()]);
    249                 assert(n - ur.size() >= 0);
    250                 res = sum(res, p2[n - ur.size()]);
    251                 if (cntx[0] == 0 || cntx[1] == 0) {
    252                     assert(cntx[0] != 0 || cntx[1] != 0);
    253                     res = sum(res, -1);
    254                 }
    255             }
    256         }
    257         
    258         printf("%d\n", res);
    259     }
    260     return 0;
    261 }
    262 ```
    263 
    264 [1574F - Occurrences](/contest/1574/problem/F "Educational Codeforces Round 114 (Rated for Div. 2)")
    265 
    266 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    267 
    268 **Tutorial**
    269 
    270 Tutorial is loading...
    271 
    272 **Solution (BledDest)**
    273 
    274 ```
    275 #include <bits/stdc++.h>     
    276 
    277 using namespace std;
    278 
    279 const int MOD = 998244353;
    280 
    281 int add(int x, int y)
    282 {
    283  	x += y;
    284  	while(x >= MOD) x -= MOD;
    285  	while(x < 0) x += MOD;
    286  	return x;
    287 }
    288 
    289 int mul(int x, int y)
    290 {
    291  	return (x * 1ll * y) % MOD;
    292 }
    293 
    294 int main()
    295 {
    296 	int n, m, k;
    297 	scanf("%d %d %d", &n, &m, &k);
    298 	vector<vector<int>> A(n);
    299 	vector<int> bad_num(k);
    300 	for(int i = 0; i < n; i++)
    301 	{
    302 		int c;
    303 		scanf("%d", &c);
    304 		A[i].resize(c);
    305 		for(int j = 0; j < c; j++)
    306 		{
    307 			scanf("%d", &A[i][j]); 	
    308 			A[i][j]--;
    309 		}
    310 	}
    311 
    312 	for(int i = 0; i < n; i++)
    313 	{
    314 	 	if(set<int>(A[i].begin(), A[i].end()).size() != A[i].size())
    315 	 	{
    316 	 	 	for(auto x : A[i])
    317 	 	 		bad_num[x] = 1;
    318 	 	}
    319 	}
    320 	vector<vector<int>> nxt(k);
    321 	vector<vector<int>> prv(k);
    322 	for(int i = 0; i < n; i++)
    323 		for(int j = 0; j + 1 < A[i].size(); j++)
    324 		{
    325 		 	nxt[A[i][j]].push_back(A[i][j + 1]);
    326 		 	prv[A[i][j + 1]].push_back(A[i][j]);
    327 		}
    328 
    329 	for(int i = 0; i < k; i++)
    330 	{
    331 	    sort(nxt[i].begin(), nxt[i].end());
    332 	    sort(prv[i].begin(), prv[i].end());
    333 	 	nxt[i].erase(unique(nxt[i].begin(), nxt[i].end()), nxt[i].end());
    334 	 	prv[i].erase(unique(prv[i].begin(), prv[i].end()), prv[i].end());
    335 	}
    336 
    337 	vector<int> used(k, 0);
    338 	vector<int> cnt(k + 1, 0);
    339 	for(int i = 0; i < k; i++)
    340 	{
    341 		if(used[i]) continue;
    342 	 	queue<int> q;
    343 	 	vector<int> comp;
    344 	 	q.push(i);
    345 	 	used[i] = 1;
    346 	 	while(!q.empty())
    347 	 	{
    348 	 		int z = q.front();
    349 	 		q.pop();
    350 	 		comp.push_back(z);
    351 	 	 	for(auto x : nxt[z])
    352 	 	 		if(!used[x])
    353 	 	 		{
    354 	 	 		 	used[x] = 1;
    355 	 	 		 	q.push(x);
    356 	 	 		}
    357 	 	 	for(auto x : prv[z])
    358 	 	 		if(!used[x])
    359 	 	 		{
    360 	 	 		 	used[x] = 1;
    361 	 	 		 	q.push(x);
    362 	 	 		}
    363 	 	}
    364 	 	bool bad = false;
    365 	 	int cnt_beg = 0;
    366 	 	for(auto x : comp)
    367 	 	{
    368 	 	 	if(prv[x].empty())
    369 	 	 		cnt_beg++;
    370 	 	 	if(prv[x].size() > 1 || nxt[x].size() > 1 || bad_num[x])
    371 	 	 		bad = true;
    372 	 	}
    373 	 	bad |= (cnt_beg == 0);
    374 	 	if(!bad)
    375 	 		cnt[comp.size()]++;
    376 	}
    377 	vector<int> nonzero;
    378 	for(int i = 1; i <= k; i++)
    379 		if(cnt[i] > 0)
    380 			nonzero.push_back(i);
    381 	vector<int> dp(m + 1, 0);
    382 	dp[0] = 1;
    383 	for(int i = 1; i <= m; i++)
    384 		for(auto x : nonzero)
    385 		 	if(x <= i)
    386 		 		dp[i] = add(dp[i], mul(cnt[x], dp[i - x]));
    387 
    388 	printf("%d\n", dp[m]);
    389 	return 0;
    390 }
    391 ```