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 ```