1913.md (12004B)
1 Source: https://codeforces.com/blog/entry/123493 2 3 [1913A - Rating Increase](/contest/1913/problem/A "Educational Codeforces Round 160 (Rated for Div. 2)") 4 5 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [awoo](/profile/awoo "Master awoo") 6 7 **Tutorial** 8 9 Tutorial is loading... 10 11 **Solution (awoo)** 12 13 ``` 14 for _ in range(int(input())): 15 ab = input() 16 for i in range(1, len(ab)): 17 if ab[i] != '0' and int(ab[:i]) < int(ab[i:]): 18 print(ab[:i], ab[i:]) 19 break 20 else: 21 print(-1) 22 ``` 23 24 [1913B - Swap and Delete](/contest/1913/problem/B "Educational Codeforces Round 160 (Rated for Div. 2)") 25 26 Idea: [BledDest](/profile/BledDest "International Grandmaster BledDest"), preparation: [adedalic](/profile/adedalic "International Master adedalic") 27 28 **Tutorial** 29 30 Tutorial is loading... 31 32 **Solution (adedalic)** 33 34 ``` 35 for _ in range(int(input())): 36 s = input() 37 cnt = [0, 0] 38 for i in range(len(s)): 39 cnt[int(s[i])] += 1 40 for i in range(len(s) + 1): 41 if (i == len(s) or cnt[1 - int(s[i])] == 0): 42 print(len(s) - i) 43 break 44 cnt[1 - int(s[i])] -= 1 45 ``` 46 47 [1913C - Game with Multiset](/contest/1913/problem/C "Educational Codeforces Round 160 (Rated for Div. 2)") 48 49 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume") 50 51 **Tutorial** 52 53 Tutorial is loading... 54 55 **Solution (awoo)** 56 57 ``` 58 from sys import stdin, stdout 59 60 LOG = 30 61 cnt = [0 for i in range(LOG)] 62 ans = [] 63 for _ in range(int(stdin.readline())): 64 t, v = map(int, stdin.readline().split()) 65 if t == 1: 66 cnt[v] += 1 67 else: 68 nw = 0 69 for i in range(LOG): 70 r = (v % (2 << i)) // (1 << i) 71 if r > nw + cnt[i]: 72 ans.append(0) 73 break 74 v -= r 75 nw = (nw + cnt[i] - r) // 2 76 else: 77 ans.append(nw >= (v >> 30)) 78 stdout.write('\n'.join(["YES" if x else "NO" for x in ans])) 79 ``` 80 81 [1913D - Array Collapse](/contest/1913/problem/D "Educational Codeforces Round 160 (Rated for Div. 2)") 82 83 Idea: [Roms](/profile/Roms "Master Roms"), preparation: [Roms](/profile/Roms "Master Roms") 84 85 **Tutorial** 86 87 Tutorial is loading... 88 89 **Solution (Roms)** 90 91 ``` 92 #include <bits/stdc++.h> 93 94 using namespace std; 95 96 const int MOD = 998244353; 97 98 int normalize(long long x) { 99 x %= MOD; 100 if (x < 0) x += MOD; 101 return x; 102 } 103 104 int main() { 105 int t; 106 cin >> t; 107 for (int tc = 0; tc < t; ++tc) { 108 int n; 109 cin >> n; 110 vector <int> a(n); 111 vector <int> nextMin(n); 112 vector <int> dpSum(n + 2); 113 vector <int> dpNext(n); 114 for (int i = 0; i < n; ++i) 115 cin >> a[i]; 116 117 stack <int> stMin; 118 nextMin[n - 1] = n; 119 dpSum[n] = 1; 120 for (int pos = n - 1; pos >= 0; --pos) { 121 while(!stMin.empty() && a[stMin.top()] > a[pos]) 122 stMin.pop(); 123 nextMin[pos] = stMin.empty() ? n : stMin.top(); 124 stMin.push(pos); 125 126 int nxtPos = nextMin[pos]; 127 int dpPos = normalize(dpSum[pos + 1] - dpSum[nxtPos + 1]); 128 if (nxtPos != n) { 129 dpPos = normalize(dpPos + dpNext[nxtPos]); 130 dpNext[pos] = normalize(dpSum[nxtPos] - dpSum[nxtPos + 1] + dpNext[nxtPos]); 131 } 132 dpSum[pos] = normalize(dpPos + dpSum[pos + 1]); 133 134 //cout << pos << ' ' << nxtPos << ' ' << dpPos << endl; 135 } 136 137 int res = 0; 138 int mn = a[0]; 139 for(int i = 0; i < n; ++i) { 140 mn = min(mn, a[i]); 141 if (a[i] == mn) { 142 res = normalize(res + dpSum[i] - dpSum[i + 1]); 143 } 144 } 145 cout << res << endl; 146 } 147 return 0; 148 } 149 ``` 150 151 [1913E - Matrix Problem](/contest/1913/problem/E "Educational Codeforces Round 160 (Rated for Div. 2)") 152 153 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume") 154 155 **Tutorial** 156 157 Tutorial is loading... 158 159 **Solution (BledDest)** 160 161 ``` 162 #include<bits/stdc++.h> 163 164 using namespace std; 165 166 const int N = 111; 167 168 struct edge 169 { 170 int y, c, w, f; 171 edge() {}; 172 edge(int y, int c, int w, int f) : y(y), c(c), w(w), f(f) {}; 173 }; 174 175 vector<edge> e; 176 vector<int> g[N]; 177 178 int rem(int x) 179 { 180 return e[x].c - e[x].f; 181 } 182 183 void add_edge(int x, int y, int c, int w) 184 { 185 g[x].push_back(e.size()); 186 e.push_back(edge(y, c, w, 0)); 187 g[y].push_back(e.size()); 188 e.push_back(edge(x, 0, -w, 0)); 189 } 190 191 int n, m, s, t, v; 192 193 pair<int, long long> MCMF() 194 { 195 int flow = 0; 196 long long cost = 0; 197 while(true) 198 { 199 vector<long long> d(v, (long long)(1e18)); 200 vector<int> p(v, -1); 201 vector<int> pe(v, -1); 202 queue<int> q; 203 vector<bool> inq(v); 204 q.push(s); 205 inq[s] = true; 206 d[s] = 0; 207 while(!q.empty()) 208 { 209 int k = q.front(); 210 q.pop(); 211 inq[k] = false; 212 for(auto ei : g[k]) 213 { 214 if(rem(ei) == 0) continue; 215 int to = e[ei].y; 216 int w = e[ei].w; 217 if(d[to] > d[k] + w) 218 { 219 d[to] = d[k] + w; 220 p[to] = k; 221 pe[to] = ei; 222 if(!inq[to]) 223 { 224 inq[to] = true; 225 q.push(to); 226 } 227 } 228 } 229 } 230 if(p[t] == -1) break; 231 flow++; 232 cost += d[t]; 233 int cur = t; 234 while(cur != s) 235 { 236 e[pe[cur]].f++; 237 e[pe[cur] ^ 1].f--; 238 cur = p[cur]; 239 } 240 } 241 return make_pair(flow, cost); 242 } 243 244 int get_sum(const vector<int>& v) 245 { 246 int sum = 0; 247 for(auto x : v) sum += x; 248 return sum; 249 } 250 251 int main() 252 { 253 cin >> n >> m; 254 s = n + m; 255 t = n + m + 1; 256 v = n + m + 2; 257 int sum_matrix = 0; 258 vector<int> A(n), B(m); 259 for(int i = 0; i < n; i++) 260 for(int j = 0; j < m; j++) 261 { 262 int x; 263 cin >> x; 264 sum_matrix += x; 265 if(x == 1) 266 add_edge(i, j + n, 1, 0); 267 else 268 add_edge(i, j + n, 1, 1); 269 } 270 for(int i = 0; i < n; i++) 271 { 272 cin >> A[i]; 273 add_edge(s, i, A[i], 0); 274 } 275 for(int i = 0; i < m; i++) 276 { 277 cin >> B[i]; 278 add_edge(i + n, t, B[i], 0); 279 } 280 281 auto res = MCMF(); 282 if(res.first != get_sum(A) || res.first != get_sum(B)) 283 cout << -1 << endl; 284 else 285 cout << sum_matrix - res.first + res.second * 2 << endl; 286 } 287 ``` 288 289 [1913F - Palindromic Problem](/contest/1913/problem/F "Educational Codeforces Round 160 (Rated for Div. 2)") 290 291 Idea: [Ferume](/profile/Ferume "Master Ferume"), preparation: [Ferume](/profile/Ferume "Master Ferume") 292 293 **Tutorial** 294 295 Tutorial is loading... 296 297 **Solution (awoo)** 298 299 ``` 300 #include <bits/stdc++.h> 301 302 #define forn(i, n) for (int i = 0; i < int(n); i++) 303 #define x first 304 #define y second 305 306 using namespace std; 307 308 struct sparse_table { 309 vector<vector<int>> st; 310 vector<int> pw; 311 312 sparse_table() {} 313 314 sparse_table(const vector<int> &a) { 315 int n = a.size(); 316 int logn = 32 - __builtin_clz(n); 317 st.resize(logn, vector<int>(n)); 318 forn(i, n) 319 st[0][i] = a[i]; 320 for (int j = 1; j < logn; ++j) forn(i, n) { 321 st[j][i] = st[j - 1][i]; 322 if (i + (1 << (j - 1)) < n) 323 st[j][i] = min(st[j][i], st[j - 1][i + (1 << (j - 1))]); 324 } 325 pw.resize(n + 1); 326 pw[0] = pw[1] = 0; 327 for (int i = 2; i <= n; ++i) 328 pw[i] = pw[i >> 1] + 1; 329 } 330 331 int get(int l, int r) { 332 if (l >= r) return 1e9; 333 int len = pw[r - l]; 334 return min(st[len][l], st[len][r - (1 << len)]); 335 } 336 }; 337 338 struct suffix_array { 339 vector<int> c, pos; 340 vector<pair<pair<int, int>, int>> p, nw; 341 vector<int> cnt; 342 int n; 343 344 void radix_sort(int max_al) { 345 cnt.assign(max_al, 0); 346 forn(i, n) ++cnt[p[i].x.y]; 347 for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1]; 348 nw.resize(n); 349 forn(i, n) nw[--cnt[p[i].x.y]] = p[i]; 350 cnt.assign(max_al, 0); 351 forn(i, n) ++cnt[nw[i].x.x]; 352 for (int i = 1; i < max_al; ++i) cnt[i] += cnt[i - 1]; 353 for (int i = n - 1; i >= 0; --i) p[--cnt[nw[i].x.x]] = nw[i]; 354 } 355 356 vector<int> lcp; 357 sparse_table st; 358 359 int get_lcp(int l, int r) { 360 l = c[l], r = c[r]; 361 if (l > r) swap(l, r); 362 return st.get(l, r); 363 } 364 365 suffix_array(const string &s) { 366 n = s.size(); 367 c = vector<int>(s.begin(), s.end()); 368 int max_al = *max_element(c.begin(), c.end()) + 1; 369 p.resize(n); 370 for (int k = 1; k < n; k <<= 1) { 371 for (int i = 0, j = k; i < n; ++i, j = (j + 1 == n ? 0 : j + 1)) 372 p[i] = make_pair(make_pair(c[i], c[j]), i); 373 radix_sort(max_al); 374 c[p[0].y] = 0; 375 for (int i = 1; i < n; ++i) c[p[i].y] = c[p[i - 1].y] + (p[i].x != p[i - 1].x); 376 max_al = c[p.back().y] + 1; 377 } 378 lcp.resize(n); 379 int l = 0; 380 forn(i, n) { 381 l = max(0, l - 1); 382 if (c[i] == n - 1) 383 continue; 384 while (i + l < n && p[c[i] + 1].y + l < n && s[i + l] == s[p[c[i] + 1].y + l]) 385 ++l; 386 lcp[c[i]] = l; 387 } 388 pos.resize(n); 389 forn(i, n) 390 pos[i] = p[i].y; 391 st = sparse_table(lcp); 392 } 393 }; 394 395 int main() { 396 string s; 397 int n; 398 cin >> n; 399 cin >> s; 400 string t = s; 401 reverse(t.begin(), t.end()); 402 auto sa = suffix_array(s + "#" + t + "$"); 403 vector<vector<int>> ev0(n), ev1(n); 404 long long base = 0; 405 vector<long long> dt(n + 2); 406 vector<int> d1(n); 407 forn(i, n){ 408 int len0 = sa.get_lcp(i, 2 * n - i + 1); 409 base += len0; 410 dt[i - len0] += 1; 411 dt[i] -= 1; 412 dt[i + 1] -= 1; 413 dt[i + len0 + 1] += 1; 414 if (i - len0 - 1 >= 0 && i + len0 < n){ 415 ev0[i - len0 - 1].push_back(i); 416 ev0[i + len0].push_back(i); 417 } 418 int len1 = sa.get_lcp(i, 2 * n - i); 419 d1[i] = len1; 420 dt[i - len1 + 1] += 1; 421 dt[i + 1] -= 2; 422 dt[i + len1 + 1] += 1; 423 base += len1; 424 if (i - len1 >= 0 && i + len1 < n){ 425 ev1[i - len1].push_back(i); 426 ev1[i + len1].push_back(i); 427 } 428 } 429 vector<long long> dx(n + 1); 430 long long curt = 0, val = 0; 431 forn(i, n){ 432 curt += dt[i]; 433 val += curt; 434 dx[i] = val; 435 } 436 long long ans = base; 437 int pos = -1, nc = -1; 438 bool gr = false; 439 forn(i, n) forn(c, 26) if (c != s[i] - 'a'){ 440 long long cur = base; 441 for (int j : ev0[i]){ 442 if (j <= i && c == s[2 * j - i - 1] - 'a') 443 cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 2)); 444 else if (j > i && c == s[2 * j - i - 1] - 'a') 445 cur += 1 + sa.get_lcp(2 * j - i, 2 * n - (i - 1)); 446 } 447 for (int j : ev1[i]){ 448 if (c != s[2 * j - i] - 'a') continue; 449 if (j < i) 450 cur += 1 + sa.get_lcp(i + 1, 2 * n - (2 * j - i - 1)); 451 else 452 cur += 1 + sa.get_lcp(2 * j - i + 1, 2 * n - (i - 1)); 453 } 454 cur += d1[i]; 455 cur -= dx[i]; 456 bool upd = false; 457 if (cur > ans){ 458 upd = true; 459 } 460 else if (cur == ans){ 461 if (c < s[i] - 'a'){ 462 if (pos == -1 || gr) 463 upd = true; 464 } 465 else{ 466 if (pos < i && gr) 467 upd = true; 468 } 469 } 470 if (upd){ 471 ans = cur; 472 pos = i; 473 nc = c; 474 gr = c > s[i] - 'a'; 475 } 476 } 477 cout << ans << endl; 478 if (pos != -1) s[pos] = nc + 'a'; 479 cout << s << endl; 480 return 0; 481 } 482 ```