1290.md (19734B)
1 Source: https://codeforces.com/blog/entry/73563 2 3 Hello everyone, this is the editorial for [Codeforces Round 616 (Div. 1)](/contest/1290 "Codeforces Round 616 (Div. 1)") and [Codeforces Round 616 (Div. 2)](/contest/1291 "Codeforces Round 616 (Div. 2)")! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b 4 5 [1291A - Even But Not Even](/contest/1291/problem/A "Codeforces Round 616 (Div. 2)") 6 7 Author: [265918](/profile/265918 "Candidate Master 265918") 8 9 **Tutorial** 10 11 Tutorial is loading... 12 13 **Implementation** 14 15 ``` 16 #include <bits/stdc++.h> 17 18 using namespace std; 19 20 int main() { 21 ios::sync_with_stdio(false); 22 cin.tie(nullptr); 23 int t; cin >> t; 24 while (t--) { 25 int n; cin >> n; 26 string s; cin >> s; 27 int odd = 0; 28 for (char c : s) if ((c - '0') & 1) odd++; 29 if (odd <= 1) { cout << "-1\n"; continue; } 30 int cnt = 0; 31 for (char c : s) { 32 if ((c - '0') & 1) { cout << c; cnt++; } 33 if (cnt == 2) break; 34 } 35 cout << '\n'; 36 } 37 return 0; 38 } 39 ``` 40 41 [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)") 42 43 Author: [hugopm](/profile/hugopm "International Master hugopm") 44 45 **Tutorial** 46 47 Tutorial is loading... 48 49 **Implementation** 50 51 ``` 52 #include <bits/stdc++.h> 53 using namespace std; 54 55 int main() 56 { 57 ios::sync_with_stdio(false); cin.tie(0); 58 59 int nbTests; cin >> nbTests; 60 while (nbTests--) { 61 int nbElem; cin >> nbElem; 62 vector<int> tab(nbElem); 63 64 for (int i = 0; i < nbElem; ++i) 65 cin >> tab[i]; 66 67 int prefixEnd = -1, suffixEnd = nbElem; 68 69 for (int i = 0; i < nbElem; ++i) { 70 if (tab[i] < i) break; 71 prefixEnd = i; 72 } 73 for (int i = nbElem-1; i >= 0; --i) { 74 if (tab[i] < (nbElem-1)-i) break; 75 suffixEnd = i; 76 } 77 78 if (suffixEnd <= prefixEnd) // Non-empty intersection 79 cout << "Yes\n"; 80 else 81 cout << "No\n"; 82 } 83 } 84 ``` 85 86 [1290A - Mind Control](/contest/1290/problem/A "Codeforces Round 616 (Div. 1)") 87 88 Author: [Ari](/profile/Ari "Master Ari") 89 90 **Tutorial** 91 92 Tutorial is loading... 93 94 **Implementation (quadratic)** 95 96 ``` 97 #include <bits/stdc++.h> 98 using namespace std; 99 100 int main() 101 { 102 ios::sync_with_stdio(false); cin.tie(0); 103 104 int nbTests; cin >> nbTests; 105 while (nbTests--) { 106 int nbElem, pos, nbControl; 107 cin >> nbElem >> pos >> nbControl; 108 109 int before = pos-1, behind = nbElem-pos; 110 nbControl = min(nbControl, before); 111 112 vector<int> tab(nbElem); 113 for (int i = 0; i < nbElem; ++i) cin >> tab[i]; 114 115 int bestStrategy = 0; 116 117 for (int orderFirst = 0; orderFirst <= nbControl; ++orderFirst) { 118 int strategyAns = (int)(1e9) + 5; 119 for (int opponentFirst = 0; opponentFirst <= before-nbControl; ++opponentFirst) { 120 int caseAns = max(tab[orderFirst + opponentFirst], tab[orderFirst + opponentFirst + behind]); 121 strategyAns = min(strategyAns, caseAns); 122 } 123 bestStrategy = max(bestStrategy, strategyAns); 124 } 125 126 cout << bestStrategy << "\n"; 127 } 128 } 129 ``` 130 131 **Implementation (linear)** 132 133 ``` 134 #include <bits/stdc++.h> 135 using namespace std; 136 137 void solve() { 138 int n, m, k; 139 cin >> n >> m >> k; 140 k = min(k, m - 1); 141 vector<int> a(n); 142 for(auto &x : a) 143 cin >> x; 144 vector<int> b; 145 for(int i = 0; i < m; i++) 146 b.push_back(max(a[i], a[i + n - m])); 147 int sz = m - k; 148 int ans = 0; 149 deque<int> q; 150 for(int i = 0, j = 0; i + sz - 1 < m; i++) { 151 while(q.size() && q.front() < i) 152 q.pop_front(); 153 while(j < i + sz) { 154 while(q.size() && b[q.back()] >= b[j]) 155 q.pop_back(); 156 q.push_back(j++); 157 } 158 ans = max(ans, b[q.front()]); 159 } 160 cout << ans << '\n'; 161 } 162 163 int main() { 164 int t; 165 cin >> t; 166 while(t--) 167 solve(); 168 } 169 ``` 170 171 [1290B - Irreducible Anagrams](/contest/1290/problem/B "Codeforces Round 616 (Div. 1)") 172 173 Author: [Ari](/profile/Ari "Master Ari") 174 175 **Tutorial** 176 177 Tutorial is loading... 178 179 **Implementation** 180 181 ``` 182 #include <bits/stdc++.h> 183 using namespace std; 184 185 const int N = 200005; 186 187 char s[N]; 188 int n, q, l, r, sum[N][26]; 189 190 int main() { 191 ios_base::sync_with_stdio(false); 192 cin.tie(nullptr); 193 cin >> (s + 1); 194 n = strlen(s + 1); 195 for (int i = 1; i <= n; i++) { 196 for (int j = 0; j < 26; j++) { 197 sum[i][j] = sum[i - 1][j]; 198 } 199 sum[i][s[i] - 'a']++; 200 } 201 cin >> q; 202 while (q--) { 203 cin >> l >> r; 204 int cnt = 0; 205 for (int i = 0; i < 26; i++) { 206 cnt += (sum[r][i] - sum[l - 1][i] > 0); 207 } 208 if (l == r || cnt >= 3 || s[l] != s[r]) { 209 cout << "Yes\n"; 210 } else { 211 cout << "No\n"; 212 } 213 } 214 } 215 ``` 216 217 [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)") 218 219 Author: [hugopm](/profile/hugopm "International Master hugopm") 220 221 **Tutorial** 222 223 Tutorial is loading... 224 225 **Implementation (preprocess with DFS)** 226 227 ``` 228 #include <bits/stdc++.h> 229 using namespace std; 230 using pii = pair<int, int>; 231 232 const int lim = 1000*1000 + 5; 233 int nbElem, nbSub; 234 vector<int> subset[lim]; 235 int side[lim]; 236 int isIn[lim][2]; 237 string ini; 238 int rep = 0; 239 240 int drepr[lim]; 241 int dsz[lim]; 242 int cnt[lim][2]; 243 244 int dfind(int x) 245 { 246 if (drepr[x] != x) drepr[x] = dfind(drepr[x]); 247 return drepr[x]; 248 } 249 250 void add(int cc, int s0, int s1) 251 { 252 cc = dfind(cc); 253 rep -= min(cnt[cc][0], cnt[cc][1]); 254 cnt[cc][0] = min(lim, cnt[cc][0] + s0); 255 cnt[cc][1] = min(lim, cnt[cc][1] + s1); 256 rep += min(cnt[cc][0], cnt[cc][1]); 257 } 258 259 void dmerge(int a, int b) 260 { 261 a = dfind(a); b = dfind(b); 262 if (a == b) return; 263 if (dsz[a] < dsz[b]) swap(a,b); 264 add(a, cnt[b][0], cnt[b][1]); 265 add(b, -cnt[b][0], -cnt[b][1]); 266 dsz[a] += dsz[b]; 267 drepr[b] = a; 268 } 269 270 void dfs(int nod) 271 { 272 cnt[nod][side[nod]] = 1; 273 for (int elem : subset[nod]) { 274 if (isIn[elem][1] == -1) continue; 275 int oth = isIn[elem][0] + isIn[elem][1] - nod; 276 if (side[oth] == -1) { 277 side[oth] = side[nod] ^ (ini[elem] == '0'); 278 dfs(oth); 279 } 280 } 281 } 282 283 int main() 284 { 285 ios::sync_with_stdio(false); 286 cin.tie(0); 287 cin >> nbElem >> nbSub; 288 cin >> ini; 289 fill(side,side+lim,-1); 290 iota(drepr,drepr+lim,0); 291 fill_n(&isIn[0][0], 2*lim, -1); 292 293 for (int sub = 0; sub < nbSub; ++sub) { 294 int st; cin >> st; 295 subset[sub].resize(st); 296 for (int pos = 0; pos < st; ++pos) { 297 int elem; cin >> elem; --elem; 298 subset[sub][pos] = elem; 299 if (isIn[elem][0] == -1) isIn[elem][0] = sub; 300 else isIn[elem][1] = sub; 301 } 302 } 303 304 for (int sub = 0; sub < nbSub; ++sub) { 305 if (side[sub] == -1) { 306 side[sub] = 0; 307 dfs(sub); 308 } 309 } 310 311 for (int elem = 0; elem < nbElem; ++elem) { 312 int n0 = isIn[elem][0], n1 = isIn[elem][1]; 313 if (n0 != -1 && n1 == -1) { 314 int destroy = side[n0] ^ (ini[elem] == '0'); 315 if (destroy == 1) add(n0, 0, lim); 316 else add(n0, lim, 0); 317 } else if (n0 != -1) { 318 dmerge(n0, n1); 319 } 320 cout << rep << "\n"; 321 } 322 } 323 ``` 324 325 **Implementation (dynamic bipartite DSU)** 326 327 ``` 328 #include <bits/stdc++.h> 329 #define fi first 330 #define se second 331 using namespace std; 332 333 const int N = 1E6 + 5, K = 1E6 + 5, INF = 1E9 + 7; 334 335 int n, k, c, v, ans = 0, dsu[K]; 336 char s[N]; 337 vector<int> adj[N]; 338 339 struct node { 340 int l, r, xo; 341 342 node(int _l = 0, int _r = 0, int _xo = 0) : l(_l), r(_r), xo(_xo) {} 343 344 int get() { 345 return min(l, r); 346 } 347 348 inline void operator+=(node oth) { 349 l = min(INF, l + oth.l); 350 r = min(INF, r + oth.r); 351 } 352 } val[K]; 353 354 pair<int, int> trace(int u) { 355 if (dsu[u] < 0) { 356 return {u, 0}; 357 } else { 358 pair<int, int> tmp = trace(dsu[u]); 359 dsu[u] = tmp.fi; 360 val[u].xo ^= tmp.se; 361 return {dsu[u], val[u].xo}; 362 } 363 } 364 365 int main() { 366 ios_base::sync_with_stdio(false); 367 cin.tie(nullptr); 368 cin >> n >> k >> (s + 1); 369 for (int i = 1; i <= k; i++) { 370 dsu[i] = -1; 371 val[i] = node(1, 0, 0); 372 cin >> c; 373 while (c--) { 374 cin >> v; 375 adj[v].push_back(i); 376 } 377 } 378 for (int i = 1; i <= n; i++) { 379 int typ = (s[i] - '0') ^ 1; 380 if (ans != -1) { 381 if (adj[i].size() == 1) { 382 pair<int, int> u = trace(adj[i][0]); 383 ans -= val[u.fi].get(); 384 val[u.fi] += node((u.se == typ) * INF, (u.se != typ) * INF); 385 ans += val[u.fi].get(); 386 } else if (adj[i].size() == 2) { 387 pair<int, int> u = trace(adj[i][0]); 388 pair<int, int> v = trace(adj[i][1]); 389 if (u.fi != v.fi) { 390 ans -= val[u.fi].get() + val[v.fi].get(); 391 if (dsu[u.fi] > dsu[v.fi]) { 392 swap(u, v); 393 } 394 if (u.se ^ v.se ^ typ) { 395 swap(val[v.fi].l, val[v.fi].r); 396 val[v.fi].xo = 1; 397 } 398 dsu[u.fi] += dsu[v.fi]; 399 dsu[v.fi] = u.fi; 400 val[u.fi] += val[v.fi]; 401 ans += val[u.fi].get(); 402 } 403 } 404 } 405 cout << ans << '\n'; 406 } 407 } 408 ``` 409 410 [1290D - Coffee Varieties (hard version)](/contest/1290/problem/D "Codeforces Round 616 (Div. 1)") 411 412 Author: [hugopm](/profile/hugopm "International Master hugopm") 413 414 **Tutorial** 415 416 Tutorial is loading... 417 418 **Implementation** 419 420 ``` 421 #include <bits/stdc++.h> 422 using namespace std; 423 424 bool ask(int pos) 425 { 426 cout << "? " << pos+1 << endl << flush; 427 char c; cin >> c; 428 if (c == 'E') exit(0); 429 return (c == 'Y'); 430 } 431 432 int main() 433 { 434 int nbElem, memSize, nbBlocks; 435 cin >> nbElem >> memSize; 436 nbBlocks = nbElem / memSize; 437 438 vector<bool> isAlive(nbElem, true); 439 440 for (int startBlock = 0; startBlock < nbBlocks; ++startBlock) { 441 int delta = 0; 442 cout << "R" << endl << flush; 443 for (int iDo = 0; iDo < nbBlocks; ++iDo) { 444 int curBlock = (startBlock+delta+nbBlocks) % nbBlocks; 445 int st = curBlock*memSize; 446 for (int elem = st; elem < st+memSize; ++elem) { 447 if (isAlive[elem]) { 448 if (ask(elem)) isAlive[elem] = false; 449 } 450 } 451 452 if (delta >= 0) ++delta; 453 delta = -delta; 454 } 455 } 456 457 int nbAlive = count(isAlive.begin(), isAlive.end(), true); 458 cout << "! " << nbAlive << endl << flush; 459 } 460 ``` 461 462 [1290E - Cartesian Tree](/contest/1290/problem/E "Codeforces Round 616 (Div. 1)") 463 464 Author: [gamegame](/profile/gamegame "International Grandmaster gamegame") 465 466 **Tutorial** 467 468 Tutorial is loading... 469 470 **Implementation** 471 472 ``` 473 #include<bits/stdc++.h> 474 using namespace std; 475 typedef long long ll; 476 const int N=3e5+1; 477 const int ts=1<<21; 478 int n; 479 ll mx[ts],se[ts],mxc[ts];//max, 2nd max, max count 480 int sz; 481 ll ch[N];//which values are changed 482 ll df[N];//change in frequency 483 void pass(int id,int c){ 484 if(mx[c]>mx[id]) mx[c]=mx[id]; 485 } 486 void push(int id){ 487 pass(id,id*2); 488 pass(id,id*2+1); 489 } 490 void pull(int id){ 491 mx[id]=max(mx[id*2],mx[id*2+1]); 492 mxc[id]=0; 493 if(mx[id]==mx[id*2]) mxc[id]+=mxc[id*2]; 494 if(mx[id]==mx[id*2+1]) mxc[id]+=mxc[id*2+1]; 495 se[id]=max(se[id*2],se[id*2+1]); 496 if(mx[id*2]!=mx[id]) se[id]=max(se[id],mx[id*2]); 497 if(mx[id*2+1]!=mx[id]) se[id]=max(se[id],mx[id*2+1]); 498 } 499 void upd(int id,int l,int r,int ql,int qr,int v){ 500 if(l>qr || r<ql || mx[id]<=v) return; 501 if(ql<=l && r<=qr && se[id]<v){ 502 ch[++sz]=mx[id];df[mx[id]]-=mxc[id]; 503 mx[id]=v; 504 ch[++sz]=mx[id];df[mx[id]]+=mxc[id]; 505 return; 506 } 507 push(id); 508 int mid=(l+r)/2; 509 upd(id*2,l,mid,ql,qr,v); 510 upd(id*2+1,mid+1,r,ql,qr,v); 511 pull(id); 512 } 513 void upd2(int id,int l,int r,int p,int v){ 514 if(l==r){ 515 ch[++sz]=mx[id];df[mx[id]]-=mxc[id]; 516 mx[id]=v; 517 ch[++sz]=mx[id];df[mx[id]]+=mxc[id]; 518 return; 519 } 520 push(id); 521 int mid=(l+r)/2; 522 if(p<=mid) upd2(id*2,l,mid,p,v); 523 else upd2(id*2+1,mid+1,r,p,v); 524 pull(id); 525 } 526 void build(int id,int l,int r){ 527 mx[id]=0;mxc[id]=r-l+1;se[id]=-1e9; 528 if(l==r) return; 529 int mid=(l+r)/2; 530 build(id*2,l,mid); 531 build(id*2+1,mid+1,r); 532 } 533 ///////////////////////////////////////////////// 534 ll bit1[N],bit2[N]; 535 void bupd1(int id,ll v){ 536 for(int i=id; i<=n ;i+=i&-i) bit1[i]+=v; 537 } 538 void bupd2(int id,ll v){ 539 for(int i=id; i<=n ;i+=i&-i) bit2[i]+=v; 540 } 541 ll bqry1(int id){ 542 ll res=0; 543 for(int i=id; i>=1 ;i-=i&-i) res+=bit1[i]; 544 return res; 545 } 546 ll bqry2(int id){ 547 ll res=0; 548 for(int i=id; i>=1 ;i-=i&-i) res+=bit2[i]; 549 return res; 550 } 551 int a[N],p[N]; 552 ll ans[N]; 553 set<int>s,t; 554 void magic(int mg){ 555 s.clear();t.clear();build(1,1,n); 556 for(int i=1; i<=n ;i++) bit1[i]=bit2[i]=0; 557 s.insert(p[1]);//set of existed elements 558 t.insert(p[1]);//set of l that maxr[] is not null 559 bupd1(p[1],1); 560 int mx=p[1];//largest existed position 561 upd2(1,1,n,p[1],p[1]); 562 bupd2(p[1],-1); 563 ll tot=-1; 564 for(int i=2; i<=n ;i++){ 565 int cur=p[i]; 566 auto it=s.lower_bound(cur); 567 bool rm=(it==s.end());//new element is rightmost 568 int nxt=0; 569 if(!rm) nxt=*it;//next 570 if(it==s.begin()){//new element is leftmost 571 tot-=bqry1(cur);bupd2(cur,-1); 572 t.insert(cur); 573 upd2(1,1,n,cur,mx); 574 } 575 else{ 576 int prv=*(--it); 577 upd(1,1,n,1,prv,prv); 578 if(rm) mx=cur; 579 else{ 580 upd2(1,1,n,nxt,mx); 581 if(t.find(nxt)==t.end()){ 582 tot-=bqry1(nxt);bupd2(nxt,-1); 583 t.insert(nxt); 584 } 585 } 586 upd2(1,1,n,*s.begin(),mx); 587 } 588 s.insert(cur); 589 tot+=bqry2(n)-bqry2(cur-1); 590 bupd1(cur,1); 591 for(int j=1; j<=sz ;j++){ 592 if(ch[j]!=0 && df[ch[j]]!=0){ 593 tot+=df[ch[j]]*bqry1(ch[j]); 594 bupd2(ch[j],df[ch[j]]); 595 df[ch[j]]=0; 596 } 597 } 598 sz=0; 599 ans[i]+=tot; 600 } 601 } 602 void solve(){ 603 for(int i=1; i<=n ;i++){ 604 p[a[i]]=i;ans[i]=0; 605 } 606 magic(1); 607 for(int i=1; i<=n ;i++) p[i]=n+1-p[i]; 608 magic(0); 609 for(int i=1; i<=n ;i++) ans[i]+=1; 610 for(int i=1; i<=n ;i++) cout << ans[i] << '\n'; 611 } 612 int main(){ 613 ios::sync_with_stdio(false); 614 cin >> n; 615 for(int i=1; i<=n ;i++) cin >> a[i]; 616 solve(); 617 } 618 ``` 619 620 [1290F - Making Shapes](/contest/1290/problem/F "Codeforces Round 616 (Div. 1)") 621 622 Author: [Kuroni](/profile/Kuroni "International Grandmaster Kuroni") 623 624 **Tutorial** 625 626 Tutorial is loading... 627 628 **Implementation** 629 630 ``` 631 #include <bits/stdc++.h> 632 using namespace std; 633 634 const int N = 5, MX = 4 * N, LG = 31, MOD = 998244353; 635 636 int n, m, x[N], y[N]; 637 int px[1 << N], nx[1 << N], py[1 << N], ny[1 << N]; 638 int dp[LG][MX][MX][MX][MX][2][2]; 639 640 void add(int &x, int y) { 641 x += y; 642 if (x >= MOD) { 643 x -= MOD; 644 } 645 } 646 647 int main() { 648 ios_base::sync_with_stdio(false); 649 cin.tie(nullptr); 650 cin >> n >> m; 651 for (int i = 0; i < n; i++) { 652 cin >> x[i] >> y[i]; 653 } 654 for (int msk = 0; msk < (1 << n); msk++) { 655 for (int i = 0; i < n; i++) { 656 if (msk >> i & 1) { 657 (x[i] < 0 ? nx : px)[msk] += abs(x[i]); 658 (y[i] < 0 ? ny : py)[msk] += abs(y[i]); 659 } 660 } 661 } 662 int mpx = max(1, px[(1 << n) - 1]); 663 int mpy = max(1, py[(1 << n) - 1]); 664 int mnx = max(1, nx[(1 << n) - 1]); 665 int mny = max(1, ny[(1 << n) - 1]); 666 dp[0][0][0][0][0][0][0] = 1; 667 for (int lg = 0; (1 << lg) <= m; lg++) { // bit position 668 for (int cpx = 0; cpx < mpx; cpx++) { // carry of positive x 669 for (int cpy = 0; cpy < mpy; cpy++) { // carry of positive y 670 for (int cnx = 0; cnx < mnx; cnx++) { // carry of negative x 671 for (int cny = 0; cny < mny; cny++) { // carry of negative y 672 for (int sx = 0; sx < 2; sx++) { // is the suffix of x greater than the suffix of m 673 for (int sy = 0; sy < 2; sy++) { // is the suffix of y greater than the suffix of m 674 for (int msk = 0; msk < (1 << n); msk++) { // iterating over the mask of the current bit position 675 int spx = cpx + px[msk]; 676 int spy = cpy + py[msk]; 677 int snx = cnx + nx[msk]; 678 int sny = cny + ny[msk]; 679 if (((spx ^ snx) & 1) || ((spy ^ sny) & 1)) { 680 continue; 681 } 682 int bx = spx & 1, by = spy & 1; 683 int nsx = (bx < (m >> lg & 1) ? 0 : bx > (m >> lg & 1) ? 1 : sx); 684 int nsy = (by < (m >> lg & 1) ? 0 : by > (m >> lg & 1) ? 1 : sy); 685 add(dp[lg + 1][spx / 2][spy / 2][snx / 2][sny / 2][nsx][nsy], dp[lg][cpx][cpy][cnx][cny][sx][sy]); 686 } 687 } 688 } 689 } 690 } 691 } 692 } 693 } 694 cout << (dp[__lg(m) + 1][0][0][0][0][0][0] + MOD - 1) % MOD << '\n'; 695 } 696 ``` 697 698 #### Theme and easter eggs 699 700 **Spoilers** 701 702 Oh boi this is gonna be interesting ( ͡° ͜ʖ ͡°) 703 704 The theme of the contest can be found by concatenating the first letter of each paragraph of the announcement ( ͡° ͜ʖ ͡°) From now on, we will refer to six-digit codes found in each problem statement as "sauce". ( ͡° ͜ʖ ͡°) 705 706 For [1291A - Even But Not Even](/contest/1291/problem/A "Codeforces Round 616 (Div. 2)"), the obvious sauces are $177013$ and $265918$. Along with this, break down the really long number in the sample input, you will get 4 sauces: $222373$, $204424$, $185217$, and $171912$. 707 708 For [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)"), the sauces are $282865$, $256988$ (found as inline examples for non-sharpened arrays), and $248618$ (found in the sample input). 709 710 For [1290A - Mind Control](/contest/1290/problem/A "Codeforces Round 616 (Div. 1)"), the sauces are $292385$ and $213604$ (found in the sample input). 711 712 For [1290B - Irreducible Anagrams](/contest/1290/problem/B "Codeforces Round 616 (Div. 1)"), look at the second sample input. There are 6 queries, concatenate $l$ and $r$ of all queries to get $122153$ and $242975$. 713 714 For [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)"), the binary string of the last sample input encodes a sauce into binary. Decode it into decimal to get $299782$. Fun side note, while developing this problem, the intended sauce was $299742$, but I typed in the wrong code to the binary converter. It turned out to be better btw. ( ͡° ͜ʖ ͡°) 715 716 For [1290D - Coffee Varieties (hard version)](/contest/1290/problem/D "Codeforces Round 616 (Div. 1)"), the ? queries of the second sample output gives you $264525$. Additionally, the ! query gives you page $6$ of the sauce. ( ͡° ͜ʖ ͡°) 717 718 For [1290E - Cartesian Tree](/contest/1290/problem/E "Codeforces Round 616 (Div. 1)") , the permutation of the second sample input gives you $124563$. 719 720 For [1290F - Making Shapes](/contest/1290/problem/F "Codeforces Round 616 (Div. 1)"), the third sample output gives you the sauce $296161$. 721 722 **UPD**: As I write these lines, $300000$ has been born. So unironically, the constraints of [1291B - Array Sharpening](/contest/1291/problem/B "Codeforces Round 616 (Div. 2)") and [1290C - Prefix Enlightenment](/contest/1290/problem/C "Codeforces Round 616 (Div. 1)") are now sauces. ( ͡° ͜ʖ ͡°) 723 724 Hope you have fun with the easter eggs we provided. ( ͡~ ͜ʖ ͡°)