Codeforces Round #807 (Div 2.) Editorial
Разница между en10 и en11, 122 символ(ов) изменены
Thanks for participating. We apologize for problem F that has appeared before. Still, we hope you all enjoy our round!↵

[problem:1705A]↵
----------------↵

Author: [user:MarkBcc168,2022-07-15]↵

<spoiler summary="Hint 1">↵
First, sort $h_1 \leq h_2 \leq \dots \leq h_{2n}$. There is a very explicit description to which $h_i$'s work.↵
</spoiler>↵


<spoiler summary="Hint 2">↵
What is the optimal arrangement that maximizes the minimum difference across all pairs?↵
</spoiler>↵

<spoiler summary="Tutorial">↵
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.↵
$$\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*}$$↵
We present two proofs.↵

-----↵

*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$.↵

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. ↵

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$↵

-----↵

*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 < b$, while the $j$-th person in the first and second row have heights $c < d$. ↵
$$\begin{array}{ccccc}↵
\dots & a & \dots & c & \dots \\↵
\dots & b & \dots & d & \dots↵
\end{array}$$↵

* 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$.↵
* Similarly, $a\geq d$ yields a switch.↵

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.↵

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.↵

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$↵

-----↵

Time Complexity: $O(n\log n)$ for sorting.↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵

using namespace std;↵

void solve() {↵
    int n, x;↵
    cin >> n >> x;↵
    vector<int> a(2 * n);↵
    for (int i = 0; i < 2 * n; ++i)↵
        cin >> a[i];↵
    sort(a.begin(), a.end());↵
    bool ok = true;↵
    for (int i = 0; i < n; ++i)↵
        if (a[n + i] - a[i] < x) ok = false;↵
    cout << (ok ? "YES" : "NO") << "\n";↵
}↵

int main() {↵
    int tt; cin >> tt;↵
    while (tt--) solve();↵
}↵

~~~~~↵

</spoiler>↵

[problem:1705B]↵
----------------↵

Author: [user:MarkBcc168,2022-07-15]↵

<spoiler summary="Hint">↵
The optimal way is to fill all the zero entries first.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
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↵
$$(a_1+a_2+\dots + a_{n-1}) + k.$$↵
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.↵

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.↵

* If a move has $j=n$, then it decreases $a_1+a_2+\dots+a_{n-1}$ by $1$ but does not decrease $k$.↵
* 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$.↵

Thus, we are done. The time complexity is $O(n)$.↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
#include <iostream>↵
#include <vector>↵
#define ll long long↵

using namespace std;↵


void solve(){↵
    int n; cin >> n;↵
    vector<int> a(n);↵
    for(int i = 0; i < n; ++i)↵
        cin >> a[i];↵
    ll ans = 0;↵
    int ptr = 0;↵
    while(ptr < n && a[ptr] == 0)↵
        ptr++;↵
    for(int i = ptr; i < n-1; ++i){↵
        ans += a[i];↵
        if(a[i] == 0) ans++;↵
    }↵
    cout << ans << "\n";↵
}↵
int main(){↵
    int tt; cin >> tt;↵
    while(tt--) solve();↵
}↵
~~~~~↵

</spoiler>↵

[problem:1705C]↵
----------------↵

Author: [user:MarkBcc168,2022-07-15]↵

<spoiler summary="Hint 1">↵
What's in common between all letters that were copied at the same time?</spoiler>↵


<spoiler summary="Hint 2">↵
The answer is the difference between the current position and the position where it came from. That's what you need to store.↵
</spoiler>↵


<spoiler summary="Hint 3">↵
By tracking the difference, you can recurse to the previously-copied substring.↵
</spoiler>↵

<spoiler summary="Tutorial">↵
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.↵

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.↵

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.↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
#include<bits/stdc++.h>↵
#define ll long long↵

using namespace std;↵

void solve(){↵
    int n, c, q; cin >> n >> c >> q;↵
    string s; cin >> s;↵

    vector<ll> left(c+1), right(c+1), diff(c+1);↵
    left[0] = 0;↵
    right[0] = n;↵

    for(int i=1; i<=c; ++i){↵
     ll l, r; cin >> l >> r;↵
     l--; r--;↵
     left[i] = right[i-1];↵
     right[i] = left[i] + (r-l+1);↵
     diff[i] = left[i] - l;↵
    }↵

    while(q--){↵
     ll k; cin >> k;↵
     k--;↵
     for(int i=c; i>=1; --i){↵
     if(k < left[i]) continue;↵
     else k -= diff[i];↵
     }↵
     cout << s[k] << "\n";↵
    }↵

}↵

int main(){↵
    int tt; cin >> tt;↵
    while(tt--) solve();↵
}↵
~~~~~↵

</spoiler>↵

[problem:1705D]↵
----------------↵

Author: [user:MarkBcc168,2022-07-15]↵

<spoiler summary="Hint 1">↵
Look at all the $01$'s and $10$'s carefully.↵
</spoiler>↵


<spoiler summary="Hint 2">↵
The sum of the number of $01$'s and $10$'s is constant.↵
</spoiler>↵


<spoiler summary="Hint 3">↵
Consider all positions of $01$'s and $10$'s. How does it change in each operation?↵
</spoiler>↵

<spoiler summary="Tutorial">↵
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}$.↵

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↵
$$↵
\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}$$↵
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↵
$$|a_1-b_1| + |a_2-b_2| + \dots + |a_k-b_k|,$$↵
which can be evaluated in $O(n)$.↵

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.↵

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.↵
</spoiler>↵

<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵
#define ll long long↵

using namespace std;↵

void solve(){↵
    int n; cin >> n;↵
    string s,t; cin >> s >> t;↵
    vector<ll> pos_s, pos_t;↵

    if(s[0] != t[0] || s[n-1] != t[n-1]){↵
        cout << -1 << "\n";↵
        return;↵
    }↵
    for(int i=0; i<n-1; i++){↵
        if(s[i] != s[i+1]) pos_s.push_back(i);↵
        if(t[i] != t[i+1]) pos_t.push_back(i);↵
    }↵
    if(pos_s.size() != pos_t.size()){↵
        cout << -1 << "\n";↵
    }↵
    else{↵
        int k = pos_s.size();↵
        ll ans = 0;↵
        for(int i=0; i<k; ++i){↵
            ans += abs(pos_s[i] - pos_t[i]);↵
        }↵
        cout << ans << "\n";↵
    }↵
}↵

int main(){↵
    int tt; cin >> tt;↵
    while(tt--) solve();↵
}↵
~~~~~↵

</spoiler>↵

[problem:1705E]↵
----------------↵

Author: [user:abc241,2022-07-15]↵

<spoiler summary="Hint 1">↵
Find a concise description of the answer first.↵
</spoiler>↵


<spoiler summary="Hint 2">↵
Think about power of two.↵
</spoiler>↵


<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵


<spoiler summary="Hint 4">↵
Use either bitset or lazy segment tree to simulate the addition/subtraction.↵
</spoiler>↵


<spoiler summary="Tutorial">↵
The key observation is the following.↵

**Claim:** The answer is $\lfloor\log_2(2^{a_1}+2^{a_2}+\dots+2^{a_n})\rfloor.$↵

*Proof:* The upper bound is pretty clear, as the 
first operation doesn't change the $\sum 2^{a_i}$, while the second operation decreases that sum. Thus, $\sum 2^{a_i}$ is always decreasing, and it. Moreover, the sum must be at least $2^{\text{ans}}$, giving the result.↵

For the construction, let Mark keep performing the 
first 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<b_2<\dots < b_k$. Then,↵
$$\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} < 2^{b_k+1}.$$↵
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$↵

------↵

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:↵

* 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.↵

* 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)$.↵
</spoiler>↵

<spoiler summary="Code (Bitsets, by errorgorn)">↵

~~~~~↵
#pragma GCC optimize("O3,unroll-loops")↵
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")↵

// Super Idol的笑容↵
//    都没你的甜↵
//  八月正午的阳光↵
//    都没你耀眼↵
//  热爱105°C的你↵
// 滴滴清纯的蒸馏水↵

#include <bits/stdc++.h>↵
using namespace std;↵

#define ll long long↵
#define ii pair<ll,ll>↵
#define iii pair<ii,ll>↵
#define fi first↵
#define se second↵
#define endl '\n'↵
#define debug(x) cout << #x << ": " << x << endl↵

#define pub push_back↵
#define pob pop_back↵
#define puf push_front↵
#define pof pop_front↵
#define lb lower_bound↵
#define ub upper_bound↵

#define rep(x,start,end) for(int x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))↵
#define all(x) (x).begin(),(x).end()↵
#define sz(x) (int)(x).size()↵

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());↵

struct bitset{↵
    unsigned long long arr[3130]={};↵
    unsigned long long AF=-1ull;↵
    ↵
    void flip(int l,int r){↵
        arr[l/64]^=(1ull<<(l%64))-1;↵
        if (r%64==63) arr[r/64]^=AF;↵
        else arr[r/64]^=(1ull<<(r%64+1))-1;↵
        l/=64,r/=64;↵
        if (l==r) return;↵
        arr[l]^=AF;↵
        ↵
        for (int x=l+1;x<r;x++) arr[x]^=AF;↵
    }↵
    ↵
    int get(int i){↵
        if (arr[i/64]&(1ull<<(i%64))) return 1;↵
        else return 0;↵
    }↵
    ↵
    int get1(int i){↵
        //search [i%64,64) on i/64 first↵
        unsigned long long mask=AF^((1ull<<(i%64))-1);↵
        ↵
        i=i/64;↵
        unsigned long long temp=arr[i]&mask;↵
        if (temp) return i*64+__builtin_ctzll(temp);↵
        i++;↵
        while (true){↵
            if (arr[i]==0) i++;↵
            else return i*64+__builtin_ctzll(arr[i]);↵
        }↵
    }↵
    ↵
    int get0(int i){↵
        //search [i%64,64) on i/64 first↵
        unsigned long long mask=AF^((1ull<<(i%64))-1);↵
        ↵
        i=i/64;↵
        unsigned long long temp=(arr[i]^AF)&mask;↵
        if (temp) return i*64+__builtin_ctzll(temp);↵
        i++;↵
        while (true){↵
            if (arr[i]==AF) i++;↵
            else return i*64+__builtin_ctzll(arr[i]^AF);↵
        }↵
    }↵
    ↵
    int gethigh(){↵
        int i=3129;↵
        while (true){↵
            if (arr[i]==0) i--;↵
            else return i*64+63-__builtin_clzll(arr[i]);↵
        }↵
    }↵
} BS;↵

int n,q;↵
int arr[200005];↵

void add(int i){↵
    BS.flip(i,BS.get0(i));↵
}↵

void del(int i){↵
    BS.flip(i,BS.get1(i));↵
}↵

signed main(){↵
    ios::sync_with_stdio(0);↵
    cin.tie(0);↵
    cout.tie(0);↵
    cin.exceptions(ios::badbit | ios::failbit);↵
    ↵
    cin>>n>>q;↵
    rep(x,1,n+1) cin>>arr[x];↵
    rep(x,1,n+1) add(arr[x]);↵
    ↵
    int a,b;↵
    while (q--){↵
        cin>>a>>b;↵
        del(arr[a]);↵
        arr[a]=b;↵
        add(arr[a]);↵
        ↵
        cout<<BS.gethigh()<<endl;↵
    }↵
}↵
~~~~~↵

</spoiler>↵

<spoiler summary="Code (Lazy Segment)">↵

~~~~~↵
#include<bits/stdc++.h>↵
using namespace std;↵

struct LazySeg {↵
    int l, r;↵
    int val = 0, tag = 0;↵
    bool is_lazy = false;↵
    LazySeg * l_child = NULL, * r_child = NULL;↵

    LazySeg(int _l, int _r) {↵
        l = _l;↵
        r = _r;↵
        if (r - l > 1) {↵
            int m = (l + r) / 2;↵
            l_child = new LazySeg(l, m);↵
            r_child = new LazySeg(m, r);↵
        }↵
    }~LazySeg() {↵
        delete l_child;↵
        delete r_child;↵
    }↵
    void unlazy() {↵
        if (!is_lazy) return;↵
        val = (r - l) * tag;↵
        if (r - l <= 1) return;↵
        l_child -> tag = tag;↵
        l_child -> is_lazy = true;↵
        r_child -> tag = tag;↵
        r_child -> is_lazy = true;↵
        tag = 0;↵
        is_lazy = false;↵
    }↵
    void update(int from, int to, int x) {↵
        unlazy();↵
        if (from >= r || l >= to) return;↵
        if (from <= l && to >= r) {↵
            tag = x;↵
            is_lazy = true;↵
            unlazy();↵
        } else {↵
            l_child -> update(from, to, x);↵
            r_child -> update(from, to, x);↵
            val = l_child -> val + r_child -> val;↵
        }↵
    }↵
    int query(int from, int to) {↵
        if (from >= r || l >= to) return 0;↵
        unlazy();↵
        if (from <= l && to >= r) return val;↵
        else {↵
            if (l_child == NULL) return 0;↵
            return l_child -> query(from, to) + r_child -> query(from, to);↵
        }↵
    }↵
    //pre = prefix in [l,k)↵
    int max_right(int k, int pre, int v) {↵
        unlazy();↵
        if (r - l == 1) {↵
            if (val == v) return l;↵
            else return l - 1;↵
        }↵
        l_child -> unlazy();↵
        int mid = (l + r) / 2;↵
        if (mid <= k) {↵
            return r_child -> max_right(k, pre - l_child -> val, v);↵
        } else if (l_child -> val - pre == v * (mid - k)) {↵
            //left to mid-1 has all 1's => answer must be >= mid-1↵
            return r_child -> max_right(mid, 0, v);↵
        } else {↵
            return l_child -> max_right(k, pre, v);↵
        }↵
    }↵
    //suff = suffix↵
    int get_answer() {↵
        unlazy();↵
        if (r - l == 1) {↵
            if (val == 1) return l;↵
            else return l - 1;↵
        }↵
        r_child -> unlazy();↵
        if (r_child -> val == 0) {↵
            //[mid to end] are all 0↵
            return l_child -> get_answer();↵
        } else {↵
            return r_child -> get_answer();↵
        }↵
    }↵
};↵

signed main() {↵
    ios_base::sync_with_stdio(0);↵
    cin.tie(NULL);↵
    cout.tie(NULL);↵

    int n, q;↵
    cin >> n >> q;↵
    LazySeg tr(0, 200100);↵

    auto add = [ & ](int x) {↵
        int y = tr.max_right(x, tr.query(0, x), 1) + 1;↵
        if (y == x) { //no carry; just change 0 to 1↵
            tr.update(x, x + 1, 1);↵
        } else { //there is a carry; set the whole block of 1's to 0↵
            tr.update(x, y, 0);↵
            tr.update(y, y + 1, 1);↵
        }↵
    };↵

    auto remove = [ & ](int x) {↵
        int y = tr.max_right(x, tr.query(0, x), 0) + 1;↵
        if (y == x) {↵
            tr.update(x, x + 1, 0);↵
        } else {↵
            tr.update(x, y, 1);↵
            tr.update(y, y + 1, 0);↵
        }↵
    };↵
    vector < int > a(n);↵
    for (int i = 0; i < n; ++i) {↵
        cin >> a[i];↵
        add(a[i]);↵
    }↵
    while (q--) {↵
        int k, l; cin >> k >> l;↵
        k--; ↵
        remove(a[k]); add(l);↵
        a[k] = l;↵
        cout << tr.get_answer() << "\n";↵
    }↵
}↵
~~~~~↵

</spoiler>↵

[problem:1705F]↵
----------------↵

Author: [user:MarkBcc168,2022-07-15]↵

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.↵

<spoiler summary="Hint 0">↵
It's possible to solve this problem without any randomization. See the subsequent hints for how to do so.↵
</spoiler>↵


<spoiler summary="Hint 1">↵
Observe that we can take differences between two very close queries to get the number of $\texttt{T}$'s in a small subsequence.↵
</spoiler>↵


<spoiler summary="Hint 2">↵
You can take the difference against a pre-computed query. Applying this with a group of two questions.↵
</spoiler>↵


<spoiler summary="Hint 3">↵
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.↵
</spoiler>↵


<spoiler summary="Hint 4">↵
You will need to precompute the query $\texttt{TFTF}\dots\texttt{TF}$.↵
</spoiler>↵


<spoiler summary="Tutorial">↵
There are many possible approaches, including using randomized algorithms. However, I will present the solution that takes about $\tfrac{2n}{3}$ queries deterministically.↵

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}$.↵

* If the difference is $+1$, then both answers must be $\texttt F$.↵
* If the difference is $-1$, then both answers must be $\texttt T$.↵
* Else, the answers must be $\texttt{TF}$ or $\texttt{FT}$ in some order.↵

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:↵
$$\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*}$$↵
(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.)↵

There are four possible scenarios.↵

* If the answers are $\texttt{TF}$ and $\texttt{T}$, then the difference is $-3$.↵
* If the answers are $\texttt{TF}$ and $\texttt{F}$, then the difference is $-1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{T}$, then the difference is $+1$.↵
* If the answers are $\texttt{FT}$ and $\texttt{F}$, then the difference is $+3$.↵

Therefore, we can distinguish these four scenarios in one go.↵

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.↵

Note that this solution can be easily improved to $\frac {3n}{5}$ on average by randomly shuffling the questions.↵
</spoiler>↵


<spoiler summary="Code">↵

~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int query(string s){↵
    cout << s << endl;↵
    cout.flush();↵
    int x; cin >> x;↵
    if(x==n) exit(0);↵
    return x;↵
}↵

int main(){↵
    int n; cin >> n;↵

    //query true count↵
    string all_T(n, 'T'), ans(n, '?');↵
    int cnt_T = query(all_T);↵
    ↵
    //query TF↵
    string all_TF(n, 'T');↵
    for(int i=1; i<n; i+=2) all_TF[i] = 'F';↵
    int cnt_TF = query(all_TF);↵

    //begin the loop↵
    int l = 0, r = n-1;↵
    while(r >= l){↵
        if(r==l){ //only l is undetermined↵
            string s(all_T);↵
            s[l] = 'F';↵
            int k = query(s);↵

            if(k > cnt_T){↵
                ans[l] = 'F';↵
            }↵
            else{↵
                ans[l] = 'T';↵
            }↵
            l++; r--;↵
        }↵
        else{↵
            string s(all_T);↵
            s[l] = 'F'; s[l+1] = 'F';↵
            int k = query(s) - cnt_T;↵

            if(k == 2){↵
                ans[l] = 'F'; ans[l+1] = 'F';↵
                l += 2;↵
            }↵
            else if(k == -2){↵
                ans[l] = 'T'; ans[l+1] = 'T';↵
                l += 2;↵
            }↵
            else{↵
                if(r == l+1){ //only l and l+1 left; figure out the order↵
                    string s(all_T);↵
                    s[l] = 'F';↵
                    int k = query(s);↵
                    ↵
                    if(k > cnt_T){↵
                        ans[l] = 'F'; ans[l+1] = 'T';↵
                    }↵
                    else{↵
                        ans[l] = 'T'; ans[l+1] = 'F';↵
                    }↵
                    l += 2;↵
                }↵
                else{ //determine l, l+1, r↵
                    string s(all_TF);↵
                    s[l] = 'F'; s[l+1] = 'T';↵

                    if(s[r] == 'F') s[r] = 'T';↵
                    else s[r] = 'F';↵

                    int k = query(s) - cnt_TF;↵
                    if(k == 3){↵
                        ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = s[r];↵
                    }↵
                    else if(k == 1){↵
                        ans[l] = 'F'; ans[l+1] = 'T'; ans[r] = all_TF[r];↵
                    }↵
                    else if(k == -1){↵
                        ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = s[r];↵
                    }↵
                    else{↵
                        ans[l] = 'T'; ans[l+1] = 'F'; ans[r] = all_TF[r];↵
                    }↵
                    l += 2; r--;↵
                }↵
            }↵
        }↵
    }↵
    query(ans);↵
}↵
~~~~~↵

</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en13 Английский MarkBcc168 2022-07-23 10:48:13 4
en12 Английский MarkBcc168 2022-07-15 19:44:48 17
en11 Английский MarkBcc168 2022-07-15 19:40:13 122
en10 Английский MarkBcc168 2022-07-15 19:23:34 20
en9 Английский MarkBcc168 2022-07-15 18:53:37 0 (published)
en8 Английский MarkBcc168 2022-07-15 18:53:06 386
en7 Английский MarkBcc168 2022-07-15 18:22:23 3104 Add the bitset solutions + Mention the block solution in D.
en6 Английский MarkBcc168 2022-07-15 17:38:27 145
en5 Английский MarkBcc168 2022-07-15 17:36:04 280
en4 Английский MarkBcc168 2022-07-15 13:01:43 46 remove //debug() in E, fix spacing in F
en3 Английский MarkBcc168 2022-07-15 12:56:24 55 fix the align in F
en2 Английский MarkBcc168 2022-07-15 11:37:39 15347 D,E,F done
en1 Английский MarkBcc168 2022-07-15 07:41:53 6576 A,B,C done (saved to drafts)