codeforces-scrape

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

1976.md (6092B)


      1 Source: https://codeforces.com/blog/entry/129992
      2 
      3 [1976A - Verify Password](/contest/1976/problem/A "Educational Codeforces Round 166 (Rated for Div. 2)")
      4 
      5 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (awoo)**
     12 
     13 ```
     14 for _ in range(int(input())):
     15 	n = int(input())
     16 	s = input()
     17 	print("YES" if list(s) == sorted(s) else "NO")
     18 ```
     19 
     20 [1976B - Increase/Decrease/Copy](/contest/1976/problem/B "Educational Codeforces Round 166 (Rated for Div. 2)")
     21 
     22 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     23 
     24 **Tutorial**
     25 
     26 Tutorial is loading...
     27 
     28 **Solution (Neon)**
     29 
     30 ```
     31 #include <bits/stdc++.h>
     32  
     33 using namespace std;
     34  
     35 using li = long long;
     36  
     37 int main() {
     38   int t;
     39   cin >> t;
     40   while (t--) {
     41     int n;
     42     cin >> n;
     43     vector<li> a(n), b(n + 1);
     44     for (auto& x : a) cin >> x;
     45     for (auto& x : b) cin >> x;
     46     li sum = 0, ext = 1e18;
     47     for (int i = 0; i < n; ++i) {
     48       sum += abs(a[i] - b[i]);
     49       ext = min(ext, abs(a[i] - b[n]));
     50       ext = min(ext, abs(b[i] - b[n]));
     51       if (min(a[i], b[i]) <= b[n] && b[n] <= max(a[i], b[i]))
     52         ext = 0;
     53     }
     54     cout << sum + ext + 1 << '\n';
     55   }
     56 }
     57 ```
     58 
     59 [1976C - Job Interview](/contest/1976/problem/C "Educational Codeforces Round 166 (Rated for Div. 2)")
     60 
     61 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
     62 
     63 **Tutorial**
     64 
     65 Tutorial is loading...
     66 
     67 **Solution (BledDest)**
     68 
     69 ```
     70 for _ in range(int(input())):
     71     n, m = map(int, input().split())
     72     bounds = [n, m]
     73     a = []
     74     a.append(list(map(int, input().split())))
     75     a.append(list(map(int, input().split())))
     76     
     77     bad = -1
     78     badType = -1
     79     cur = [0, 0]
     80     ans = 0
     81     types = [0 for i in range(n + m + 1)]
     82     for i in range(n + m):
     83         curType = 0
     84         if a[0][i] < a[1][i]:
     85             curType = 1
     86         if cur[curType] == bounds[curType]:
     87             curType = 1 - curType
     88             if bad == -1:
     89                 bad = i
     90                 badType = 1 - curType
     91         types[i] = curType
     92         ans += a[types[i]][i]
     93         cur[types[i]] += 1
     94         
     95     res = []
     96     for i in range(n + m):
     97         val = ans - a[types[i]][i]
     98         if bad != -1 and i < bad and types[i] == badType:
     99             val = val + a[badType][bad] - a[1 - badType][bad] + a[1 - badType][n + m]
    100         else:
    101             val = val + a[types[i]][n + m]
    102         res.append(val)
    103     res.append(ans)
    104     print(*res)
    105 ```
    106 
    107 [1976D - Invertible Bracket Sequences](/contest/1976/problem/D "Educational Codeforces Round 166 (Rated for Div. 2)")
    108 
    109 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    110 
    111 **Tutorial**
    112 
    113 Tutorial is loading...
    114 
    115 **Solution (Neon)**
    116 
    117 ```
    118 #include <bits/stdc++.h>
    119  
    120 using namespace std;
    121  
    122 int main() {
    123   int t;
    124   cin >> t;
    125   while (t--) {
    126     string s;
    127     cin >> s;
    128     map<int, int> cnt;
    129     int b = 0;
    130     ++cnt[b];
    131     long long ans = 0;
    132     for (auto& c : s) {
    133       b += (c == '(' ? +1 : -1);
    134       ans += cnt[b];
    135       ++cnt[b];
    136       while (cnt.begin()->first * 2 < b)
    137         cnt.erase(cnt.begin());
    138     }
    139     cout << ans << '\n';
    140   }
    141 }
    142 ```
    143 
    144 [1976E - Splittable Permutations](/contest/1976/problem/E "Educational Codeforces Round 166 (Rated for Div. 2)")
    145 
    146 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    147 
    148 **Tutorial**
    149 
    150 Tutorial is loading...
    151 
    152 **Solution (BledDest)**
    153 
    154 ```
    155 #include<bits/stdc++.h>
    156  
    157 using namespace std;
    158  
    159 const int N = 300043;
    160 const int MOD = 998244353;
    161  
    162 int add(int x, int y)
    163 {
    164 	x += y;
    165 	while(x >= MOD) x -= MOD;
    166 	while(x < 0) x += MOD;
    167 	return x;
    168 }
    169  
    170 int mul(int x, int y)
    171 {
    172 	return (x * 1ll * y) % MOD;
    173 }
    174  
    175 int nxt[N], prv[N];
    176 bool exists[N];
    177  
    178 int main()
    179 {
    180 	int n, q;
    181 	scanf("%d %d", &n, &q);
    182 	for(int i = 1; i <= n; i++) nxt[i] = prv[i] = -1;
    183 	exists[n] = true;
    184 	vector<int> l(q), r(q);
    185 	for(int i = 0; i < q; i++) scanf("%d", &l[i]);
    186 	for(int i = 0; i < q; i++) scanf("%d", &r[i]);
    187 	for(int i = 0; i < q; i++)
    188 	{
    189 		int L = l[i], R = r[i];
    190 		if(exists[L])
    191 		{
    192 			exists[R] = true;
    193 			nxt[R] = nxt[L];
    194 			if(nxt[R] != -1) prv[nxt[R]] = R;
    195 			prv[R] = L;
    196 			nxt[L] = R;
    197 		}
    198 		else
    199 		{
    200 			exists[L] = true;
    201 			prv[L] = prv[R];
    202 			if(prv[L] != -1) nxt[prv[L]] = L;
    203 			nxt[L] = R;
    204 			prv[R] = L;
    205 		}
    206 	}
    207 	vector<int> seq;
    208 	int start = -1;
    209 	for(int i = 1; i <= n; i++)
    210 		if(prv[i] == -1 && exists[i])
    211 			start = i;
    212 	seq.push_back(start);
    213 	while(nxt[start] != -1)
    214 	{
    215 		start = nxt[start];
    216 		seq.push_back(start);
    217 	}
    218 	vector<int> cnt_segments(n + 1);
    219 	cnt_segments[seq[0]]++;
    220 	cnt_segments[seq[q]]++;
    221 	for(int i = 0; i < q; i++)
    222 		cnt_segments[max(seq[i], seq[i + 1])]++;
    223 	int ans = 1;
    224 	int places = 0;
    225 	for(int i = n; i >= 1; i--)
    226 	{
    227 		if(exists[i])
    228 			places += cnt_segments[i];
    229 		else
    230 		{
    231 			ans = mul(ans, places);
    232 			places++;
    233 		}
    234 	}
    235 	printf("%d\n", ans);
    236 }
    237 ```
    238 
    239 [1976F - Remove Bridges](/contest/1976/problem/F "Educational Codeforces Round 166 (Rated for Div. 2)")
    240 
    241 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest")
    242 
    243 **Tutorial**
    244 
    245 Tutorial is loading...
    246 
    247 **Solution (awoo)**
    248 
    249 ```
    250 #include <bits/stdc++.h>
    251  
    252 #define forn(i, n) for (int i = 0; i < int(n); i++)
    253  
    254 using namespace std;
    255  
    256 vector<int> h;
    257 vector<vector<int>> g;
    258  
    259 void dfs(int v, int p = -1){
    260 	for (int u : g[v]) if (u != p){
    261 		dfs(u, v);
    262 		h[v] = max(h[v], h[u] + 1);
    263 	}
    264 }
    265  
    266 int main() {
    267 	cin.tie(0);
    268 	ios::sync_with_stdio(false);
    269 	int t;
    270 	cin >> t;
    271 	while (t--){
    272 		int n;
    273 		cin >> n;
    274 		g.assign(n, {});
    275 		forn(i, n - 1){
    276 			int v, u;
    277 			cin >> v >> u;
    278 			--v, --u;
    279 			g[v].push_back(u);
    280 			g[u].push_back(v);
    281 		}
    282 		h.assign(n, 0);
    283 		dfs(0);
    284 		set<pair<int, int>> cur;
    285 		forn(i, n) cur.insert({h[i], i});
    286 		vector<int> ans;
    287 		int tmp = n;
    288 		while (!cur.empty()){
    289 			int v = cur.rbegin()->second;
    290 			while (v != -1){
    291 				--tmp;
    292 				cur.erase({h[v], v});
    293 				int pv = -1;
    294 				for (int u : g[v]) if (h[u] == h[v] - 1){
    295 					pv = u;
    296 					break;
    297 				}
    298 				v = pv;
    299 			}
    300 			ans.push_back(tmp);
    301 		}
    302 		for (int i = 0; i < int(ans.size()); i += 2){
    303 			cout << ans[i] << ' ';
    304 		}
    305 		for (int i = (int(ans.size()) + 1) / 2; i < n - 1; ++i){
    306 			cout << 0 << ' ';
    307 		}
    308 		cout << '\n';
    309 	}
    310 	return 0;
    311 }
    312 ```