1598.md (9433B)
1 Source: https://codeforces.com/blog/entry/95890 2 3 [1598A - Computer Game](/contest/1598/problem/A "Educational Codeforces Round 115 (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 def solve(): 15 n = int(input()) 16 s1 = input() 17 s2 = input() 18 bad = False 19 for i in range(n): 20 bad |= s1[i] == '1' and s2[i] == '1' 21 if bad: 22 print('NO') 23 else: 24 print('YES') 25 26 t = int(input()) 27 for i in range(t): 28 solve() 29 ``` 30 31 [1598B - Groups](/contest/1598/problem/B "Educational Codeforces Round 115 (Rated for Div. 2)") 32 33 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 34 35 **Tutorial** 36 37 Tutorial is loading... 38 39 **Solution (BledDest)** 40 41 ``` 42 t = int(input()) 43 for i in range(t): 44 n = int(input()) 45 a = [[] for i in range(n)] 46 for j in range(n): 47 a[j] = list(map(int, input().split())) 48 ans = False 49 for j in range(5): 50 for k in range(5): 51 if k != j: 52 cnt1 = 0 53 cnt2 = 0 54 cntno = 0 55 for z in range(n): 56 if a[z][j] == 1: 57 cnt1 += 1 58 if a[z][k] == 1: 59 cnt2 += 1 60 if a[z][j] == 0 and a[z][k] == 0: 61 cntno += 1 62 if cnt1 >= n // 2 and cnt2 >= n // 2 and cntno == 0: 63 ans = True 64 if ans: 65 print('YES') 66 else: 67 print('NO') 68 ``` 69 70 [1598C - Delete Two Elements](/contest/1598/problem/C "Educational Codeforces Round 115 (Rated for Div. 2)") 71 72 Idea: [fcspartakm](/profile/fcspartakm "Candidate Master fcspartakm") 73 74 **Tutorial** 75 76 Tutorial is loading... 77 78 **Solution (Neon)** 79 80 ``` 81 #include <bits/stdc++.h> 82 83 using namespace std; 84 85 int main() { 86 int t; 87 scanf("%d", &t); 88 while (t--) { 89 int n; 90 scanf("%d", &n); 91 vector<int> a(n); 92 map<int, int> cnt; 93 for (auto &x : a) { 94 scanf("%d", &x); 95 cnt[x] += 1; 96 } 97 long long sum = accumulate(a.begin(), a.end(), 0LL); 98 if ((2 * sum) % n != 0) { 99 puts("0"); 100 continue; 101 } 102 long long need = (2 * sum) / n; 103 long long ans = 0; 104 for (int i = 0; i < n; ++i) { 105 int a1 = a[i]; 106 int a2 = need - a1; 107 if (cnt.count(a2)) ans += cnt[a2]; 108 if (a1 == a2) ans -= 1; 109 } 110 printf("%lld\n", ans / 2); 111 } 112 } 113 ``` 114 115 [1598D - Training Session](/contest/1598/problem/D "Educational Codeforces Round 115 (Rated for Div. 2)") 116 117 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 118 119 **Tutorial** 120 121 Tutorial is loading... 122 123 **Solution (Neon)** 124 125 ``` 126 #include <bits/stdc++.h> 127 128 using namespace std; 129 130 int main() { 131 ios_base::sync_with_stdio(false); 132 cin.tie(NULL); 133 int t; 134 cin >> t; 135 while (t--) { 136 int n; 137 cin >> n; 138 vector<int> a(n), b(n), ca(n + 1), cb(n + 1); 139 for (int i = 0; i < n; ++i) { 140 cin >> a[i] >> b[i]; 141 ca[a[i]]++; cb[b[i]]++; 142 } 143 long long ans = n * 1LL * (n - 1) * (n - 2) / 6; 144 for (int i = 0; i < n; ++i) 145 ans -= (ca[a[i]] - 1) * 1LL * (cb[b[i]] - 1); 146 cout << ans << '\n'; 147 } 148 } 149 ``` 150 151 [1598E - Staircases](/contest/1598/problem/E "Educational Codeforces Round 115 (Rated for Div. 2)") 152 153 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution (awoo)** 160 161 ``` 162 #include <bits/stdc++.h> 163 164 #define forn(i, n) for (int i = 0; i < int(n); i++) 165 166 using namespace std; 167 168 int main() { 169 int n, m, q; 170 scanf("%d%d%d", &n, &m, &q); 171 vector<vector<int>> a(n, vector<int>(m, 1)); 172 long long ans = 0; 173 forn(x, n) forn(y, m){ 174 if (x == 0){ 175 for (int k = 1;; ++k){ 176 int nx = x + k / 2; 177 int ny = y + (k + 1) / 2; 178 if (nx == n || ny == m) break; 179 ans += k; 180 } 181 } 182 if (y == 0){ 183 for (int k = 1;; ++k){ 184 int nx = x + (k + 1) / 2; 185 int ny = y + k / 2; 186 if (nx == n || ny == m) break; 187 ans += k; 188 } 189 } 190 } 191 ans += n * m; 192 forn(i, q){ 193 int x, y; 194 scanf("%d%d", &x, &y); 195 --x, --y; 196 forn(c, 2){ 197 int l = 1, r = 1; 198 while (true){ 199 int nx = x + (l + c) / 2; 200 int ny = y + (l + !c) / 2; 201 if (nx == n || ny == m || a[nx][ny] == 0) break; 202 ++l; 203 } 204 while (true){ 205 int nx = x - (r + !c) / 2; 206 int ny = y - (r + c) / 2; 207 if (nx < 0 || ny < 0 || a[nx][ny] == 0) break; 208 ++r; 209 } 210 if (a[x][y] == 0){ 211 ans += l * r; 212 } 213 else{ 214 ans -= l * r; 215 } 216 } 217 ans += a[x][y]; 218 a[x][y] ^= 1; 219 ans -= a[x][y]; 220 printf("%lld\n", ans); 221 } 222 } 223 ``` 224 225 [1598F - RBS](/contest/1598/problem/F "Educational Codeforces Round 115 (Rated for Div. 2)") 226 227 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 228 229 **Tutorial** 230 231 Tutorial is loading... 232 233 **Solution (BledDest)** 234 235 ``` 236 #include <bits/stdc++.h> 237 238 using namespace std; 239 240 const int INF = int(1e9); 241 242 const int N = 20; 243 const int M = (1 << N); 244 245 struct BracketSeqn 246 { 247 int balance; 248 int lowestBalance; 249 vector<int> queryAns; 250 251 pair<int, bool> go(int x, bool f) 252 { 253 if(f) 254 return make_pair(0, true); 255 else 256 return make_pair(x < queryAns.size() ? queryAns[x] : 0, x + lowestBalance < 0); 257 } 258 259 BracketSeqn() {}; 260 BracketSeqn(string s) 261 { 262 vector<int> bal; 263 int cur = 0; 264 int n = s.size(); 265 for(auto x : s) 266 { 267 if(x == '(') 268 cur++; 269 else 270 cur--; 271 bal.push_back(cur); 272 } 273 balance = bal.back(); 274 lowestBalance = min(0, *min_element(bal.begin(), bal.end())); 275 vector<vector<int>> negPos(-lowestBalance + 1); 276 for(int i = 0; i < n; i++) 277 { 278 if(bal[i] > 0) continue; 279 negPos[-bal[i]].push_back(i); 280 } 281 queryAns.resize(-lowestBalance + 1); 282 for(int i = 0; i < queryAns.size(); i++) 283 { 284 int lastPos = int(1e9); 285 if(i != -lowestBalance) 286 lastPos = negPos[i + 1][0]; 287 queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) - negPos[i].begin(); 288 } 289 }; 290 }; 291 292 int dp[M][2]; 293 char buf[M]; 294 int total_bal[M]; 295 296 int main() 297 { 298 int n; 299 scanf("%d", &n); 300 vector<BracketSeqn> bs; 301 for(int i = 0; i < n; i++) 302 { 303 scanf("%s", buf); 304 string s = buf; 305 bs.push_back(BracketSeqn(s)); 306 } 307 for(int i = 0; i < (1 << n); i++) 308 for(int j = 0; j < n; j++) 309 if(i & (1 << j)) 310 total_bal[i] += bs[j].balance; 311 for(int i = 0; i < (1 << n); i++) 312 for(int j = 0; j < 2; j++) 313 dp[i][j] = -int(1e9); 314 dp[0][0] = 0; 315 for(int i = 0; i < (1 << n); i++) 316 for(int f = 0; f < 2; f++) 317 { 318 if(dp[i][f] < 0) continue; 319 for(int k = 0; k < n; k++) 320 { 321 if(i & (1 << k)) continue; 322 pair<int, bool> res = bs[k].go(total_bal[i], f); 323 dp[i ^ (1 << k)][res.second] = max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first); 324 } 325 } 326 printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1])); 327 } 328 ``` 329 330 [1598G - The Sum of Good Numbers](/contest/1598/problem/G "Educational Codeforces Round 115 (Rated for Div. 2)") 331 332 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest") 333 334 **Tutorial** 335 336 Tutorial is loading... 337 338 **Solution (Neon)** 339 340 ``` 341 #include <bits/stdc++.h> 342 343 using namespace std; 344 345 #define forn(i, n) for (int i = 0; i < int(n); ++i) 346 347 const int MOD[] = { 597804841, 618557587, 998244353 }; 348 const int N = 500 * 1000 + 13; 349 const int K = 3; 350 351 using hs = array<int, K>; 352 353 int add(int x, int y, int mod) { 354 x += y; 355 if (x >= mod) x -= mod; 356 if (x < 0) x += mod; 357 return x; 358 } 359 360 int mul(int x, int y, int mod) { 361 return x * 1LL * y % mod; 362 } 363 364 hs get(const int& x) { 365 hs c; 366 forn(i, K) c[i] = x; 367 return c; 368 } 369 370 hs operator +(const hs& a, const hs& b) { 371 hs c; 372 forn(i, K) c[i] = add(a[i], b[i], MOD[i]); 373 return c; 374 } 375 376 hs operator -(const hs& a, const hs& b) { 377 hs c; 378 forn(i, K) c[i] = add(a[i], -b[i], MOD[i]); 379 return c; 380 } 381 382 hs operator *(const hs& a, const hs& b) { 383 hs c; 384 forn(i, K) c[i] = mul(a[i], b[i], MOD[i]); 385 return c; 386 } 387 388 int n, m; 389 string s, sx; 390 hs sum[N], pw[N]; 391 392 hs get(int l, int r) { 393 return sum[r] - sum[l] * pw[r - l]; 394 } 395 396 vector<int> zfunction(const string& s) { 397 int n = s.size(); 398 vector<int> z(n); 399 int l = 0, r = 0; 400 for (int i = 1; i < n; ++i) { 401 if (i <= r) z[i] = min(z[i - l], r - i + 1); 402 while (i + z[i] < n && s[z[i]] == s[i + z[i]]) 403 ++z[i]; 404 if (i + z[i] - 1 > r) { 405 l = i; 406 r = i + z[i] - 1; 407 } 408 } 409 return z; 410 } 411 412 int main() { 413 ios_base::sync_with_stdio(false); 414 cin.tie(NULL); 415 416 cin >> s >> sx; 417 n = s.size(); 418 m = sx.size(); 419 420 pw[0] = get(1); 421 forn(i, N - 1) pw[i + 1] = pw[i] * get(10); 422 sum[0] = get(0); 423 forn(i, n) sum[i + 1] = sum[i] * get(10) + get(s[i] - '0'); 424 hs x = get(0); 425 forn(i, m) x = x * get(10) + get(sx[i] - '0'); 426 427 if (m > 1) for (int i = 0; i + 2 * (m - 1) <= n; ++i) { 428 if (get(i, i + m - 1) + get(i + m - 1, i + 2 * (m - 1)) == x) { 429 cout << i + 1 << ' ' << i + m - 1 << '\n'; 430 cout << i + m << ' ' << i + 2 * (m - 1) << '\n'; 431 return 0; 432 } 433 } 434 435 auto z = zfunction(sx + "#" + s); 436 437 for (int i = 0; i + m <= n; ++i) { 438 int lcp = z[m + i + 1]; 439 for (int len = m - lcp - 1; len <= m - lcp; ++len) { 440 if (len < 1) continue; 441 if (i + m + len <= n && get(i, i + m) + get(i + m, i + m + len) == x) { 442 cout << i + 1 << ' ' << i + m << '\n'; 443 cout << i + m + 1 << ' ' << i + m + len << '\n'; 444 return 0; 445 } 446 if (i >= len && get(i - len, i) + get(i, i + m) == x) { 447 cout << i - len + 1 << ' ' << i << '\n'; 448 cout << i + 1 << ' ' << i + m << '\n'; 449 return 0; 450 } 451 } 452 } 453 454 assert(false); 455 } 456 ```