1705.md (24122B)
1 Source: https://codeforces.com/blog/entry/104881 2 3 Thanks for participating. We apologize for problem F that has appeared before. Still, we hope you all enjoy our round! 4 5 ## [1705A - Mark the Photographer](/contest/1705/problem/A "Codeforces Round 807 (Div. 2)") 6 7 Author: [MarkBcc168](/profile/MarkBcc168 "Master MarkBcc168") 8 9 **Hint 1** 10 11 First, sort $h_1 \leq h_2 \leq \dots \leq h_{2n}$. There is a very explicit description to which $h_i$'s work. 12 13 **Hint 2** 14 15 What is the optimal arrangement that maximizes the minimum difference across all pairs? 16 17 **Tutorial** 18 19 We have a very explicit description of whether the arrangement is possible. Sort the heights so that $h_1 \leq h_2 \leq \dots \leq h_{2n}$. Then, there exists such arrangement if and only if all the following conditions hold. 20 21 $\begin{align*} h_{n+1}-h_1 &\geq x \\ h_{n+2}-h_2 &\geq x \\ &\vdots \\ h_{2n}-h_n &\geq x \end{align*}$ 22 23 We present two proofs. 24 25 --- 26 27 *Proof 1 (Direct Proof).* Suppose that the arrangement is possible. We will show that for each $i$, we have $h_{n+i}-h_i\geq x$. 28 29 To do so, note that $n+1$ people who have height in $[h_i, h_{n+i}]$. It's impossible that these $n+1$ people got assigned to different columns (because there are $n$ columns), so there exist two people that got assigned to the same column. 30 31 However, because these two people have height in $[h_i, h_{n+i}]$, the difference in heights between these two people is at most $h_{n+i}-h_i$. As the difference is at least $x$ by the arrangement, we must have that $h_{n+i}-h_i\geq x$. $\blacksquare$ 32 33 --- 34 35 *Proof 2 (Exchange Argument).* First, we look at two pairs. Suppose that the $i$-th person in the first and second row have heights $a \lt b$, while the $j$-th person in the first and second row have heights $c \lt d$. 36 37 $\begin{array}{ccccc} \dots & a & \dots & c & \dots \\ \dots & b & \dots & d & \dots \end{array}$ 38 39 * Assume that $b\geq c$, then we switch $b,c$. The arrangement still works since $a-c \geq a-b \geq x$ and $b-d \geq c-d \geq x$. 40 * Similarly, $a\geq d$ yields a switch. 41 42 Thus, we can keep exchanging until anyone in the first row is at least as tall as anyone in the second row. Thus, the first row must be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in some order. 43 44 Now, we look at the same picture again. Assume that $a\geq c$ but $b\leq d$. then, we can switch $b,d$, and it still works because $a-d \geq c-d \geq x$ and $c-b \geq c-d \geq x$. Thus, we can switch the second row until it matches the order of the first row. 45 46 Therefore, we force the first row to be $h_{n+1}, h_{n+2}, \dots, h_{2n}$, while the second row must be $h_1, h_2, \dots, h_n$ in that order. This implies the conclusion. $\blacksquare$ 47 48 --- 49 50 Time Complexity: $O(n\log n)$ for sorting. 51 52 **Code** 53 54 ``` 55 #include <bits/stdc++.h> 56 57 using namespace std; 58 59 void solve() { 60 int n, x; 61 cin >> n >> x; 62 vector<int> a(2 * n); 63 for (int i = 0; i < 2 * n; ++i) 64 cin >> a[i]; 65 sort(a.begin(), a.end()); 66 bool ok = true; 67 for (int i = 0; i < n; ++i) 68 if (a[n + i] - a[i] < x) ok = false; 69 cout << (ok ? "YES" : "NO") << "\n"; 70 } 71 72 int main() { 73 int tt; cin >> tt; 74 while (tt--) solve(); 75 } 76 ``` 77 78 ## [1705B - Mark the Dust Sweeper](/contest/1705/problem/B "Codeforces Round 807 (Div. 2)") 79 80 Author: [MarkBcc168](/profile/MarkBcc168 "Master MarkBcc168") 81 82 **Hint** 83 84 The optimal way is to fill all the zero entries first. 85 86 **Tutorial** 87 88 Delete the leading zeroes in the array $a$ (i.e., the first $t$ numbers of $a$ that are zero) so that now $a_1\ne 0$. Let $k$ be the number of $0$'s in $a_1,a_2,\dots,a_{n-1}$. The answer is 89 90 $(a_1+a_2+\dots + a_{n-1}) + k.$ 91 92 To see why, let Mark keep filling the *holes* (rooms with dust level $0$) first by subtracting the first nonzero index and changing the first zero index to $1$. This takes $k$ moves to fill all zeroes in $a_1,a_2,\dots,a_{n-1}$. Then, we can start moving, from left to right, all dust to the $n$-th room, taking $a_1+a_2+\dots+a_{n-1}$ moves. 93 94 Finally, we argue that this is the minimum number of moves. To that end, we prove that each move decreases the answer by at most $1$. We consider two cases. 95 96 * If a move has $j=n$, then it decreases $a_1+a_2+\dots+a_{n-1}$ by $1$ but does not decrease $k$. 97 * If $j\ne n$, then the move doesn't decrease $a_1+a_2+\dots+a_{n-1}$ and decreases $k$ by at most $1$. 98 99 Thus, we are done. The time complexity is $O(n)$. 100 101 **Code** 102 103 ``` 104 #include <iostream> 105 #include <vector> 106 #define ll long long 107 108 using namespace std; 109 110 void solve(){ 111 int n; cin >> n; 112 vector<int> a(n); 113 for(int i = 0; i < n; ++i) 114 cin >> a[i]; 115 ll ans = 0; 116 int ptr = 0; 117 while(ptr < n && a[ptr] == 0) 118 ptr++; 119 for(int i = ptr; i < n-1; ++i){ 120 ans += a[i]; 121 if(a[i] == 0) ans++; 122 } 123 cout << ans << "\n"; 124 } 125 int main(){ 126 int tt; cin >> tt; 127 while(tt--) solve(); 128 } 129 ``` 130 131 ## [1705C - Mark and His Unfinished Essay](/contest/1705/problem/C "Codeforces Round 807 (Div. 2)") 132 133 Author: [MarkBcc168](/profile/MarkBcc168 "Master MarkBcc168") 134 135 **Hint 1** 136 137 What's in common between all letters that were copied at the same time? 138 139 **Hint 2** 140 141 The answer is the difference between the current position and the position where it came from. That's what you need to store. 142 143 **Hint 3** 144 145 By tracking the difference, you can recurse to the previously-copied substring. 146 147 **Tutorial** 148 149 This is an implementation problem. What you need to do is after the $i$-th copying operation, we need to keep track of the beginning point $a_i$ and the ending point $b_i$ of the appended string. Moreover, we also keep track the *subtraction distance* $t_i = a_i-l_i$ so that for $k\in [a_i, b_i]$, the $k$-th letter is the same as the $(k-t_i)$-th letter. Thus, we have recursed the position to the smaller position $k-t_i$, so we keep doing that until we reach the initial string. 150 151 Therefore, to solve this problem, we iterate from $i=c,c-1,\dots,1$. If $k$ is in $[a_i,b_i]$, subtract $k$ by $t_i$. After all operations, $k$ should be at the inital string, and we output the $k$-th letter. 152 153 The time complexity of this solution is $O(cq)$. However, less efficient solutions of $O((c\log c) q)$ (using binary search each time) or $O(c^2q)$ (by going through all intervals in each iteration) pass as well. 154 155 **Code** 156 157 ``` 158 #include<bits/stdc++.h> 159 #define ll long long 160 161 using namespace std; 162 163 void solve(){ 164 int n, c, q; cin >> n >> c >> q; 165 string s; cin >> s; 166 167 vector<ll> left(c+1), right(c+1), diff(c+1); 168 left[0] = 0; 169 right[0] = n; 170 171 for(int i=1; i<=c; ++i){ 172 ll l, r; cin >> l >> r; 173 l--; r--; 174 left[i] = right[i-1]; 175 right[i] = left[i] + (r-l+1); 176 diff[i] = left[i] - l; 177 } 178 179 while(q--){ 180 ll k; cin >> k; 181 k--; 182 for(int i=c; i>=1; --i){ 183 if(k < left[i]) continue; 184 else k -= diff[i]; 185 } 186 cout << s[k] << "\n"; 187 } 188 189 } 190 191 int main(){ 192 int tt; cin >> tt; 193 while(tt--) solve(); 194 } 195 ``` 196 197 ## [1705D - Mark and Lightbulbs](/contest/1705/problem/D "Codeforces Round 807 (Div. 2)") 198 199 Author: [MarkBcc168](/profile/MarkBcc168 "Master MarkBcc168") 200 201 **Hint 1** 202 203 Look at all the $01$'s and $10$'s carefully. 204 205 **Hint 2** 206 207 The sum of the number of $01$'s and $10$'s is constant. 208 209 **Hint 3** 210 211 Consider all positions of $01$'s and $10$'s. How does it change in each operation? 212 213 **Tutorial** 214 215 As explained in the sample explanations, the operation cannot change the first or the last bit. Thus, if either $s_1\ne t_1$ or $s_n\ne t_n$, simply return $\texttt{-1}$. 216 217 Now, the key idea is to consider a binary $\overline{s} = (s_1\oplus s_2)(s_2\oplus s_3) \dots (s_{n-1}\oplus s_n)$ of length $n-1$, where $a\oplus b$ denotes the XOR operation of bits $a$ and $b$. Then, it's easy to verify that the operation acts on $\overline{s}$ by just swapping two different bits. An example is shown below 218 219 $ \begin{array}{cc} s & \overline s \\ \texttt{000101} & \texttt{00111} \\ \downarrow & \downarrow \\ \texttt{001101} & \texttt{01011}\\ \downarrow & \downarrow \\ \texttt{011101} & \texttt{10011} \\ \downarrow & \downarrow \\ \texttt{011001} & \texttt{10101} \\ \downarrow & \downarrow \\ \texttt{011011} & \texttt{10110} \\ \downarrow & \downarrow \\ \texttt{010011} & \texttt{11010} \end{array}$ 220 221 Thus, the operation is possible if and only if $\overline s$ and $\overline t$ has the same number of $1$'s. Moreover, if $a_1,a_2,\dots,a_k$ are the positions of $1$'s in $\overline s$ and $b_1,b_2,\dots,b_k$ are the positions of $1$'s in $\overline t$. Then, the minimum number of moves is given by 222 223 $|a_1-b_1| + |a_2-b_2| + \dots + |a_k-b_k|,$ 224 225 which can be evaluated in $O(n)$. 226 227 This is a well-known fact, but for completeness, here is the proof. Note that the operation is moving $1$ to left or right by one position. Thus, to achieve that number of moves, simply move the first $1$ from $a_1$ to $b_1$, move the second $1$ from $a_2$ to $b_2$, $\ldots$, and move the $k$-th $1$ from $a_k$ to $b_k$. For the lower bound, notice that the $i$-th $1$ cannot move past the $(i-1)$-th or $(i+1)$-th $1$. Thus, it takes at least $|a_i-b_i|$ moves to move the $i$-th $1$ from $a_i$ to $b_i$. Summing gives the conclusion. 228 229 Note that another way to think about this problem is to look at the block of $1$'s and $0$'s and notice that the number of blocks remains constant. This is more or less the same as the above solution. 230 231 **Code** 232 233 ``` 234 #include <bits/stdc++.h> 235 #define ll long long 236 237 using namespace std; 238 239 void solve(){ 240 int n; cin >> n; 241 string s,t; cin >> s >> t; 242 vector<ll> pos_s, pos_t; 243 244 if(s[0] != t[0] || s[n-1] != t[n-1]){ 245 cout << -1 << "\n"; 246 return; 247 } 248 for(int i=0; i<n-1; i++){ 249 if(s[i] != s[i+1]) pos_s.push_back(i); 250 if(t[i] != t[i+1]) pos_t.push_back(i); 251 } 252 if(pos_s.size() != pos_t.size()){ 253 cout << -1 << "\n"; 254 } 255 else{ 256 int k = pos_s.size(); 257 ll ans = 0; 258 for(int i=0; i<k; ++i){ 259 ans += abs(pos_s[i] - pos_t[i]); 260 } 261 cout << ans << "\n"; 262 } 263 } 264 265 int main(){ 266 int tt; cin >> tt; 267 while(tt--) solve(); 268 } 269 ``` 270 271 ## [1705E - Mark and Professor Koro](/contest/1705/problem/E "Codeforces Round 807 (Div. 2)") 272 273 Author: [abc241](/profile/abc241 "Specialist abc241") 274 275 **Hint 1** 276 277 Find a concise description of the answer first. 278 279 **Hint 2** 280 281 Think about power of two. 282 283 **Hint 3** 284 285 The sum $2^{a_1}+2^{a_2}+\dots+2^{a_n}$ is constant. Show that the answer must be the most significant bit of that. 286 287 **Hint 4** 288 289 Use either bitset or lazy segment tree to simulate the addition/subtraction. 290 291 **Tutorial** 292 293 The key observation is the following. 294 295 **Claim:** The answer is $\lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor.$ 296 297 *Proof:* The upper bound is pretty clear, as the operation doesn't change the $\sum 2^{a_i}$. Moreover, the sum must be at least $2^{\text{ans}}$, giving the result. 298 299 For the construction, let Mark keep performing the operation until he cannot. At this point, all numbers must be distinct, and the $\sum 2^{a_i}$ is unchanged. Let the current numbers on the board be $b_1 \lt b_2 \lt \dots \lt b_k$. Then, 300 301 $\sum_{i=1}^n 2^{a_i} = 2^{b_1}+2^{b_2}+\dots + 2^{b_k} \leq 2^1+2^2+\dots+2^{b_k} \lt 2^{b_k+1}.$ 302 303 Thus, Mark can make the final number be $b_k = \lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor$ as desired. $\blacksquare$ 304 305 --- 306 307 Finally, we need a data structure to maintain the $\sum 2^{a_i}$ and simulate base 2 addition. There are many ways to proceed, including the following: 308 309 * Using bitsets, partition the bits into many chunks of $w$ bits ($w$ between $50$ and $64$ is fine). This gives $O(n^2/w)$ complexity, but its low constant factor makes it enough to pass comfortably. 310 * Use lazy segment augmented with $O(\log n)$ binary search. For each bit added, find where the longest streak of $1$'s to the left of that bit ends, and update accordingly. Similarly, for each bit subtracted, find where the longest streak of $0$'s to the left of that bit ends, and update accordingly. The total complexity is $O(n\log n)$. 311 312 **Code (Bitsets, by errorgorn)** 313 314 ``` 315 #pragma GCC optimize("O3,unroll-loops") 316 #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") 317 318 // Super Idol的笑容 319 // 都没你的甜 320 // 八月正午的阳光 321 // 都没你耀眼 322 // 热爱105°C的你 323 // 滴滴清纯的蒸馏水 324 325 #include <bits/stdc++.h> 326 using namespace std; 327 328 #define ll long long 329 #define ii pair<ll,ll> 330 #define iii pair<ii,ll> 331 #define fi first 332 #define se second 333 #define endl '\n' 334 #define debug(x) cout << #x << ": " << x << endl 335 336 #define pub push_back 337 #define pob pop_back 338 #define puf push_front 339 #define pof pop_front 340 #define lb lower_bound 341 #define ub upper_bound 342 343 #define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) 344 #define all(x) (x).begin(),(x).end() 345 #define sz(x) (int)(x).size() 346 347 mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); 348 349 struct bitset{ 350 unsigned long long arr[3130]={}; 351 unsigned long long AF=-1ull; 352 353 void flip(int l,int r){ 354 arr[l/64]^=(1ull<<(l%64))-1; 355 if (r%64==63) arr[r/64]^=AF; 356 else arr[r/64]^=(1ull<<(r%64+1))-1; 357 l/=64,r/=64; 358 if (l==r) return; 359 arr[l]^=AF; 360 361 for (int x=l+1;x<r;x++) arr[x]^=AF; 362 } 363 364 int get(int i){ 365 if (arr[i/64]&(1ull<<(i%64))) return 1; 366 else return 0; 367 } 368 369 int get1(int i){ 370 //search [i%64,64) on i/64 first 371 unsigned long long mask=AF^((1ull<<(i%64))-1); 372 373 i=i/64; 374 unsigned long long temp=arr[i]&mask; 375 if (temp) return i*64+__builtin_ctzll(temp); 376 i++; 377 while (true){ 378 if (arr[i]==0) i++; 379 else return i*64+__builtin_ctzll(arr[i]); 380 } 381 } 382 383 int get0(int i){ 384 //search [i%64,64) on i/64 first 385 unsigned long long mask=AF^((1ull<<(i%64))-1); 386 387 i=i/64; 388 unsigned long long temp=(arr[i]^AF)&mask; 389 if (temp) return i*64+__builtin_ctzll(temp); 390 i++; 391 while (true){ 392 if (arr[i]==AF) i++; 393 else return i*64+__builtin_ctzll(arr[i]^AF); 394 } 395 } 396 397 int gethigh(){ 398 int i=3129; 399 while (true){ 400 if (arr[i]==0) i--; 401 else return i*64+63-__builtin_clzll(arr[i]); 402 } 403 } 404 } BS; 405 406 int n,q; 407 int arr[200005]; 408 409 void add(int i){ 410 BS.flip(i,BS.get0(i)); 411 } 412 413 void del(int i){ 414 BS.flip(i,BS.get1(i)); 415 } 416 417 signed main(){ 418 ios::sync_with_stdio(0); 419 cin.tie(0); 420 cout.tie(0); 421 cin.exceptions(ios::badbit | ios::failbit); 422 423 cin>>n>>q; 424 rep(x,1,n+1) cin>>arr[x]; 425 rep(x,1,n+1) add(arr[x]); 426 427 int a,b; 428 while (q--){ 429 cin>>a>>b; 430 del(arr[a]); 431 arr[a]=b; 432 add(arr[a]); 433 434 cout<<BS.gethigh()<<endl; 435 } 436 } 437 ``` 438 439 **Code (Lazy Segment)** 440 441 ``` 442 #include<bits/stdc++.h> 443 using namespace std; 444 445 struct LazySeg { 446 int l, r; 447 int val = 0, tag = 0; 448 bool is_lazy = false; 449 LazySeg * l_child = NULL, * r_child = NULL; 450 451 LazySeg(int _l, int _r) { 452 l = _l; 453 r = _r; 454 if (r - l > 1) { 455 int m = (l + r) / 2; 456 l_child = new LazySeg(l, m); 457 r_child = new LazySeg(m, r); 458 } 459 }~LazySeg() { 460 delete l_child; 461 delete r_child; 462 } 463 void unlazy() { 464 if (!is_lazy) return; 465 val = (r - l) * tag; 466 if (r - l <= 1) return; 467 l_child -> tag = tag; 468 l_child -> is_lazy = true; 469 r_child -> tag = tag; 470 r_child -> is_lazy = true; 471 tag = 0; 472 is_lazy = false; 473 } 474 void update(int from, int to, int x) { 475 unlazy(); 476 if (from >= r || l >= to) return; 477 if (from <= l && to >= r) { 478 tag = x; 479 is_lazy = true; 480 unlazy(); 481 } else { 482 l_child -> update(from, to, x); 483 r_child -> update(from, to, x); 484 val = l_child -> val + r_child -> val; 485 } 486 } 487 int query(int from, int to) { 488 if (from >= r || l >= to) return 0; 489 unlazy(); 490 if (from <= l && to >= r) return val; 491 else { 492 if (l_child == NULL) return 0; 493 return l_child -> query(from, to) + r_child -> query(from, to); 494 } 495 } 496 //pre = prefix in [l,k) 497 int max_right(int k, int pre, int v) { 498 unlazy(); 499 if (r - l == 1) { 500 if (val == v) return l; 501 else return l - 1; 502 } 503 l_child -> unlazy(); 504 int mid = (l + r) / 2; 505 if (mid <= k) { 506 return r_child -> max_right(k, pre - l_child -> val, v); 507 } else if (l_child -> val - pre == v * (mid - k)) { 508 //left to mid-1 has all 1's => answer must be >= mid-1 509 return r_child -> max_right(mid, 0, v); 510 } else { 511 return l_child -> max_right(k, pre, v); 512 } 513 } 514 //suff = suffix 515 int get_answer() { 516 unlazy(); 517 if (r - l == 1) { 518 if (val == 1) return l; 519 else return l - 1; 520 } 521 r_child -> unlazy(); 522 if (r_child -> val == 0) { 523 //[mid to end] are all 0 524 return l_child -> get_answer(); 525 } else { 526 return r_child -> get_answer(); 527 } 528 } 529 }; 530 531 signed main() { 532 ios_base::sync_with_stdio(0); 533 cin.tie(NULL); 534 cout.tie(NULL); 535 536 int n, q; 537 cin >> n >> q; 538 LazySeg tr(0, 200100); 539 540 auto add = [ & ](int x) { 541 int y = tr.max_right(x, tr.query(0, x), 1) + 1; 542 if (y == x) { //no carry; just change 0 to 1 543 tr.update(x, x + 1, 1); 544 } else { //there is a carry; set the whole block of 1's to 0 545 tr.update(x, y, 0); 546 tr.update(y, y + 1, 1); 547 } 548 }; 549 550 auto remove = [ & ](int x) { 551 int y = tr.max_right(x, tr.query(0, x), 0) + 1; 552 if (y == x) { 553 tr.update(x, x + 1, 0); 554 } else { 555 tr.update(x, y, 1); 556 tr.update(y, y + 1, 0); 557 } 558 }; 559 vector < int > a(n); 560 for (int i = 0; i < n; ++i) { 561 cin >> a[i]; 562 add(a[i]); 563 } 564 while (q--) { 565 int k, l; cin >> k >> l; 566 k--; 567 remove(a[k]); add(l); 568 a[k] = l; 569 cout << tr.get_answer() << "\n"; 570 } 571 } 572 ``` 573 574 ## [1705F - Mark and the Online Exam](/contest/1705/problem/F "Codeforces Round 807 (Div. 2)") 575 576 Author: [MarkBcc168](/profile/MarkBcc168 "Master MarkBcc168") 577 578 Unfortunately, a harder version of this problem has appeared in a Chinese contest [here](https://www.luogu.com.cn/problem/P7848) and [here](https://www.luogu.com.cn/problem/T183641). You can look at their solution [here](https://www.luogu.com.cn/blog/1973224568qq/kao-shi-2021-coe-iii-d#). We thank many contestants who pointed it out. 579 580 **Hint 0** 581 582 It's possible to solve this problem without any randomization. See the subsequent hints for how to do so. 583 584 **Hint 1** 585 586 Observe that we can take differences between two very close queries to get the number of $\texttt{T}$'s in a small subsequence. 587 588 **Hint 2** 589 590 You can take the difference against a pre-computed query. Applying this with a group of two questions. 591 592 **Hint 3** 593 594 You have three possibilities: either $\texttt{TT}$, $\texttt{FF}$, and ${\texttt{TF}, \texttt{FT}}$. If the third possibility happens, simultaneously figure out whether is $\texttt{TF}$ or $\texttt{FT}$ and answer one question within one query. 595 596 **Hint 4** 597 598 You will need to precompute the query $\texttt{TFTF}\dots\texttt{TF}$. 599 600 **Tutorial** 601 602 There are many possible approaches, including using randomized algorithms. However, I will present the solution that takes about $\tfrac{2n}{3}$ queries deterministically. 603 604 We pre-query $\texttt{TTT...T}$ and $\texttt{TFTF...TF}$. Then, for $i=1,2,\dots,\left\lfloor\frac n3\right\rfloor$, we take the difference when both the $(2i-1)$-th and the $2i$-th question in $\texttt{TTT...T}$ is changed to $\texttt{F}$. 605 606 * If the difference is $+2$, then both answers must be $\texttt F$. 607 * If the difference is $-2$, then both answers must be $\texttt T$. 608 * Else, the answers must be $\texttt{TF}$ or $\texttt{FT}$ in some order. 609 610 Now, here is the key idea: if the last case happens, then we can figure out if it's $\texttt{TF}$ or $\texttt{FT}$ **as well as** the answer to one more question in one query. To do so, compare the previous $\texttt{TFTF...TF}$ with a new query that has $3$ differences: 611 612 $\begin{align*} \\ \texttt{TFTF} \dots \texttt{TF} \dots \texttt{T} \dots \texttt{TF} \\ \texttt{TFTF} \dots \color{red}{\texttt{FT}} \dots \color{red}{\texttt F} \dots \texttt{TF} \end{align*}$ 613 614 (Note: we assume that the third question corresponds to $\texttt T$ in the query. If it's $\texttt F$, just change to $\texttt T$ and proceed analogously.) 615 616 There are four possible scenarios. 617 618 * If the answers are $\texttt{TF}$ and $\texttt{T}$, then the difference is $-3$. 619 * If the answers are $\texttt{TF}$ and $\texttt{F}$, then the difference is $-1$. 620 * If the answers are $\texttt{FT}$ and $\texttt{T}$, then the difference is $+1$. 621 * If the answers are $\texttt{FT}$ and $\texttt{F}$, then the difference is $+3$. 622 623 Therefore, we can distinguish these four scenarios in one go. 624 625 Finally, if the first two cases happen, we can easily figure out the answer to one more question in one query (say, by changing that question to $\texttt F$ and compare with the $\texttt{TT...T}$ query). Either way, we can deduce the answer to $3$ questions in $2$ queries, leading to a solution with $\tfrac{2n}{3}$ queries. 626 627 Note that this solution can be easily improved to $\frac {3n}{5}$ on average by randomly shuffling the questions. 628 629 **Code** 630 631 ``` 632 #include <bits/stdc++.h> 633 using namespace std; 634 635 int n; 636 637 int query(string s){ 638 cout << s << endl; 639 cout.flush(); 640 int x; cin >> x; 641 if(x==n) exit(0); 642 return x; 643 } 644 645 int main(){ 646 cin >> n; 647 648 //query true count 649 string all_T(n, 'T'), ans(n, '?'); 650 int cnt_T = query(all_T); 651 652 //query TF 653 string all_TF(n, 'T'); 654 for(int i=1; i<n; i+=2) all_TF[i] = 'F'; 655 int cnt_TF = query(all_TF); 656 657 //begin the loop 658 int l = 0, r = n-1; 659 while(r >= l){ 660 if(r==l){ //only l is undetermined 661 string s(all_T); 662 s[l] = 'F'; 663 int k = query(s); 664 665 if(k > cnt_T){ 666 ans[l] = 'F'; 667 } 668 else{ 669 ans[l] = 'T'; 670 } 671 l++; r--; 672 } 673 else{ 674 string s(all_T); 675 s[l] = 'F'; s[l+1] = 'F'; 676 int k = query(s) - cnt_T; 677 678 if(k == 2){ 679 ans[l] = 'F'; ans[l+1] = 'F'; 680 l += 2; 681 } 682 else if(k == -2){ 683 ans[l] = 'T'; ans[l+1] = 'T'; 684 l += 2; 685 } 686 else{ 687 if(r == l+1){ //only l and l+1 left; figure out the order 688 string s(all_T); 689 s[l] = 'F'; 690 int k = query(s); 691 692 if(k > cnt_T){ 693 ans[l] = 'F'; ans[l+1] = 'T'; 694 } 695 else{ 696 ans[l] = 'T'; ans[l+1] = 'F'; 697 } 698 l += 2; 699 } 700 else{ //determine l, l+1, r 701 string s(all_TF); 702 s[l] = 'F'; s[l+1] = 'T'; 703 704 if(s[r] == 'F') s[r] = 'T'; 705 else s[r] = 'F'; 706 707 int k = query(s) - cnt_TF; 708 if(k == 3){ 709 ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = s[r]; 710 } 711 else if(k == 1){ 712 ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = all_TF[r]; 713 } 714 else if(k == -1){ 715 ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = s[r]; 716 } 717 else{ 718 ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = all_TF[r]; 719 } 720 l += 2; r--; 721 } 722 } 723 } 724 } 725 query(ans); 726 } 727 ```