2129.md (51640B)
1 Source: https://codeforces.com/blog/entry/145152 2 3 Thank you for participation and we hope you enjoy this round :) 4 5 **How did you find the contest?** 6 7 * Great: 8 * Good: 9 * Average: 10 * Bad: 11 * Trash: 12 13 **Which problem is your most favourite?** 14 15 * D2A: 16 * D2B: 17 * D1A: 18 * D1B: 19 * D1C1: 20 * D1C2: 21 * D1C3: 22 * D1D: 23 * D1E: 24 * D1F1: 25 * D1F2: 26 27 **Which problem you hate the most?** 28 29 * D2A: 30 * D2B: 31 * D1A: 32 * D1B: 33 * D1C1: 34 * D1C2: 35 * D1C3: 36 * D1D: 37 * D1E: 38 * D1F1: 39 * D1F2: 40 41 #### [D2A Submission is All You Need](https://codeforces.com/contest/2130/problem/A) 42 43 **Fun** 44 45 Do you know the source of the title? 46 47 **Hint 1** 48 49 Assuming that choosing $\text{mex(S')}$ is optimal, what conditions does $S'$ need to satisfy? 50 51 **Hint 2** 52 53 Are there duplicate numbers in $S'$? Is there a number greater than $\text{mex(S')}$ in $S'$? 54 55 **Tutorial** 56 57 Assuming that choosing $\text{mex(S')}$ is optimal, there are no duplicate numbers in $S'$. And thers is not a number greater than $\text{mex(S')}$. Otherwise, we can easily construct a better answer. 58 59 Consider $\text{S={0,1,...,x}}$. We can see $\text{mex(S')} \gt \text{max(S')}$ when $x$ is $0$ or $1$. And $\text{mex({0,1})}=\text{mex({0})}+\text{sum({1})}$. Thus, we only use $\text{mex}$ operation for each single $0$. 60 61 The answer is $\text{sum(S)}$ add the number of $0$ in $S$. 62 63 **solution** 64 65 ``` 66 #include <bits/stdc++.h> 67 using namespace std; 68 69 void solve(){ 70 int n, tmp, ans = 0; 71 cin >> n; 72 for(int i=0; i<n; i++){cin >> tmp; ans += tmp + (tmp == 0);} 73 cout << ans << '\n'; 74 } 75 76 int main(){ 77 ios::sync_with_stdio(false); 78 cin.tie(NULL); 79 int t; 80 cin >> t; 81 while(t--) solve(); 82 } 83 ``` 84 85 **Rate the Problem** 86 87 Amazing problem: 88 89 Good problem: 90 91 Average problem: 92 93 Bad problem: 94 95 Didn't solve: 96 97 #### [D2B Pathless](https://codeforces.com/contest/2130/problem/B) 98 99 **Hint1** 100 101 Casework. Consider two easy cases first: $\Sigma a \gt s$ and $\Sigma a=s$. 102 103 **Hint2** 104 105 What if there is an index $i$ such that $a_i+a_{i+1}=1$? 106 107 **Hint3** 108 109 To "block" $a_i+a_{i+1}=1$, what should Bob do? 110 111 **Hint4** 112 113 Consider cases of $\Sigma a=s+1$ and $\Sigma a \gt s+1$. 114 115 **Tutorial** 116 117 The minimum path sum is the sum of the simple path from $1$ to $n$ (i.e., $1 \rightarrow 2 \rightarrow \dots \rightarrow n$), denoted as $\text{base_sum} = \sum_{i=1}^{n} a_i$. 118 119 The path can include back-and-forth movements (e.g., from $i$ to $i+1$ and back to $i$), which increases the path length and the path sum. Specifically, each back-and-forth movement between adjacent positions $(i, i+1)$ adds $a_i + a_{i+1}$ to the path sum. 120 121 Thus, the total path sum can be expressed as $\text{base_sum} + d$, where $d$ is the additional sum contributed by zero or more back-and-forth movements. Here, $d$ can be represented as a non-negative integer linear combination of the sums of adjacent pairs. 122 123 Casework: 124 125 * If $s \lt \text{base_sum}$, no path sum can equal $s$ (since the base sum already exceeds $k$, and any additional movements will further increase the sum). 126 * If $s = \text{base_sum}$, the simple path ($1 \rightarrow 2 \rightarrow \dots \rightarrow n$) already satisfies the condition, so Alice cannot be stopped. 127 * If $s \gt \text{base_sum}$, let $d = s - \text{base_sum}$: 128 129 + If $d = 1$, we can rearrange the array to avoid adjacent pairs summing to $1$ (i.e., avoid $0$ and $1$ being adjacent). Specifically, place all $0$s first, followed by all $2$s, and then all $1$s (e.g., $[0, 0, \dots, 0, 2, 2, \dots, 2, 1, 1, \dots, 1]$). This ensures no adjacent pair sums to $1$, making $d = 1$ unachievable. 130 + If $d \neq 1$, no rearrangement can prevent Alice from achieving the path sum $s$ (since sums of adjacent pairs can cover all $T \geq 2$ through linear combinations). 131 132 **solution** 133 134 ``` 135 #include <bits/stdc++.h> 136 using namespace std; 137 138 void solve(){ 139 int n, k, tmp; 140 cin >> n >> k; 141 vector<int> a(3); 142 for(int i=0; i<n; i++){cin >> tmp; a[tmp]++;} 143 if(k == a[1] + 2*a[2] || k >= a[1] + 2*a[2] + 2){cout << -1 << '\n'; return;} 144 for(int i=0; i<a[0]; i++) cout << 0 << ' '; 145 for(int i=0; i<a[2]; i++) cout << 2 << ' '; 146 for(int i=0; i<a[1]; i++) cout << 1 << ' '; 147 cout << '\n'; 148 } 149 150 int main(){ 151 ios::sync_with_stdio(false); 152 cin.tie(NULL); 153 int t; 154 cin >> t; 155 while(t--) solve(); 156 } 157 ``` 158 159 **Rate the Problem** 160 161 Amazing problem: 162 163 Good problem: 164 165 Average problem: 166 167 Bad problem: 168 169 Didn't solve: 170 171 #### [D1A Double Perspective](https://codeforces.com/contest/2129/problem/A) 172 173 **Hint1** 174 175 Assuming that choosing $S$ is optimal, what is the value of $g(S)$? 176 177 **Hint2** 178 179 In the case of $g(S)=0$, make $f(S)$ the length of the union of the entire set. 180 181 **Tutorial** 182 183 Assuming that choosing $S$ is optimal, $g(S)$ must be $0$ because removing an edge on the cycle will not change $f(S)$. 184 185 In the case of $g(S)=0$, we need to make $f(S)$ the length of the union of the entire set. There are many approaches. 186 187 An easiest $O(n^2)$ approach is to remove all segments contained by other segments. Afterwards, it can be proven that there are no cycles with a length greater than or equal to $3$ in the graph. If there is a cycle, note it as $x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow ... \rightarrow x_1$, we can always find $x_{i-1} \lt x_i \gt x_{i+1}$, where either $[x_{i-1},x_i] \subseteq [x_i,x_{i+1}]$ or $[x_i,x_{i+1}] \subseteq [x_{i-1},x_i]$. At this point, we have deduced the contradiction, so there are no cycles with a length greater than or equal to $3$ in the graph. 188 189 Another approach is to use DSU to maintain the generate forest. 190 191 **solution** 192 193 ``` 194 #include <map> 195 #include <set> 196 #include <cmath> 197 #include <ctime> 198 #include <queue> 199 #include <stack> 200 #include <cstdio> 201 #include <cstdlib> 202 #include <vector> 203 #include <cstring> 204 #include <algorithm> 205 #include <iostream> 206 #include <bitset> 207 #include <unordered_map> 208 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 209 using namespace std; 210 typedef double db; 211 typedef long long ll; 212 typedef unsigned long long ull; 213 const int N=1000010; 214 int T,n; 215 int a[N],b[N]; 216 217 void init() 218 { 219 cin>>n; 220 for(int i=1;i<=n;i++) 221 cin>>a[i]>>b[i]; 222 } 223 224 void solve() 225 { 226 vector<int> tag(n+4,1),ans; 227 for(int i=1;i<=n;i++) 228 { 229 for(int j=1;j<=n;j++) 230 { 231 if(i==j) continue; 232 if(a[j]<=a[i]&&b[i]<=b[j]) tag[i]=0; 233 } 234 if(tag[i]) ans.push_back(i); 235 } 236 cout<<ans.size()<<"\n"; 237 for(int i=0;i<ans.size();i++) 238 cout<<ans[i]<<(i+1==ans.size()?"\n":" "); 239 } 240 241 int main() 242 { 243 fastio; 244 245 cin>>T; 246 while(T--) 247 { 248 init(); 249 solve(); 250 } 251 252 return 0; 253 } 254 ``` 255 256 **Rate the Problem** 257 258 Amazing problem: 259 260 Good problem: 261 262 Average problem: 263 264 Bad problem: 265 266 Didn't solve: 267 268 #### [D1B Stay or Mirror](https://codeforces.com/contest/2129/problem/B) 269 270 **Hint1** 271 272 Consider $p_i=1$. If $a_i=1$, what are inversions containing $i$? If $a_i=2n-1$, what are inversions containing $i$? 273 274 **Hint2** 275 276 Attempt to generalize the conclusion to any pair $(i, j)$. 277 278 **Tutorial** 279 280 Consider $p_i=1$ and inversions containing $i$. If $a_i=1$, it is the minimum value, and the inversions containing $i$ are $(1, i), (2, i),... (i-1, i)$; If $a_i=2n-1$, it is the maximum value, and the inversions containing $i$ are $(i, i+1),... (i, n)$. The key observation is the number of inversions containing $i$ is only related to $a_i$, and completely unrelated to other elements. 281 282 At this point, the problem has actually been solved. We can greedily choose $\min(i-1,n-i)$ and remove $1$ from $p$, and the remaining part is a completely identical subproblem with a size of $n-1$. 283 284 It can be implemented as follows: for each index $i$, calculate the number of elements to the left that are bigger than $p_i$ (note it as $lbigger$), and the number of elements to the right that are bigger than $p_i$ (note it as $rbigger$). Then greedily add $\min(lbigger,rbigger)$ to the answer. 285 286 **solution** 287 288 ``` 289 #include <bits/stdc++.h> 290 using namespace std; 291 292 void solve(){ 293 int n, ans = 0; 294 cin >> n; 295 vector<int> p(n); 296 for(int i=0; i<n; i++) cin >> p[i]; 297 for(int i=0; i<n; i++){ 298 int left = 0, right = 0; 299 for(int j=0; j<i; j++) if(p[j] > p[i]) left++; 300 for(int j=i+1; j<n; j++) if(p[j] > p[i]) right++; 301 ans += min(left, right); 302 } 303 cout << ans << '\n'; 304 } 305 306 int main(){ 307 ios::sync_with_stdio(false); 308 cin.tie(NULL); 309 int t; 310 cin >> t; 311 while(t--) solve(); 312 } 313 ``` 314 315 **Rate the Problem** 316 317 Amazing problem: 318 319 Good problem: 320 321 Average problem: 322 323 Bad problem: 324 325 Didn't solve: 326 327 #### [D1C1 Interactive RBS (Easy Version)](https://codeforces.com/contest/2129/problem/C1), [D1C2 Interactive RBS (Medium Version)](https://codeforces.com/contest/2129/problem/C2) and [D1C3 Interactive RBS (Hard Version)](https://codeforces.com/contest/2129/problem/C3) 328 329 **Hint1** 330 331 Try to Perform binary search to find a $\texttt{'('}$ and a $\texttt{')'}$ using $O(\log n)$ queries. It is best to complete it within $10$ operations (to pass the hard version). 332 333 **Hint2** 334 335 Consider the easy version. Constraint implies that we use one query to determine $2$ characters. 336 337 **Hint3** 338 339 Construct a string $x$, insert $s_i$ and $s_j$ into certain positions of $x$ to obtain string $y$, so that $f(y)$ can produce $4$ different values. 340 341 **Hint4** 342 343 Consider the medium version. Effectively utilizing the conditions of $k \le 1000$. 344 345 **Hint5** 346 347 Consider binary code. 348 349 **Hint6** 350 351 Consider the hard version. The number of substrings in a string of length $l$ is $O(l ^ 2)$. How to utilize this? 352 353 **Tutorial (easy version)** 354 355 At first, we need to find $s_x=\texttt{’(’}$ and $s_y=\texttt{’)’}$. Do binary search to find the smallest $i$ such that $f(s_1s_2...s_i) \gt 0$. Then we get $s_{i-1}=\texttt{’(’}$ and $s_i=\texttt{’)’}$. A corner case is $f(s)=0$. In this case, $s_n=\texttt{’(’}$ and $s_1=\texttt{’)’}$. 356 357 Ask $f(\texttt{"s1)s2)()"})$: 358 359 * If $f(\texttt{"s1)s2)()"})=6$, $s_1=$ $\texttt{'('}$ and $s_2=$ $\texttt{'('}$. 360 * If $f(\texttt{"s1)s2)()"})=2$, $s_1=$ $\texttt{'('}$ and $s_2=$ $\texttt{')'}$. 361 * If $f(\texttt{"s1)s2)()"})=3$, $s_1=$ $\texttt{')'}$ and $s_2=$ $\texttt{'('}$. 362 * If $f(\texttt{"s1)s2)()"})=1$, $s_1=$ $\texttt{')'}$ and $s_2=$ $\texttt{')'}$. 363 364 In this way, we can determine two characters with one query. 365 366 **Tutorial (medium version)** 367 368 Read the tutorial in easy version first. 369 370 Note $f_0$ as the $f$ value of the following string: 371 372 $\underbrace{()()\ldots()}_{128 pairs}$ $)$ $\underbrace{()()\ldots()}_{64 pairs}$ $)$ $\dots$ $)()$ 373 374 Then ask for the $f$ value of the following string (note it as $f_1$): 375 376 $\underbrace{s_8)()\ldots()}_{128 pairs}$ $)$ $\underbrace{s_7)()\ldots()}_{64 pairs}$ $)$ $\dots$ $)s_1)$ 377 378 By checking the binary bits of $f_0-f_1$, we can determine $8$ positions with one query. For example, if $f_0-f_1=(10000101)_2$, we can get $s_1=s_3=s_8=')'$. 379 380 **Tutorial (hard version)** 381 382 Read the tutorial of the medium version first. 383 384 We can optimize 385 386 $\underbrace{s_i)()\ldots()}_{2^k pairs}$ 387 388 to 389 390 $\underbrace{()()\ldots()}_{2^{\lfloor \frac{k}{2} \rfloor}-1\ pairs}$ $s_i)$ $\underbrace{()()\ldots()}_{2^{\lceil \frac{k}{2} \rceil}-1\ pairs}$ 391 392 With this optimization, we can determine $12$ locations in one query. 393 394 Another construction also works: 395 396 $\underbrace{s_1)s_1)\ldots s_1)}_{g(1)\ pairs}$ $)$ $\underbrace{s_2)s_2)\ldots s_2)}_{g(2)\ pairs}$ $)$ $\underbrace{s_3)s_3)\ldots s_3)}_{g(3)\ pairs}$ $)$ $\ldots$ $\underbrace{s_{12})s_{12})\ldots s_{12})}_{g(12)\ pairs}$ 397 398 where $g(1)=1$ and $\frac{g(i+1) \cdot (g(i+1)+1)}{2} \gt \frac{g(1) \cdot (g(1)+1)}{2}+\frac{g(2) \cdot (g(2)+1)}{2}+\ldots+\frac{g(i) \cdot (g(i)+1)}{2}$. 399 400 **solution (easy version)** 401 402 ``` 403 #include <bits/stdc++.h> 404 using namespace std; 405 406 typedef long long ll; 407 408 typedef long long ll; 409 typedef long double ld; 410 typedef pair<ll, ll> pll; 411 typedef pair<int, int> pii; 412 typedef vector<int> vi; 413 typedef vector<ll> vll; 414 415 const long long kk = 1000; 416 const long long ml = kk * kk; 417 const long long mod = ml * kk + 7; 418 const long long inf = ml * ml * ml + 7; 419 420 #define T(x, i) get<i>(x) 421 #define F first 422 #define S second 423 #define all(v) v.begin(), v.end() 424 #define forn(i, n) for (int i = 0; i < n; i++) 425 426 template<class T, class U> inline istream& operator>>(istream& str, pair<T, U> &p) { return str >> p.F >> p.S; } 427 template<class T, class U> inline ostream& operator<<(ostream& str, const pair<T, U> &p) { str << p.F << ' ' << p.S << ' '; return str; } 428 template<class T> inline istream& operator>>(istream& str, vector<T> &a) { for (auto &i : a) str >> i; return str; } 429 template<class T> inline ostream& operator<<(ostream& str, const vector<T> &a) { for (auto &i : a) str << i << ' '; return str; } 430 431 void flush() { cout << flush; } 432 void flushln() { cout << endl; } 433 template<class T> void read(T &x) { cin >> x; } 434 template<class T, class ...U> void read(T &x, U&... u) { read(x); read(u...); } 435 template<class T> void print(const T &x) { cout << x; } 436 template<class T, class ...U> void print(const T &x, const U&... u) { print(x); print(u...); } 437 template<class ...T> void println(const T&... u) { print(u..., '\n'); } 438 template<class T> void eprint(const T &x) { cerr << x; } 439 template<class T, class ...U> void eprint(const T &x, const U&... u) { eprint(x); eprint(u...); } 440 template<class ...T> void eprintln(const T&... u) { eprint(u..., '\n'); } 441 442 #ifdef DEBUG 443 mt19937 rng(1033); 444 #define var(x) cerr << #x << ": " << x << '\n'; 445 #define range(a, b) cerr << #a << ", " << #b << ": "; for (auto _it = a; _it != b; ++_it) cerr << *_it << ' '; cerr << '\n'; 446 #else 447 mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); 448 #define cerr if (false) cerr 449 #define var(x) 450 #define range(a, b) 451 #define eprintln if(false)eprintln 452 #define eprint if(false)eprint 453 #endif 454 int rnd(int mod) { return uniform_int_distribution<int>(0, mod - 1)(rng); } 455 456 int n; 457 458 map<vector<int>, int> mem; 459 460 int ask(vector<int> ind) { 461 if (!mem.count(ind)) { 462 cout << "? "; 463 cout << ind.size() << ' '; 464 for (auto i : ind) 465 cout << i + 1 << ' '; 466 cout << endl; 467 468 int res; 469 cin >> res; 470 mem[ind] = res; 471 } 472 473 return mem[ind]; 474 } 475 476 bool same(vector<int> ind) { 477 if (ask(ind)) 478 return false; 479 ind.push_back(ind[0]); 480 ind.erase(ind.begin()); 481 if (ask(ind)) 482 return false; 483 return true; 484 } 485 486 pii search(vector<int> ind) { 487 if (ind.size() == 2) { 488 if (ask(ind)) 489 return {ind[0], ind[1]}; 490 return {ind[1], ind[0]}; 491 } 492 493 vector<int> inda, indb; 494 int sz = (ind.size() + 1) / 2; 495 for (int i = 0; i < sz; i++) { 496 inda.push_back(ind[i]); 497 indb.push_back(ind[ind.size() - 1 - i]); 498 } 499 500 if (!same(inda)) 501 return search(inda); 502 if (!same(indb)) 503 return search(indb); 504 inda.push_back(indb[0]); 505 return search(inda); 506 } 507 508 pii find_reg2() { 509 vector<int> ind(n); 510 iota(all(ind), 0); 511 shuffle(all(ind), rng); 512 return search(ind); 513 } 514 515 void solve() { 516 mem.clear(); 517 auto [po, pc] = find_reg2(); 518 519 vector<int> to_ask(n); 520 iota(all(to_ask), 0); 521 if (to_ask.size() & 1) 522 to_ask.push_back(0); 523 524 string ans = string(n, '.'); 525 ans[po] = '('; 526 ans[pc] = ')'; 527 528 for (int i = 0; i < to_ask.size(); i += 2) { 529 int a = to_ask[i], b = to_ask[i + 1]; 530 531 vector<int> q = {po, pc, po, a, b, pc}; 532 int res = ask(q); 533 534 // ()(ab) - x ab 535 // ()(()) - 4 () 536 // ()((() - 2 (( 537 // ()())) - 3 )) 538 // ()()() - 6 )( 539 map<int, pair<char, char>> results = { 540 {4, {'(', ')'}}, 541 {2, {'(', '('}}, 542 {3, {')', ')'}}, 543 {6, {')', '('}}, 544 }; 545 546 assert(results.count(res)); 547 auto [resa, resb] = results[res]; 548 ans[a] = resa; 549 ans[b] = resb; 550 } 551 552 cout << "! " << ans << endl; 553 } 554 555 signed main() { 556 #ifdef DEBUG 557 // freopen("input.txt", "r", stdin); 558 // freopen("output.txt", "w", stdout); 559 #endif 560 ios_base::sync_with_stdio(0); cin.tie(0); 561 cout << fixed << setprecision(20); 562 int t = 1; 563 cin >> t; 564 for (int i = 0; i < t; i++) { 565 cin >> n; 566 solve(); 567 } 568 #ifdef DEBUG 569 cerr << "Runtime is: " << clock() * 1.0 / CLOCKS_PER_SEC << endl; 570 #endif 571 } 572 573 /* 574 575 ()(ab) 576 ()(()) - 4 () 577 ()((() - 2 (( 578 ()())) - 3 )) 579 ()()() - 6 )( 580 581 2 582 3 583 )(( 584 2 585 () 586 587 */ 588 ``` 589 590 **solution (medium version)** 591 592 ``` 593 #include <vector> 594 #include <list> 595 #include <map> 596 #include <set> 597 #include <deque> 598 #include <vector> 599 #include <list> 600 #include <map> 601 #include <set> 602 #include <deque> 603 #include <queue> 604 #include <stack> 605 #include <bitset> 606 #include <algorithm> 607 #include <functional> 608 #include <numeric> 609 #include <utility> 610 #include <sstream> 611 #include <iostream> 612 #include <iomanip> 613 #include <cstdio> 614 #include <cmath> 615 #include <cstdlib> 616 #include <cctype> 617 #include <string> 618 #include <cstring> 619 #include <ctime> 620 #include <random> 621 #include <chrono> 622 623 using namespace std; 624 625 #define _int64 long long 626 #define mo 998244353 627 628 char tar[110000]; 629 int cnt; 630 631 int doask(vector<int>& a) 632 { 633 int i,ret; 634 /* 635 { 636 int v,tmp,j; 637 string ss; 638 cnt++; 639 ss=""; 640 for (i=0;i<a.size();i++) 641 { 642 ss.push_back(tar[a[i]]); 643 } 644 tmp=0; 645 for (i=0;i<ss.length();i++) 646 { 647 v=0; 648 for (j=i;j<ss.length();j++) 649 { 650 if (ss[j]=='(') v++; 651 else v--; 652 if (v<0) break; 653 if (v==0) tmp++; 654 } 655 } 656 return tmp; 657 } 658 */ 659 660 printf("? %d",(int)a.size()); 661 for (i=0;i<a.size();i++) 662 printf(" %d",a[i]+1); 663 printf("\n"); 664 fflush(stdout); 665 scanf("%d",&ret); 666 return ret; 667 668 } 669 670 char ans[1100]; 671 672 void doanswer() 673 { 674 printf("! %s\n",ans); 675 cerr<<"T "<<tar<<endl; 676 cerr<<"cnt:"<<cnt<<endl; 677 if (string(ans)==string(tar)) 678 { 679 cerr<<"good"<<endl; 680 } 681 else cerr<<"bad"<<endl; 682 fflush(stdout); 683 } 684 685 int main() 686 { 687 int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st; 688 vector<int> a; 689 scanf("%d",&t); 690 for (l=0;l<t;l++) 691 { 692 scanf("%d",&n); 693 for (i=0;i<n;i++) 694 { 695 x=rand()%2; 696 if (x==0) tar[i]='('; 697 else tar[i]=')'; 698 } 699 tar[n]='\0'; 700 cnt=0; 701 st=0;ans[n]='\0'; 702 indl=-1; 703 indr=-1; 704 // while (st<n) 705 // { 706 ll=st;rr=n; 707 while (rr-ll>1) 708 { 709 mid=(ll+rr)/2; 710 a.clear(); 711 for (i=st;i<=mid;i++) 712 a.push_back(i); 713 tmp=doask(a); 714 if (tmp==0) ll=mid; 715 else rr=mid; 716 } 717 if (rr==n) 718 { 719 indr=st; 720 /* 721 if ((indl==-1)&&(indr==-1)) 722 { 723 indr=st; 724 } 725 ll=st-1;rr=n; 726 while (rr-ll>1) 727 { 728 mid=(ll+rr)/2; 729 a.clear(); 730 a.push_back(mid); 731 a.push_back(indr); 732 tmp=doask(a); 733 if (tmp==0) ll=mid; 734 else rr=mid; 735 } 736 for (i=st;i<=ll;i++) 737 ans[i]=')'; 738 for (i=rr;i<n;i++) 739 ans[i]='('; 740 st=n; 741 break; 742 */ 743 } 744 else 745 { 746 indr=rr; 747 /* 748 v=rr; 749 ans[v]=')'; 750 ll=st-1;rr=v-1; 751 while (rr-ll>1) 752 { 753 mid=(ll+rr)/2; 754 a.clear(); 755 a.push_back(mid); 756 a.push_back(v); 757 tmp=doask(a); 758 if (tmp==0) ll=mid; 759 else rr=mid; 760 } 761 for (i=st;i<=ll;i++) 762 ans[i]=')'; 763 for (i=rr;i<v;i++) 764 ans[i]='('; 765 st=v+1; 766 indl=v-1; 767 indr=v; 768 */ 769 } 770 // } 771 //cerr<<"indr:"<<indr<<endl; 772 for (i=0;i<n;i+=8) 773 { 774 a.clear(); 775 for (j=0;j<8;j++) 776 { 777 if (i+j>=n) break; 778 for (k=0;k<(1<<j);k++) 779 { 780 a.push_back(i+j); 781 a.push_back(indr); 782 a.push_back(indr); 783 } 784 } 785 tmp=doask(a); 786 for (j=0;j<8;j++) 787 { 788 if (i+j>=n) break; 789 if (((1<<j)&tmp)!=0) ans[i+j]='('; 790 else ans[i+j]=')'; 791 } 792 } 793 794 doanswer(); 795 } 796 } 797 ``` 798 799 **solution (hard version)** 800 801 ``` 802 #include <vector> 803 #include <list> 804 #include <map> 805 #include <set> 806 #include <deque> 807 #include <vector> 808 #include <list> 809 #include <map> 810 #include <set> 811 #include <deque> 812 #include <queue> 813 #include <stack> 814 #include <bitset> 815 #include <algorithm> 816 #include <functional> 817 #include <numeric> 818 #include <utility> 819 #include <sstream> 820 #include <iostream> 821 #include <iomanip> 822 #include <cstdio> 823 #include <cmath> 824 #include <cstdlib> 825 #include <cctype> 826 #include <string> 827 #include <cstring> 828 #include <ctime> 829 #include <random> 830 #include <chrono> 831 832 using namespace std; 833 834 #define _int64 long long 835 #define mo 998244353 836 837 char tar[110000]; 838 int cnt; 839 840 int doask(vector<int>& a) 841 { 842 int i,ret; 843 /* 844 { 845 int v,tmp,j; 846 string ss; 847 cnt++; 848 ss=""; 849 for (i=0;i<a.size();i++) 850 { 851 ss.push_back(tar[a[i]]); 852 } 853 tmp=0; 854 for (i=0;i<ss.length();i++) 855 { 856 v=0; 857 for (j=i;j<ss.length();j++) 858 { 859 if (ss[j]=='(') v++; 860 else v--; 861 if (v<0) break; 862 if (v==0) tmp++; 863 } 864 } 865 return tmp; 866 } 867 */ 868 869 printf("? %d",(int)a.size()); 870 for (i=0;i<a.size();i++) 871 printf(" %d",a[i]+1); 872 printf("\n"); 873 fflush(stdout); 874 scanf("%d",&ret); 875 return ret; 876 877 } 878 879 char ans[1100]; 880 881 void doanswer() 882 { 883 printf("! %s\n",ans); 884 cerr<<"T "<<tar<<endl; 885 cerr<<"cnt:"<<cnt<<endl; 886 if (string(ans)==string(tar)) 887 { 888 cerr<<"good"<<endl; 889 } 890 else cerr<<"bad"<<endl; 891 fflush(stdout); 892 } 893 894 int main() 895 { 896 int i,j,k,n,l,t,m,x,y,o,b1,indl,indr,ll,rr,mid,tmp,v,st,sum,len; 897 vector<int> a; 898 vector<int> p; 899 sum=0;len=0; 900 for (i=1;i<=130;i++) 901 { 902 tmp=i*(i+1)/2; 903 if (tmp>sum) 904 { 905 p.push_back(i); 906 //cerr<<"i:"<<i<<endl; 907 sum+=tmp; 908 len+=i+i; 909 } 910 } 911 //cerr<<"p.sz:"<<p.size()<<" "<<len<<endl; 912 scanf("%d",&t); 913 for (l=0;l<t;l++) 914 { 915 scanf("%d",&n); 916 for (i=0;i<n;i++) 917 { 918 x=rand()%2; 919 if (x==0) tar[i]='('; 920 else tar[i]=')'; 921 } 922 tar[n]='\0'; 923 cnt=0; 924 st=0;ans[n]='\0'; 925 indl=-1; 926 indr=-1; 927 // while (st<n) 928 // { 929 ll=st;rr=n; 930 while (rr-ll>1) 931 { 932 mid=(ll+rr)/2; 933 a.clear(); 934 for (i=st;i<=mid;i++) 935 a.push_back(i); 936 tmp=doask(a); 937 if (tmp==0) ll=mid; 938 else rr=mid; 939 } 940 if (rr==n) 941 { 942 indr=st; 943 /* 944 if ((indl==-1)&&(indr==-1)) 945 { 946 indr=st; 947 } 948 ll=st-1;rr=n; 949 while (rr-ll>1) 950 { 951 mid=(ll+rr)/2; 952 a.clear(); 953 a.push_back(mid); 954 a.push_back(indr); 955 tmp=doask(a); 956 if (tmp==0) ll=mid; 957 else rr=mid; 958 } 959 for (i=st;i<=ll;i++) 960 ans[i]=')'; 961 for (i=rr;i<n;i++) 962 ans[i]='('; 963 st=n; 964 break; 965 */ 966 } 967 else 968 { 969 indr=rr; 970 /* 971 v=rr; 972 ans[v]=')'; 973 ll=st-1;rr=v-1; 974 while (rr-ll>1) 975 { 976 mid=(ll+rr)/2; 977 a.clear(); 978 a.push_back(mid); 979 a.push_back(v); 980 tmp=doask(a); 981 if (tmp==0) ll=mid; 982 else rr=mid; 983 } 984 for (i=st;i<=ll;i++) 985 ans[i]=')'; 986 for (i=rr;i<v;i++) 987 ans[i]='('; 988 st=v+1; 989 indl=v-1; 990 indr=v; 991 */ 992 } 993 // } 994 //cerr<<"indr:"<<indr<<endl; 995 for (i=0;i<n;i+=p.size()) 996 { 997 a.clear(); 998 for (j=0;j<p.size();j++) 999 { 1000 if (i+j>=n) break; 1001 for (k=0;k<p[j];k++) 1002 { 1003 a.push_back(i+j); 1004 a.push_back(indr); 1005 } 1006 a.push_back(indr); 1007 } 1008 tmp=doask(a); 1009 for (j=p.size()-1;j>=0;j--) 1010 { 1011 if (i+j>=n) continue; 1012 v=p[j]*(p[j]+1)/2; 1013 if (tmp>=v) 1014 { 1015 tmp-=v;ans[i+j]='('; 1016 } 1017 else ans[i+j]=')'; 1018 } 1019 } 1020 1021 doanswer(); 1022 } 1023 } 1024 ``` 1025 1026 **Rate the Problem** 1027 1028 Amazing problem: 1029 1030 Good problem: 1031 1032 Average problem: 1033 1034 Bad problem: 1035 1036 Didn't solve: 1037 1038 #### [D1D Permutation Blackhole](https://codeforces.com/contest/2129/problem/D) 1039 1040 **Hint1** 1041 1042 Consider enumerating $p_i = 1$. After that, will the cells to the left of $p_i$ affect the cells to the right of $p_i$? 1043 1044 **Hint2** 1045 1046 Consider range DP. 1047 1048 **Hint3** 1049 1050 Can you find the upper bound of $s_i$? 1051 1052 **Tutorial** 1053 1054 Consider range DP. 1055 1056 Note $dp[l][r][x][y]$ as the number of scheme ensureing $s[l-1]+=x$ and $s[r+1]+=y$. 1057 1058 Transform: 1059 1060 $ 1061 1062 dp[l][r][x][y] = \left\{ \begin{array}{l} \Sigma_{\text{i is nearer to l}} \binom{r-l}{i-l} \cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{\text{i is nearer to r}} \binom{r-l}{i-l} \cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i = -1) \\ \Sigma_{\text{i is nearer to l},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x-1][j] \cdot dp[i+1][r][k][y] \\ + \Sigma_{ \text{i is nearer to r},\ j+k=s_i} \binom{r-l}{i-l}\cdot dp[l][i-1][x][j] \cdot dp[i+1][r][k][y-1]\ (s_i \neq -1) \end{array} \right. 1063 1064 $ 1065 1066 For simplicity, this formula omits some edge cases. Readers are encouraged to fill in the details themselves. 1067 1068 The complexity seems high, but the problem can be solved with one key observation: the upper bound of $s_i$ is $O( \log n)$. 1069 1070 Proof: let's fix a position $i$ and only consider the cells $c_1, c_2, ..., c_k$ $(c_1 \lt c_2 \lt ... \lt c_k)$ to the left of $i$ that cause $s_i$ to increase. We can see that $i - c_j \gt 2(i - c_{j+1})$. Otherwise, $c_{j+1}$ would cause $s_{c_j}$ to increase by $1$ instead of $s_i$. Thus, We can get $k$ is $O( \log n)$. 1071 1072 Complexity: $O(n^3 \log^3n)$. 1073 1074 **solution** 1075 1076 ``` 1077 #include <map> 1078 #include <set> 1079 #include <cmath> 1080 #include <ctime> 1081 #include <queue> 1082 #include <stack> 1083 #include <cstdio> 1084 #include <cstdlib> 1085 #include <vector> 1086 #include <cstring> 1087 #include <algorithm> 1088 #include <iostream> 1089 #include <bitset> 1090 #include <unordered_map> 1091 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 1092 using namespace std; 1093 typedef double db; 1094 typedef long long ll; 1095 typedef unsigned long long ull; 1096 const int N=110; 1097 const int LOGN=10; 1098 const ll TMD=998244353; 1099 const ll INF=2147483647; 1100 int T,n; 1101 ll s[N],fac[N],inv[N]; 1102 ll dp[N][N][LOGN][LOGN]; 1103 1104 void init_C() 1105 { 1106 fac[0]=1; 1107 for(int i=1;i<N;i++) fac[i]=(fac[i-1]*i)%TMD; 1108 inv[N-1]=pw(fac[N-1],TMD-2); 1109 for(int i=N-2;i>=0;i--) inv[i]=(inv[i+1]*(i+1))%TMD; 1110 } 1111 1112 ll C(int n,int m) 1113 { 1114 if(n<m||n<0||m<0) return 0; 1115 return fac[n]*inv[m]%TMD*inv[n-m]%TMD; 1116 } 1117 1118 void init() 1119 { 1120 cin>>n; 1121 for(int i=1;i<=n;i++) cin>>s[i]; 1122 for(int i=1;i<=n+4;i++) 1123 for(int j=1;j<=n+4;j++) 1124 for(int ii=0;ii<LOGN;ii++) 1125 for(int jj=0;jj<LOGN;jj++) 1126 dp[i][j][ii][jj]=0; 1127 dp[1][1][0][1]=(s[1]<1); 1128 for(int i=2;i<=n;i++) 1129 dp[i][i][1][0]=(s[i]<1); 1130 for(int i=1;i<=n;i++) //auxiliary value 1131 dp[i][i-1][0][0]=dp[i+1][i][0][0]=1; 1132 } 1133 1134 int ABS(int x) 1135 { 1136 return x<0?-x:x; 1137 } 1138 1139 void solve() 1140 { 1141 for(int i=2;i<=n;i++) 1142 { 1143 for(int j=1;j+i-1<=n;j++) 1144 { 1145 for(int ii=0;ii<LOGN;ii++) 1146 { 1147 for(int jj=0;jj<LOGN;jj++) 1148 { 1149 int l=j,r=j+i-1; 1150 for(int k=l;k<=r;k++) 1151 { 1152 int tagl=0,tagr=0; 1153 if(l==1&&r==n) tagl=tagr=0; 1154 else if(l==1) tagr=1; 1155 else if(r==n) tagl=1; 1156 else 1157 { 1158 if(ABS(l-1-k)<=ABS(k-(r+1))) tagl=1; 1159 else tagr=1; 1160 } 1161 if(ii-tagl<0||jj-tagr<0) continue; 1162 if(s[k]==-1) 1163 { 1164 ll suml=0,sumr=0; 1165 for(int kk=0;kk<LOGN;kk++) suml=(suml+dp[l][k-1][ii-tagl][kk])%TMD; 1166 for(int kk=0;kk<LOGN;kk++) sumr=(sumr+dp[k+1][r][kk][jj-tagr])%TMD; 1167 dp[l][r][ii][jj]=(dp[l][r][ii][jj]+suml*sumr%TMD*C(r-l,k-l))%TMD; 1168 } 1169 else 1170 { 1171 for(int kk=0;kk<LOGN;kk++) 1172 { 1173 if(s[k]-kk<0||s[k]-kk>=LOGN) continue; 1174 dp[l][r][ii][jj]=(dp[l][r][ii][jj]+dp[l][k-1][ii-tagl][kk]*dp[k+1][r][s[k]-kk][jj-tagr]%TMD*C(r-l,k-l))%TMD; 1175 } 1176 } 1177 } 1178 } 1179 } 1180 } 1181 } 1182 cout<<dp[1][n][0][0]<<'\n'; 1183 } 1184 1185 int main() 1186 { 1187 fastio; 1188 1189 init_C(); 1190 1191 cin>>T; 1192 while(T--) 1193 { 1194 init(); 1195 solve(); 1196 } 1197 1198 return 0; 1199 } 1200 ``` 1201 1202 **Rate the Problem** 1203 1204 Amazing problem: 1205 1206 Good problem: 1207 1208 Average problem: 1209 1210 Bad problem: 1211 1212 Didn't solve: 1213 1214 #### [D1E Induced Graph Queries](https://codeforces.com/contest/2129/problem/E) 1215 1216 **Fun** 1217 1218 Come up with an O(n log^4 n) solution using a persistent multidimensional segment tree with Trie that supports rectangle update XOR. 1219 1220 **Hint1** 1221 1222 Find the nature of the problem and recall the data structures and algorithms learned. What can we utilize? 1223 1224 **Hint2** 1225 1226 Consider a standard Mo's algorithm. Why it doesn't work in this problem? 1227 1228 **Hint3** 1229 1230 Recalling the Handshake Theorem: $\Sigma_{i=1}^n degree_i=2m$. 1231 1232 **Hint4** 1233 1234 Consider a variation of Mo's algorithm. 1235 1236 **Hint5** 1237 1238 How to find the $k$-th smallest value without $O( \log n)$ complexity? 1239 1240 **Tutorial** 1241 1242 We found that merging the $f$ values of two intervals is a bit difficult. However, if we want to add a single node to the graph, it is relatively easy to update the $f$ value using brute force. This inspires us to use the Mo's algorithm. 1243 1244 If we use the standard Mo's Algorithm, when expanding the interval from $[l, r]$ to $[l, r+1]$, we need to examine all edges connected to $r+1$ and update the node degrees accordingly. We define a cost array: $cost_i=degree_i+1$. The cost of update node $r+1$ is $cost_{r+1}$. 1245 1246 However, if a node has a high degree, repeatedly processing it in Mo's Algorithm could lead to big time complexity. 1247 1248 We leverage the Handshaking Lemma to use modified Mo's Algorithm to efficiently handle the queries. 1249 1250 Recall that the Mo's algorithm relatively evenly divides array indices into blocks according to array length and assigns block numbers. Here, our dividinging strategy is different: we "relatively evenly" divide the array into blocks based on the prefix sum value of the $cost$ array. Specifically, we calculate the prefix sum of the cost array $precost$, using $\frac{precost_i}{B}$ as the block number of node $i$, where $B$ is the block length parameter. 1251 1252 Assuming we have a data structure that can maintain the value of $k$-th smallest value in $O(1)$, using the same analysis method as standard Mo's algorithm, we can get the complexity is $O((n+m+q)\sqrt{n+m})$. 1253 1254 To find the $k$-th smallest value without $O( \log n)$ complexity, we only need to maintain two arrays $cnt$ and $sum$, where $cnt_i$ is the occurrence of value $i$, and $sum_i=\Sigma_{j=(i-1)B+1}^{iB}cnt_j$ ($B$ is the block length parameter). We can perform modification in $O(1)$ and query in $O(\sqrt{n})$. The complexity is $O((n+q)\sqrt{n})$. 1255 1256 Regarding implementation, you need to pay attention to two common pitfalls: 1257 1258 * If you use $cost_i=degree_i$ instead of $cost_i=degree_i+1$, the dividing algorithm doesn't work for the graph with many nodes with degree $0$. 1259 * Similarly, you can not set $B=\sqrt{m}$. 1260 1261 **solution** 1262 1263 ``` 1264 #include<bits/stdc++.h> 1265 using namespace std; 1266 1267 #define all(a) a.begin(),a.end() 1268 #define pb push_back 1269 #define sz(a) ((int)a.size()) 1270 1271 using ll=long long; 1272 using u32=unsigned int; 1273 using u64=unsigned long long; 1274 using i128=__int128; 1275 using u128=unsigned __int128; 1276 using f128=__float128; 1277 1278 using pii=pair<int,int>; 1279 using pll=pair<ll,ll>; 1280 1281 template<typename T> using vc=vector<T>; 1282 template<typename T> using vvc=vc<vc<T>>; 1283 template<typename T> using vvvc=vc<vvc<T>>; 1284 1285 using vi=vc<int>; 1286 using vll=vc<ll>; 1287 using vvi=vc<vi>; 1288 using vvll=vc<vll>; 1289 1290 #define vv(type,name,n,...) \ 1291 vector<vector<type>> name(n,vector<type>(__VA_ARGS__)) 1292 #define vvv(type,name,n,m,...) \ 1293 vector<vector<vector<type>>> name(n,vector<vector<type>>(m,vector<type>(__VA_ARGS__))) 1294 1295 template<typename T> using min_heap=priority_queue<T,vector<T>,greater<T>>; 1296 template<typename T> using max_heap=priority_queue<T>; 1297 1298 // https://trap.jp/post/1224/ 1299 #define rep1(n) for(ll i=0; i<(ll)(n); ++i) 1300 #define rep2(i,n) for(ll i=0; i<(ll)(n); ++i) 1301 #define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i) 1302 #define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c)) 1303 #define cut4(a,b,c,d,e,...) e 1304 #define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__) 1305 #define per1(n) for(ll i=((ll)n)-1; i>=0; --i) 1306 #define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i) 1307 #define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i) 1308 #define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c)) 1309 #define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__) 1310 #define rep_subset(i,s) for(ll i=(s); i>=0; i=(i==0?-1:(i-1)&(s))) 1311 1312 template<typename T, typename S> constexpr T ifloor(const T a, const S b){return a/b-(a%b&&(a^b)<0);} 1313 template<typename T, typename S> constexpr T iceil(const T a, const S b){return ifloor(a+b-1,b);} 1314 1315 template<typename T> 1316 void sort_unique(vector<T> &vec){ 1317 sort(vec.begin(),vec.end()); 1318 vec.resize(unique(vec.begin(),vec.end())-vec.begin()); 1319 } 1320 1321 template<typename T, typename S> constexpr bool chmin(T &a, const S b){if(a>b) return a=b,true; return false;} 1322 template<typename T, typename S> constexpr bool chmax(T &a, const S b){if(a<b) return a=b,true; return false;} 1323 1324 template<typename T, typename S> istream& operator >> (istream& i, pair<T,S> &p){return i >> p.first >> p.second;} 1325 template<typename T, typename S> ostream& operator << (ostream& o, const pair<T,S> &p){return o << p.first << ' ' << p.second;} 1326 1327 #ifdef i_am_noob 1328 #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) 1329 template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 1330 template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 1331 template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";} 1332 template<typename T> void _do(T && x) {cerr << x << endl;} 1333 template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} 1334 #else 1335 #define bug(...) 777771449 1336 #endif 1337 1338 template<typename T> void print(vector<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 1339 template<typename T> void print(set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 1340 template<typename T> void print(unordered_set<T> x){for(auto i: x) cout << i << ' ';cout << "\n";} 1341 template<typename T> void print(T && x) {cout << x << "\n";} 1342 template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);} 1343 1344 template<typename T> istream& operator >> (istream& i, vector<T> &vec){for(auto &x: vec) i >> x; return i;} 1345 1346 vvi read_graph(int n, int m, int base=1){ 1347 vvi adj(n); 1348 for(int i=0,u,v; i<m; ++i){ 1349 cin >> u >> v,u-=base,v-=base; 1350 adj[u].pb(v),adj[v].pb(u); 1351 } 1352 return adj; 1353 } 1354 1355 vvi read_tree(int n, int base=1){return read_graph(n,n-1,base);} 1356 1357 template<typename T, typename S> pair<T,S> operator + (const pair<T,S> &a, const pair<T,S> &b){return {a.first+b.first,a.second+b.second};} 1358 1359 template<typename T> constexpr T inf=0; 1360 template<> constexpr int inf<int> = 0x3f3f3f3f; 1361 template<> constexpr ll inf<ll> = 0x3f3f3f3f3f3f3f3f; 1362 1363 template<typename T> vector<T> operator += (vector<T> &a, int val){for(auto &i: a) i+=val; return a;} 1364 1365 template<typename T> T isqrt(const T &x){T y=sqrt(x+2); while(y*y>x) y--; return y;} 1366 1367 #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) 1368 1369 //#include<atcoder/all> 1370 //using namespace atcoder; 1371 1372 //using mint=modint998244353; 1373 //using mint=modint1000000007; 1374 1375 const int N=1<<18,K=1<<10; 1376 1377 struct DS{ 1378 int big[N/K],small[N]; 1379 void ins(int x){ 1380 small[x]++; 1381 big[x>>10]++; 1382 } 1383 void del(int x){ 1384 small[x]--; 1385 big[x>>10]--; 1386 } 1387 int kth(int k){ 1388 k--; 1389 int cur=0; 1390 while(big[cur]<=k) k-=big[cur++]; 1391 cur<<=10; 1392 while(small[cur]<=k) k-=small[cur++]; 1393 return cur; 1394 } 1395 }ds; 1396 1397 void ahcorz(){ 1398 int n,m; cin >> n >> m; 1399 vvi adj=read_graph(n,m); 1400 vi block(n); 1401 int cur=0; 1402 rep(n){ 1403 if(cur>=n) break; 1404 int tot=0; 1405 while(cur<n&&tot<K){ 1406 tot+=sz(adj[cur])+1; 1407 block[cur++]=i; 1408 } 1409 } 1410 int q; cin >> q; 1411 vc<array<int,4>> qq(q); 1412 vi res(q); 1413 rep(q){ 1414 int l,r,k; cin >> l >> r >> k; l--,r--; 1415 qq[i]={l,r,k,i}; 1416 } 1417 sort(all(qq),[&](array<int,4> arr1, array<int,4> arr2){ 1418 if(block[arr1[0]]!=block[arr2[0]]) return block[arr1[0]]<block[arr2[0]]; 1419 if(block[arr1[0]]&1) return arr1[1]>arr2[1]; 1420 else return arr1[1]<arr2[1]; 1421 }); 1422 vi val(n); 1423 int l=0,r=0; 1424 ds.ins(0); 1425 auto ins=[&](int i){ 1426 for(auto j: adj[i]){ 1427 if(j>=l&&j<=r){ 1428 ds.del(val[j]); 1429 val[j]^=i+1,val[i]^=j+1; 1430 ds.ins(val[j]); 1431 } 1432 } 1433 ds.ins(val[i]); 1434 }; 1435 auto del=[&](int i){ 1436 ds.del(val[i]); 1437 for(auto j: adj[i]){ 1438 if(j>=l&&j<=r){ 1439 ds.del(val[j]); 1440 val[j]^=i+1,val[i]^=j+1; 1441 ds.ins(val[j]); 1442 } 1443 } 1444 }; 1445 auto gogo=[&](int l2, int r2){ 1446 while(l>l2){ 1447 ins(l-1); 1448 l--; 1449 } 1450 while(r<r2){ 1451 ins(r+1); 1452 r++; 1453 } 1454 while(l<l2){ 1455 l++; 1456 del(l-1); 1457 } 1458 while(r>r2){ 1459 r--; 1460 del(r+1); 1461 } 1462 }; 1463 for(auto [l2,r2,k,i]: qq){ 1464 gogo(l2,r2); 1465 res[i]=ds.kth(k); 1466 } 1467 rep(i,l,r+1) ds.del(val[i]); 1468 rep(q) print(res[i]); 1469 } 1470 1471 signed main(){ 1472 ios_base::sync_with_stdio(0),cin.tie(0); 1473 cout << fixed << setprecision(20); 1474 int t=1; 1475 cin >> t; 1476 while(t--) ahcorz(); 1477 } 1478 ``` 1479 1480 **Rate the Problem** 1481 1482 Amazing problem: 1483 1484 Good problem: 1485 1486 Average problem: 1487 1488 Bad problem: 1489 1490 Didn't solve: 1491 1492 #### [D1F1 Top-K Tracker (Easy Version)](https://codeforces.com/contest/2129/problem/F1) and [D1F2 Top-K Tracker (Hard Version)](https://codeforces.com/contest/2129/problem/F2) 1493 1494 **Fun** 1495 1496 Did you notice the double meaning of the title? 1497 1498 **Hint1** 1499 1500 Consider easy version. Try to use only operation $1$ and $3$ (Due to symmetry, using operation $2$ and $4$ is the same), and only use $m=30$ in operation $1$ and $m=300$ in operation $3$. 1501 1502 **Hint2** 1503 1504 Let $S_i$ represent the set in which queries element $i$ is accessed. Make all $S_i$ different to distinguish all elements. 1505 1506 **Hint3** 1507 1508 Greedily choose all $S_i$ such that $|S_i| \lt 3$. Afterwards, carefully construct a set of size $3$ to reach the upper bound. 1509 1510 **Hint4** 1511 1512 Suppose there are $30$ numbers $1, 2, …, 30$, and each number can be used up to $30$ times. Can you construct $900$ distinct triplets? 1513 1514 **Hint5** 1515 1516 Consider hard version. How to efficiently utilize the four operations, and the condition $m \gt k$? 1517 1518 **Hint6** 1519 1520 Using operation $1$ and operation $4$ is enough. Due to symmetry, using operation $2$ and $3$ is the same. 1521 1522 **Hint7** 1523 1524 Recall the bottleneck of the easy version. We used too many sets of size $3$. Let’s say it another way — too many elements were determined at the cost of $3$. How to optimize it? 1525 1526 **Hint8** 1527 1528 Consider $S_i=S_j$. This actually provides an unordered pair. In other words, we know unordered pair $(p_i,p_j)=(x,y)$, but we can not determine whether $p_i=x$ or $p_j=x$. To determine it, we can add one of $x$ or $y$ to the query of type $4$. 1529 1530 **Hint9** 1531 1532 Suppose there are $300$ unordered pairs $(x_1, y_1), (x_2, y_2), …, (x_{300}, y_{300})$. We can add one element of $(x_i, y_i)$ into query $4$, then query to determine all unordered pairs. However, the average cost is still near to $3$, which is no better than the easy version. 1533 1534 **Hint10** 1535 1536 Try to determine $435$ unordered pairs using single query $4$. 1537 1538 **Tutorial (easy version)** 1539 1540 Use only operation $1$ and $3$, with $m=30$ in operation $1$ and $m=300$ in operation $3$. 1541 1542 Let $S_i$ represent the set accessed by query element $i$. To distinguish all elements, we need to ensure that all $S_i$ ($1 \le i \le n$) are distinct. 1543 1544 After selecting all $S_i$ such that $|S_i| \lt 3$, we must also construct a set of size $3$ to reach the upper bound. 1545 1546 Another way to phrase this: We have $30$ numbers $1, 2, \ldots, 30$, where $1$ through $29$ can each be used $30$ times, and $30$ can be used $270$ times. The goal is to construct as many distinct triplets as possible to maximize the count. 1547 1548 A natural approach is to prioritize consuming the usage count of $30$. Since $29$ is prime, the sequence $x = [1, k \mod 29 + 1, 2k \mod 29 + 1, \ldots, 28k \mod 29 + 1]$ ensures all elements are distinct. For $1 \le k \le 9$, we can construct triplets $(x_1, x_2, 30), (x_2, x_3, 30), \ldots, (x_{29}, x_1, 30)$. 1549 1550 After this, $1$ through $29$ will each have $12$ remaining uses, and $30$ will have $9$ remaining uses. This distribution is not ideal. Instead, we can use $(1, 2, 3)$ and $(4, 5, 6)$ in place of $(1, 2, 30), (3, 4, 30),$ and $(5, 6, 30)$. This adjustment ensures that $1$ through $30$ each have $12$ remaining uses. 1551 1552 Define a **perfect set** $S_x$ as a set of triplets where each number from $1$ to $x$ appears exactly once. 1553 1554 For numbers $1, 2, \ldots, 3l$, define: 1555 1556 * $al = [1, 2, \ldots, l]$, 1557 * $am = [l+1, l+2, \ldots, 2l]$, 1558 * $ar = [2l+1, 2l+2, \ldots, 3l]$. 1559 1560 Let $\text{lshift}(a, i) = [a_{1+i}, a_{2+i}, \ldots, a_{(n+i-1) \mod n + 1}]$. Then, define: 1561 1562 $ S_l(\text{al}, \text{am}, \text{ar}) = \{(\text{al}_1, \text{am}_1, \text{ar}_1), (\text{al}_2, \text{am}_2, \text{ar}_2), \ldots, (\text{al}_l, \text{am}_l, \text{ar}_l)\} $ 1563 1564 We can generate $l^2$ distinct perfect sets of the form $S_l(al, \text{lshift}(am, i), \text{lshift}(ar, j))$ for $0 \le i, j \le l$. 1565 1566 Now that all numbers have equal remaining usage counts, we can apply the above construction. 1567 1568 Using the above construction, there are many different approaches. 1569 1570 Overall, we can construct a total of $846$ distinct sets, which is sufficient to pass the easy version. 1571 1572 **Tutorial (hard version)** 1573 1574 The hard version differs significantly from the easy version in its approach, particularly in utilizing the concept of distinguishing elements through $S_i$. 1575 1576 We need to efficiently utilize the four operations, and the condition $m \gt k$. 1577 1578 In this solution, use operation $2$ $29$ times and operation $3$ once. 1579 1580 Consider all sets $S_i$ with $|S_i| \lt 3$ and elements in $[1,29]$, assigning each to exactly two indices, yielding $2×(1+29+\frac{29×28}{2})=872$ sets forming 436 unordered pairs where $S_i=S_j$, where we cannot initially determine whether $pos_i = x$ or $pos_j = x$. 1581 1582 Consider $S_i = S_j$. This actually provides an unordered pair $(pos_i, pos_j) = (x, y)$, where we know the pair of positions but cannot determine whether $pos_i = x$ and $pos_j = y$, or $pos_i = y$ and $pos_j = x$. 1583 1584 Let these $\frac{872}{2} = 436$ pairs be denoted as $(pos_1, pos_n), (pos_2, pos_{n-1}), \ldots, (pos_{436}, pos_{n-435})$ (for convenience, we assume $n = 890$). Then, randomly select exactly one $pos$ from each of these pairs, and query the maximum value (considering only one maximum for now) among $p[pos_1 \text{ or } pos_n], p[pos_2 \text{ or } pos_{n-1}], \ldots$. 1585 1586 Let us analyze what will happen: 1587 1588 | Return Value | Pairs Determined | Probability | 1589 | --- | --- | --- | 1590 | $n$ | $1$ | $\frac{1}{2}$ | 1591 | $n-1$ | $2$ | $\frac{1}{4}$ | 1592 | $n-2$ | $3$ | $\frac{1}{8}$ | 1593 | ... | ... | ... | 1594 1595 We can see ehe expected number of resolved pairs per query: 1596 1597 $1 \times \frac{1}{2} + 2 \times \frac{1}{4} + 3 \times \frac{1}{8} + \dots \approx 2$ 1598 1599 With an expectation value of $2$, we can estimate that performing $\text{max}$ query $300$ times yields a high probability $P \approx 1$ of determining all $436$ unordered pairs $(pos_i, pos_j)$. This implies that a single application of operation $3$ suffices to resolve all such pairs. 1600 1601 Through this methodology, we successfully determine $872$ elements of the permutation $p$. At this stage, $29$ query operations remain available (with exactly $2$ uses permitted), and the determination of all $n=890$ elements becomes computationally tractable. 1602 1603 **Failure probability analysis** 1604 1605 Mathematically, this follows a geometric distribution with success probability $p = \frac{1}{2}$ where $\mathbb{P}(X = i) = 2^{-i}$, and the sum of such geometric random variables yields a negative binomial distribution $\text{NB}(r,p)$. For large $n$, this can be approximated by a normal distribution $\mathcal{N}(\mu, \sigma^2)$ via the Central Limit Theorem, where $\mu = \frac{1}{p} = 2$ and $\sigma^2 = \frac{1-p}{p^2} = 2$. 1606 1607 ## Probability that $\sum_{i=1}^{300} X_i \le 435$ 1608 1609 **Given.** $X$ is discrete with $ \mathbb{P}(X=k)=2^{-k},\; k=1,2,\dots$. Thus $X\sim\mathrm{Geom}(p=\tfrac12)$ on ${1,2,\dots}$ with mean $1/p=2$. 1610 1611 ### 1) Sum–negative-binomial connection 1612 1613 Let $S=\sum_{i=1}^{300} X_i$. The sum of i.i.d. $\mathrm{Geom}(p)$ variables is negative binomial: 1614 1615 $ S \sim \mathrm{NB}(r=300,\;p=\tfrac12), $ 1616 1617 i.e., $S$ is the number of Bernoulli$(\tfrac12) 1618 1619 Unable to parse markup [type=CF_MATHJAX] 1620 1621 successes. 1622 1623 ### 2) Convert to a binomial tail 1624 1625 $ \mathbb{P}(S \le 435) = \mathbb{P}\big(\text{300th success occurs by time }435\big) = \mathbb{P}\big(\mathrm{Bin}(n=435,p=\tfrac12)\ge 300\big). $ 1626 1627 ### 3) Exact expression 1628 1629 By symmetry of the binomial with $p=\tfrac12$, 1630 1631 $ \mathbb{P}\big(\mathrm{Bin}(435,\tfrac12)\ge 300\big) = \sum_{k=300}^{435} \binom{435}{k} 2^{-435} = \sum_{k=0}^{135} \binom{435}{k} 2^{-435}. $ 1632 1633 ### 4) Numerical value 1634 1635 $ \boxed{\;\mathbb{P}\!\left(\sum_{i=1}^{300} X_i \le 435\right) \;\approx\; 8.61\times 10^{-16}\;} $ 1636 1637 ### 5) Sanity check (normal approximation to the binomial) 1638 1639 With $\mu = np = 217.5$, $\sigma=\sqrt{np(1-p)}=\sqrt{108.75}\approx 10.428$, and continuity correction, 1640 1641 $ z=\frac{299.5-\mu}{\sigma}\approx 7.86 \quad\Rightarrow\quad \mathbb{P}(Z\ge z)\approx 1.87\times 10^{-15}, $ 1642 1643 which is of the same (tiny) order as the exact value above. 1644 1645 **solution (easy version)** 1646 1647 ``` 1648 #include <map> 1649 #include <set> 1650 #include <cmath> 1651 #include <ctime> 1652 #include <queue> 1653 #include <stack> 1654 #include <cstdio> 1655 #include <cstdlib> 1656 #include <vector> 1657 #include <cstring> 1658 #include <algorithm> 1659 #include <iostream> 1660 #include <bitset> 1661 #include <unordered_map> 1662 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 1663 using namespace std; 1664 typedef double db; 1665 typedef long long ll; 1666 typedef unsigned long long ull; 1667 const int N=1010; 1668 int T,n; 1669 vector<int> Sv[N],Sp[N]; 1670 1671 void init() 1672 { 1673 cin>>n; 1674 for(int i=1;i<N;i++) 1675 Sv[i].clear(),Sp[i].clear(); 1676 } 1677 1678 vector<int> ask(int ty,vector<int> &v) 1679 { 1680 cout<<ty<<" "<<v.size(); 1681 for(int i=0;i<v.size();i++) 1682 cout<<" "<<v[i]; 1683 cout<<"\n"<<flush; 1684 int k; 1685 if(ty<3) k=min(60,(int)v.size()); 1686 else k=min(300,(int)v.size()); 1687 vector<int> res; 1688 for(int i=1;i<=k;i++) 1689 { 1690 int t; 1691 cin>>t; 1692 res.push_back(t); 1693 } 1694 return res; 1695 } 1696 1697 void solve() 1698 { 1699 int cnt=0; 1700 vector<int> p(n+4); 1701 for(int i=1;i<=30;i++) 1702 Sv[++cnt].push_back(i); 1703 for(int i=1;i<=30;i++) 1704 { 1705 for(int j=i+1;j<=30;j++) 1706 { 1707 cnt++; 1708 Sv[cnt].push_back(i),Sv[cnt].push_back(j); 1709 } 1710 } 1711 for(int i=1;i<=9;i++) 1712 { 1713 int cur=1; 1714 while(1) 1715 { 1716 int nxt=cur+i; 1717 if(nxt>29) nxt-=29; 1718 cnt++; 1719 Sv[cnt].push_back(30); 1720 Sv[cnt].push_back(cur); 1721 Sv[cnt].push_back(nxt); 1722 cur=nxt; 1723 if(nxt==1) break; 1724 } 1725 } 1726 vector<int> vl(11),vm(11),vr(11); 1727 for(int i=1;i<=10;i++) 1728 vl[i]=i,vm[i]=10+i,vr[i]=20+i; 1729 for(int i=1;i<=9;i++) 1730 { 1731 for(int j=1;j<=10;j++) 1732 { 1733 cnt++; 1734 Sv[cnt].push_back(vl[j]); 1735 Sv[cnt].push_back(vm[j]); 1736 Sv[cnt].push_back(vr[j]); 1737 } 1738 for(int j=0;j<10;j++) 1739 vr[j]=vr[j+1]; 1740 vr[10]=vr[0]; 1741 } 1742 for(int i=1,cur=1;i<=29;i++) 1743 { 1744 int x=cur,y=cur+1,z=cur+2; 1745 while(x>29) x-=29; 1746 while(y>29) y-=29; 1747 while(z>29) z-=29; 1748 cnt++; 1749 Sv[cnt].push_back(x); 1750 Sv[cnt].push_back(y); 1751 Sv[cnt].push_back(z); 1752 cur+=3; 1753 } 1754 for(int i=1;i<=30;i++) 1755 { 1756 vector<int> v,t; 1757 for(int j=1;j<=n;j++) 1758 if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end()) 1759 v.push_back(j); 1760 if(v.empty()) continue; 1761 if(i<30) t=ask(2,v); 1762 else t=ask(4,v); 1763 for(int j=0;j<t.size();j++) 1764 Sp[t[j]].push_back(i); 1765 } 1766 for(int i=1;i<=n;i++) 1767 sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end()); 1768 for(int i=1;i<=n;i++) 1769 for(int j=1;j<=n;j++) 1770 if((!Sp[i].empty())&&Sp[i]==Sv[j]) p[i]=j; 1771 cout<<"! "; 1772 for(int i=1;i<=n;i++) 1773 cout<<p[i]<<(i==n?'\n':' '); 1774 cout<<flush; 1775 } 1776 1777 int main() 1778 { 1779 fastio; 1780 1781 cin>>T; 1782 while(T--) 1783 { 1784 init(); 1785 solve(); 1786 } 1787 1788 return 0; 1789 } 1790 ``` 1791 1792 **solution (hard version)** 1793 1794 ``` 1795 #include <map> 1796 #include <set> 1797 #include <cmath> 1798 #include <ctime> 1799 #include <queue> 1800 #include <stack> 1801 #include <cstdio> 1802 #include <cstdlib> 1803 #include <vector> 1804 #include <cstring> 1805 #include <algorithm> 1806 #include <iostream> 1807 #include <bitset> 1808 #include <unordered_map> 1809 #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); 1810 using namespace std; 1811 typedef double db; 1812 typedef long long ll; 1813 typedef unsigned long long ull; 1814 const int N=1010; 1815 int T,n; 1816 vector<int> Sv[N],Sp[N],prv[N],prp[N]; 1817 1818 void init() 1819 { 1820 srand(time(0)); 1821 cin>>n; 1822 for(int i=1;i<N;i++) 1823 Sv[i].clear(),Sp[i].clear(),prv[i].clear(),prp[i].clear(); 1824 } 1825 1826 vector<int> ask(int ty,vector<int> &v) 1827 { 1828 cout<<ty<<" "<<v.size(); 1829 for(int i=0;i<v.size();i++) 1830 cout<<" "<<v[i]; 1831 cout<<"\n"<<flush; 1832 int k; 1833 if(ty<3) k=min(60,(int)v.size()); 1834 else k=min(300,(int)v.size()); 1835 vector<int> res; 1836 for(int i=1;i<=k;i++) 1837 { 1838 int t; 1839 cin>>t; 1840 res.push_back(t); 1841 } 1842 return res; 1843 } 1844 1845 void solve() 1846 { 1847 int cnt=0,cntr=871,cntpr=30; 1848 vector<int> p(n+4); 1849 for(int i=1;i<=29;i++) 1850 { 1851 cnt++; 1852 Sv[cnt].push_back(i); 1853 cntr--; 1854 Sv[cntr].push_back(i); 1855 } 1856 for(int i=1;i<=29;i++) 1857 { 1858 for(int j=i+1;j<=29;j++) 1859 { 1860 cnt++; 1861 Sv[cnt].push_back(i),Sv[cnt].push_back(j); 1862 cntr--; 1863 Sv[cntr].push_back(i),Sv[cntr].push_back(j); 1864 } 1865 } 1866 for(int i=871,hd=1;i<890;i++,hd+=3) 1867 { 1868 int x=hd,y=hd+1,z=hd+2; 1869 if(x>29) x-=29; 1870 if(y>29) y-=29; 1871 if(z>29) z-=29; 1872 Sv[i].push_back(x),Sv[i].push_back(y),Sv[i].push_back(z); 1873 } 1874 for(int i=1;i<=29;i++) 1875 { 1876 vector<int> v,t; 1877 for(int j=1;j<=n;j++) 1878 if(find(Sv[j].begin(),Sv[j].end(),i)!=Sv[j].end()) 1879 v.push_back(j); 1880 if(v.empty()) continue; 1881 t=ask(2,v); 1882 for(int j=0;j<t.size();j++) 1883 Sp[t[j]].push_back(i); 1884 } 1885 for(int i=1;i<=n;i++) 1886 sort(Sp[i].begin(),Sp[i].end()), sort(Sv[i].begin(),Sv[i].end()); 1887 for(int i=1;i<=n;i++) 1888 { 1889 for(int j=871;j<=n;j++) 1890 if(Sp[i]==Sv[j]) p[i]=j; 1891 } 1892 for(int i=1;i<=n;i++) 1893 { 1894 if(Sp[i].size()==1) prp[Sp[i][0]].push_back(i); 1895 else if(Sp[i].size()==2) prp[30*Sp[i][0]+Sp[i][1]].push_back(i); //hash the set 1896 //|S|>2 and empty set are ignored 1897 } 1898 for(int i=1;i<=n;i++) 1899 { 1900 if(Sv[i].size()==1) prv[Sv[i][0]].push_back(i); 1901 else if(Sv[i].size()==2) prv[30*Sv[i][0]+Sv[i][1]].push_back(i); //hash the set 1902 } 1903 //necessary shuffle 1904 for(int i=1;i<N;i++) 1905 { 1906 if(prp[i].size()<2) continue; 1907 if(rand()&1) swap(prp[i][0],prp[i][1]); 1908 } 1909 for(int i=1;i<=1;i++) 1910 { 1911 vector<int> v,t; 1912 for(int j=1;j<N;j++) 1913 { 1914 if(prp[j].empty()) continue; 1915 else if(prp[j].size()==1) 1916 { 1917 p[prp[j][0]]=prv[j][0]; 1918 prp[j].clear(); 1919 prv[j].clear(); 1920 continue; 1921 } 1922 v.push_back(prp[j][0]); 1923 } 1924 if(v.empty()) continue; 1925 t=ask(3,v); 1926 for(int j=1;j<N;j++) 1927 { 1928 if(prp[j].empty()) continue; 1929 if(t.empty()) break; 1930 if(prv[j][1]==t.back()) 1931 { 1932 t.pop_back(); 1933 p[prp[j][0]]=prv[j][1]; 1934 p[prp[j][1]]=prv[j][0]; 1935 } 1936 else 1937 { 1938 p[prp[j][0]]=prv[j][0]; 1939 p[prp[j][1]]=prv[j][1]; 1940 } 1941 prp[j].clear(); 1942 prv[j].clear(); 1943 } 1944 } 1945 cout<<"! "; 1946 for(int i=1;i<=n;i++) 1947 cout<<p[i]<<(i==n?'\n':' '); 1948 cout<<flush; 1949 } 1950 1951 int main() 1952 { 1953 fastio; 1954 1955 cin>>T; 1956 while(T--) 1957 { 1958 init(); 1959 solve(); 1960 } 1961 1962 return 0; 1963 } 1964 ``` 1965 1966 **Rate the Problem** 1967 1968 Amazing problem: 1969 1970 Good problem: 1971 1972 Average problem: 1973 1974 Bad problem: 1975 1976 Didn't solve: