Thanks for participating. 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).* We will directly show that $h_{n+i} - h_i \geq x$ for all $i$.↵
↵
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 two people got assigned to the same row.↵
↵
However, the difference of heights between these two people is at most $h_{n+i}-h_i$, implying 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$ is 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* < 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 <bits/stdc++.hiostream>↵
#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">↵
You can't keep the entire string, but there is an efficient way to track what letter each index comes fromWhat'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]↵
↵
[problem:1705E]↵
↵
Author: [user:abc241,2022-07-15]↵
↵
[problem:1705F]↵
↵
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 $s$ and $b_1,b_2,\dots,b_k$ are the positions of $1$'s in $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.↵
</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 must be at least $2^{\text{ans}}$.↵
↵
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">↵
↵
~~~~~↵
#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);↵
}↵
//debug();↵
};↵
↵
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);↵
}↵
//debug();↵
};↵
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]↵
↵
<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>↵
↵
↵
[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).* We will directly show that $h_{n+i} - h_i \geq x$ for all $i$.↵
↵
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 two people got assigned to the same row.↵
↵
However, the difference of heights between these two people is at most $h_{n+i}-h_i$, implying 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$ is 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() {↵
cin >> n >> x;↵
}↵
↵
int main() {↵
}↵
↵
~~~~~↵
↵
</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 <
#include <vector>↵
#define ll long long↵
↵
using namespace std;↵
↵
↵
void solve(){↵
int n; cin >> n;↵
vector<int> a(n);↵
for(int i
cin >> a[i];↵
ll ans = 0;↵
int ptr = 0;↵
while(ptr < n && a[ptr] == 0)↵
ptr++;↵
for(int 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">↵
↵
↵
<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(){↵
↵
↵
cout << s[k] << "\n";↵
↵
}↵
↵
int main(){↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
[problem:1705D]↵
----------------↵
↵
Author: [user:MarkBcc168,2022-07-15]↵
↵
↵
Author: [user:abc241,2022-07-15]↵
↵
[problem:1705F]↵
↵
Author: [user:MarkBcc168,2022-07-15]
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 $s$ and $b_1,b_2,\dots,b_k$ are the positions of $1$'s in $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.↵
</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 must be at least $2^{\text{ans}}$.↵
↵
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">↵
↵
~~~~~↵
#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);↵
}↵
//debug();↵
};↵
↵
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);↵
}↵
//debug();↵
};↵
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]↵
↵
<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>↵
↵
