codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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 ```