thanks to [user:nifeshe,2026-10-10] for making my life easier with templates ↵
↵
[problem:2271A]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> After performing $z$ operations, the robot's $x$-coordinate is exactly $z$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> After completing any operation, the $x$-coordinate and $y$-coordinate always have the same parity. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Try to find a construction to reach any point $(x,y)$ where $y\le x$ and $x$ and $y$ have the same parity. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Notice that after performing $z$ operations, the robot's $x$-coordinate will be exactly $z$, while its $y$-coordinate cannot exceed $z$.↵
↵
We will first consider the case $b\le a$, then handle the special case $b=a+1$.↵
↵
Notice that the robot can reach any point $(x,y)$ where $0\le y\le x$ and $x$ and $y$ have the same parity in exactly $x$ operations. To do so, we can first move up until reaching $y$, then alternate between moving up and down.↵
↵
But what if $x$ and $y$ have different parities?↵
↵
In this case, we can reach $(x,y-1)$ in exactly $x$ operations, since $x$ and $y-1$ have the same parity.↵
↵
Now, recall that in each operation, the robot moves vertically **before** moving horizontally. Therefore, we can perform one additional operation:↵
↵
$$(x,y-1)\rightarrow(x,y)\rightarrow(x+1,y).$$↵
↵
The robot visits $(x,y)$ during this operation, so the answer is $x+1$.↵
↵
Now, let's consider the remaining cases:↵
↵
- If $b=a+1$, we can use the same construction, since $a$ and $b$ have different parities. We reach $(a,b-1)=(a,a)$ in $a$ operations, then visit $(a,b)$ during the next operation. Thus, the answer is $a+1$.↵
- If $b>a+1$, reaching $(a,b)$ is impossible, since the robot can make at most $a+1$ vertical moves before leaving column $a$.↵
↵
Therefore, the answer is:↵
↵
- $-1$ if $b>a+1$.↵
- $a$ if $a$ and $b$ have the same parity.↵
- $a+1$ otherwise.↵
↵
The time complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int a, b;↵
cin >> a >> b;↵
if (b > a + 1) cout << -1 << '\n';↵
else if (a % 2 == b % 2) cout << a << '\n';↵
else cout << a + 1 << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 1, option1] Good Problem ↵
- [likes: 1, option2] Okay Problem ↵
- [likes: 1, option3] Bad Problem ↵
- [likes: 1, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271B]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Let $cnt[x]$ be the number of cards containing $x$. Consider the smallest $x$ such that $cnt[x]<2k$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> What happens if $cnt[x]=2k-1$? Can Alice and Bob have the same $\operatorname{mex}_k$? </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> If $cnt[x]\le 2k-2$, try finding a winning strategy for Bob by pairing cards with the same value. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
↵
Let $cnt[x]$ be the number of cards containing $x$.↵
↵
We will consider the integers $x=0,1,2,\ldots$ in increasing order, and find the first $x$ such that $cnt[x]<2k$.↵
↵
We claim that **Alice wins if and only if $cnt[x]=2k-1$**.↵
↵
Let's prove this by considering two cases.↵
↵
**Case 1: $cnt[x]=2k-1$.**↵
↵
We will show that it is impossible for Alice and Bob to have the same $\operatorname{mex}_k$, regardless of how they play.↵
↵
Suppose both players have the same $\operatorname{mex}_k=y$. We consider three cases:↵
↵
- If $y<x$, both players must have fewer than $k$ cards containing $y$. This is impossible because $cnt[y]\ge 2k$.↵
- If $y=x$, both players must again have fewer than $k$ cards containing $x$. This is impossible because $cnt[x]=2k-1$.↵
- If $y>x$, both players must have at least $k$ cards containing $x$. This is also impossible because $cnt[x]=2k-1<2k$.↵
↵
Therefore, there is no possible value of $y$ for which both players have the same $\operatorname{mex}_k$.↵
↵
Thus, **Alice always wins**, regardless of how either player plays.↵
↵
**Case 2: $cnt[x]\le 2k-2$.**↵
↵
We will show that Bob can always make both MEX values equal.↵
↵
Bob can use the following strategy: pair as many cards with the same value as possible, then pair the remaining cards arbitrarily. Whenever Alice takes a card, Bob takes the other card from its pair.↵
↵
This guarantees that each player receives either $\lfloor cnt[y]/2\rfloor$ or $\lceil cnt[y]/2\rceil$ cards containing any integer $y$.↵
↵
Now notice that:↵
↵
- For every $y<x$, we have $cnt[y]\ge 2k$, so both players receive at least $k$ cards containing $y$.↵
- For $y=x$, we have $cnt[x]\le 2k-2$, so both players receive fewer than $k$ cards containing $x$.↵
↵
Therefore, both players have $\operatorname{mex}_k=x$, and Bob wins.↵
↵
Thus, we only need to find the first $x$ with $cnt[x]<2k$. The answer is "YES" if $cnt[x]=2k-1$, and "NO" otherwise.↵
↵
The time complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> cnt(n + 1, 0);↵
for (int i = 0; i < n; ++i) {↵
int a;↵
cin >> a;↵
++cnt[a];↵
}↵
↵
for (int x = 0; x <= n; ++x) {↵
if (cnt[x] < 2 * k) {↵
cout << (cnt[x] == 2 * k - 1 ? "YES\n" : "NO\n");↵
break;↵
}↵
}↵
}↵
↵
return 0;↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 2, option1] Good Problem ↵
- [likes: 2, option2] Okay Problem ↵
- [likes: 2, option3] Bad Problem ↵
- [likes: 2, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271C]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Consider the prefix XOR array $p$. A subarray $[l,r]$ has XOR $0$ if and only if $p_{l-1}=p_r$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> How does the beauty change when a prefix XOR appears for the first, second, or third time? </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Try constructing a prefix XOR array where every possible value appears exactly twice, while ensuring that $p_{i-1}\oplus p_i\le n$. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Let $x$ be the greatest power of $2$ not exceeding $n$.↵
↵
Define the prefix XOR array $p$ as follows:↵
↵
- $p_0=0$.↵
- $p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$.↵
↵
Notice that a subarray $[l,r]$ has XOR equal to $0$ if and only if $p_{l-1}=p_r$.↵
↵
Also, since $a_i\le n<2x$, none of the elements has a set bit greater than or equal to $2x$. Therefore, every prefix XOR belongs to the range $[0,2x-1]$.↵
↵
Now, let's see what happens when we add a new prefix XOR $p_i$:↵
↵
- If $p_i$ has never appeared before, no new subarray with XOR $0$ is created, so the beauty increases by $1$.↵
- If $p_i$ has appeared exactly once, exactly one new subarray with XOR $0$ is created, so the beauty stays the same.↵
- If $p_i$ has appeared at least twice, the beauty decreases.↵
↵
Since there are only $2x$ possible prefix XOR values, and $p_0=0$ already exists, the **maximum possible beauty is at most $2x-1$**.↵
↵
To achieve this beauty with the maximum possible length, we want every prefix XOR from $0$ to $2x-1$ to appear exactly twice.↵
↵
This gives us $4x$ prefix XORs, corresponding to an array of length $4x-1$.↵
↵
Now, let's show how to construct such an array.↵
↵
Instead of constructing $a$ directly, we will construct the prefix XOR array $p$, then recover $a$ using $a_i=p_{i-1}\oplus p_i$.↵
↵
First, visit all integers from $0$ to $x-1$ in increasing order, then visit them again in decreasing order:↵
↵
$$0,1,\ldots,x-1,x-1,\ldots,1,0.$$↵
↵
After that, do the same for all integers from $x$ to $2x-1$:↵
↵
$$x,x+1,\ldots,2x-1,2x-1,\ldots,x+1,x.$$↵
↵
Clearly, every integer from $0$ to $2x-1$ appears exactly twice.↵
↵
We only need to verify that every $a_i=p_{i-1}\oplus p_i$ is at most $n$.↵
↵
Notice that:↵
↵
- The XOR of any two integers from $[0,x-1]$ is smaller than $x$.↵
- The XOR of any two integers from $[x,2x-1]$ is also smaller than $x$, since their highest set bits cancel.↵
- The only jump between these two ranges is from $0$ to $x$, whose XOR is exactly $x$.↵
↵
Therefore, every element of $a$ is at most $x\le n$, so our construction is valid.↵
↵
Since every prefix XOR appears exactly twice, we have exactly $2x$ subarrays with XOR $0$. Thus, the beauty is↵
↵
$$(4x-1)-2x=2x-1,$$↵
↵
which achieves the maximum possible beauty with the maximum possible length.↵
↵
The time complexity is $O(n)$ per test case.↵
↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
int x = 1;↵
while (2 * x <= n) x *= 2;↵
↵
vector<int> p;↵
for (int i = 0; i < x; i++) p.push_back(i);↵
for (int i = x - 1; i >= 0; i--) p.push_back(i);↵
for (int i = x; i < 2 * x; i++) p.push_back(i);↵
for (int i = 2 * x - 1; i >= x; i--) p.push_back(i);↵
↵
cout << (int)p.size() - 1 << '\n';↵
for (int i = 1; i < (int)p.size(); i++)↵
cout << (p[i] ^ p[i - 1]) << " \n"[i == (int)p.size() - 1];↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 3, option1] Good Problem ↵
- [likes: 3, option2] Okay Problem ↵
- [likes: 3, option3] Bad Problem ↵
- [likes: 3, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271D]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Notice that $|f(s+1)-f(s)|\le 1$. How can we use this property? </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Prove that the maximum value of $f(s)$ is achieved at some $s=l_i$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> After finding a position $pos$ with maximum $f(pos)$, try using binary search to find a position $s$ where $f(s)=k$, even though $f(s)$ is not monotonic. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Let $f(s)$ be the number of infected positions in the segment $[s,s+m-1]$.↵
↵
First, notice that when we increase $s$ by $1$, we remove the position $s$ and add the position $s+m$.↵
↵
Therefore, **$f(s)$ can change by at most $1$** when we increase $s$ by $1$.↵
↵
This observation will be useful later.↵
↵
Now, let's find the maximum possible value of $f(s)$.↵
↵
We claim that **the maximum is achieved at some $s=l_i$**.↵
↵
To see why, consider any starting position $s$:↵
↵
- If $s$ is infected but is not the beginning of an infection interval, we can move $s$ to the left by $1$. Since the newly added position is infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of that interval.↵
- If $s$ is not infected, we can move $s$ to the right by $1$. Since the removed position is not infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of the next infection interval.↵
↵
Therefore, it is sufficient to check $f(l_i)$ for every interval.↵
↵
Let $mx$ be the maximum value we find, and let $pos$ be a position where $f(pos)=mx$.↵
↵
Now, we have three cases:↵
↵
- If $k>mx$, the answer is $-1$, since we cannot infect that many people.↵
- If $k=mx$, we can simply output $pos$.↵
- Otherwise, $k<mx$, and we will find a valid position using binary search.↵
↵
↵
Now, suppose $k<mx$. We know that $f(pos)=mx>k$, and we also know that $f(10^{15}+1)=0\le k$, since there are no infected positions after $10^{15}$.↵
↵
Therefore, we have two positions: one where $f(s)>k$, and another where $f(s)\le k$.↵
↵
Recall that **moving $s$ by $1$ changes $f(s)$ by at most $1$**. This means that somewhere between these two positions, there must be a position where $f(s)=k$.↵
↵
We can find such a position using binary search!↵
↵
Maintain two positions $l$ and $r$ such that $f(l)>k$ and $f(r)\le k$. Initially, set $l=pos$ and $r=10^{15}+1$.↵
↵
Let $mid=\lfloor(l+r)/2\rfloor$.↵
↵
- If $f(mid)>k$, set $l=mid$.↵
- Otherwise, set $r=mid$.↵
↵
Notice that we always keep one position with $f(s)>k$ and another with $f(s)\le k$, so we never lose the guarantee that a valid answer exists between them.↵
↵
Continue until $r=l+1$.↵
↵
Now, since $f(l)>k$ and $f(r)\le k$, and these positions are adjacent, we must have $f(r)=k$. Therefore, we can output $r$.↵
↵
**Note that $f(s)$ does not need to be monotonic for this binary search to work!** We only need the fact that $f(s)$ changes by at most $1$ between consecutive positions.↵
↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
long long m, k;↵
cin >> n >> m >> k;↵
↵
vector<long long> l(n), r(n), pref(n + 1);↵
for (int i = 0; i < n; i++) {↵
cin >> l[i] >> r[i];↵
pref[i + 1] = pref[i] + r[i] - l[i] + 1;↵
}↵
↵
auto f = [&](long long s) -> long long {↵
long long e = s + m - 1;↵
↵
int i = lower_bound(r.begin(), r.end(), s) - r.begin();↵
int j = upper_bound(l.begin(), l.end(), e) - l.begin() - 1;↵
↵
if (i > j) return 0;↵
↵
long long ans = pref[j + 1] - pref[i];↵
ans -= max(0LL, s - l[i]);↵
ans -= max(0LL, r[j] - e);↵
return ans;↵
};↵
↵
long long mx = -1, pos = 0;↵
for (int i = 0; i < n; i++) {↵
long long cur = f(l[i]);↵
if (cur > mx) {↵
mx = cur;↵
pos = l[i];↵
}↵
}↵
↵
if (k > mx) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
if (k == mx) {↵
cout << pos << '\n';↵
return;↵
}↵
↵
long long low = pos, high = 1000000000000001LL;↵
↵
while (high - low > 1) {↵
long long mid = (low + high) / 2;↵
if (f(mid) > k) low = mid;↵
else high = mid;↵
}↵
↵
cout << high << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 4, option1] Good Problem ↵
- [likes: 4, option2] Okay Problem ↵
- [likes: 4, option3] Bad Problem ↵
- [likes: 4, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271E]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Try solving a relaxed version where we can split any element, even if it is smaller than or equal to $k$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Show that we can perform all splits before any erasures, then process the erasures in reverse order. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Binary search on the number of splits. When processing backward, consider the largest remaining element: should we erase it or split it? </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
First, let's solve a **relaxed version** of the problem, where we are allowed to split any element, even if it is already small enough to be erased.↵
↵
Let's find a greedy solution for this relaxed version.↵
↵
Suppose we perform exactly $c$ splits. Each split increases the number of elements by $1$, so we will need $n+c$ erasures.↵
↵
Therefore, the total number of operations is↵
↵
$$n+2c.$$↵
↵
Now, notice that **we can always perform all splits before any erasures**.↵
↵
We can prove this using an exchange argument. If a split happens after an erasure, we can swap these two operations. The split remains valid because splitting is always allowed in our relaxed version, and the erasure remains valid because $k$ only increases.↵
↵
By repeatedly applying this argument, we can rearrange the operations into the following order:↵
↵
$$\underbrace{\text{split},\ldots,\text{split}}_{c},\underbrace{\text{erase},\ldots,\text{erase}}_{n+c}.$$↵
↵
Now, let's binary search on the number of splits $c$.↵
↵
To check whether $c$ splits are sufficient, we will **process the erasures in reverse order**, starting from the last erasure and moving toward the first.↵
↵
The value of $k$ at the last operation is↵
↵
$$S=k+n+2c-1.$$↵
↵
Let $H$ be the largest remaining element.↵
↵
We have two cases:↵
↵
- **If $H>S$**, we must split $H$, since we cannot erase it now, and we certainly cannot erase it at any earlier operation, where $k$ is even smaller.↵
↵
- **If $H\le S$**, we claim that it is optimal to erase $H$ now.↵
↵
Let's prove the second case.↵
↵
Consider an optimal solution that does not erase $H$ at this moment. There are two possibilities:↵
↵
1. **It erases $H$ at an earlier operation.** In this case, we can simply swap that erasure with the current one. This is valid because $H\le S$, and the other element, being no larger than $H$, can also be erased earlier.↵
↵
2. **It splits $H$ instead.** Suppose it erases some smaller element $y$ at this moment. We can instead erase $H$ and split $y$. Since $y\le H$, the two elements produced by splitting $y$ are no larger than those produced by splitting $H$. Therefore, we can perform the same subsequent operations without making anything harder. If the element erased at this moment was itself produced by splitting $H$, we can simply erase $H$ instead and avoid those splits.↵
↵
Thus, in both cases, there exists an optimal solution that erases $H$ now.↵
↵
This proves our greedy strategy.↵
↵
Whenever we erase an element, we decrease $S$ by $1$, since we move to the previous erasure. Whenever we split an element, we replace it with two elements equal to $\lceil H/2\rceil$, without changing $S$.↵
↵
If we need more than $c$ splits, the check fails. Otherwise, it succeeds.↵
↵
We can implement this efficiently using a frequency array to maintain the remaining elements.↵
↵
Now, let $X$ be the minimum number of operations for the relaxed problem.↵
↵
Clearly, the answer to the original problem is **at least $X$**, since the relaxed problem allows everything the original problem allows.↵
↵
However, notice something important about our greedy construction: **we only split an element when $H>S$**.↵
↵
Since $S$ is at least the value of $k$ when that split would actually happen, we also have $H>k$ at that moment.↵
↵
Therefore, every split performed by our greedy solution is valid in the original problem as well!↵
↵
This means our solution to the relaxed problem is also a valid solution to the original problem, so the minimum number of operations is the same for both.↵
↵
Finally, if $c$ is the minimum number of splits found by binary search, the answer is↵
↵
$$\boxed{n+2c}.$$↵
↵
The time complexity is $O(n\log n)$ per test case, and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> a(n);↵
int mx = 0;↵
for (int &x : a) {↵
cin >> x;↵
mx = max(mx, x);↵
}↵
↵
vector<int> freq(mx + 1);↵
for (int x : a) freq[x]++;↵
↵
auto ok = [&](int c) {↵
vector<int> cnt = freq;↵
int alive = n, used = 0, H = mx;↵
long long S = 1LL * k + n + 2LL * c - 1;↵
↵
while (alive > 0) {↵
while (cnt[H] == 0) H--;↵
↵
if (H <= S) {↵
cnt[H]--;↵
alive--;↵
S--;↵
} else {↵
if (used == c) return false;↵
cnt[H]--;↵
cnt[(H + 1) / 2] += 2;↵
alive++;↵
used++;↵
}↵
}↵
return true;↵
};↵
↵
int l = 0, r = max(0, mx - k);↵
while (l < r) {↵
int mid = (l + r) / 2;↵
if (ok(mid)) r = mid;↵
else l = mid + 1;↵
}↵
↵
cout << n + 2 * l << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 5, option1] Good Problem ↵
- [likes: 5, option2] Okay Problem ↵
- [likes: 5, option3] Bad Problem ↵
- [likes: 5, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271F]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Notice that we can always make the array beautiful using at most $2$ operations. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Let $mx$ be the maximum element. Try setting $a_1=mx$ or $a_n=mx$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> If neither works, can we make the array beautiful by changing one occurrence of $mx$ to something? </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
↵
First, notice that we can always make the array beautiful using at most **$2$ operations**, by setting $a_1=a_n=10^9$.↵
↵
Now, let's check whether the array is already beautiful. If it is, the answer is $0$.↵
↵
Otherwise, the answer must be either $1$ or $2$.↵
↵
We claim that **if the answer is $1$, at least one of the following three operations makes the array beautiful**.↵
↵
Let $mx$ be the maximum element of the array, and let $pos$ be any position such that $a_{pos}=mx$.↵
↵
The three operations are:↵
↵
1. Set $a_1=mx$.↵
2. Set $a_n=mx$.↵
3. Set $a_{pos}=1$.↵
↵
We can simply try each operation and check whether the resulting array is beautiful. If any of them works, the answer is $1$. Otherwise, the answer is $2$.↵
↵
Now, let's prove why these three cases are sufficient.↵
↵
Imagine the array looks like this:↵
↵
$$\underbrace{\text{xxxxx}}_{\text{left}}\quad mx\quad\underbrace{\text{xxxxx}}_{\text{right}}.$$↵
↵
Notice that setting $a_1=mx$ makes the entire left side covered by good pairs, while setting $a_n=mx$ does the same for the right side.↵
↵
If neither operation makes the array beautiful, this means there are still uncovered positions on both sides.↵
↵
Therefore, if we want to fix everything using only one operation, we must somehow fix both sides at once.↵
↵
The only remaining possibility is to **decrease a maximum element**, allowing good pairs to connect across it.↵
↵
Suppose changing this maximum element to some value $X$ makes the array beautiful.↵
↵
We claim that changing it to $1$ would also work.↵
↵
Why? Any new good pair that spans this position remains good if we decrease its value even further.↵
↵
The other possibility is that the new value $X$ creates two good pairs, one on each side, looking like this:↵
↵
$$X\quad\ldots\quad X\quad\ldots\quad X.$$↵
↵
Here, the middle $X$ is the element we changed, and both pairs are good.↵
↵
If we decrease the middle element to $1$, the two pairs can be replaced by one larger good pair:↵
↵
$$X\quad\ldots\quad 1\quad\ldots\quad X.$$↵
↵
Thus, decreasing the maximum element to $1$ is sufficient.↵
↵
lets also note if that max element occurs more than once this is useless.↵
↵
This proves that checking our three operations is enough to find an optimal solution.↵
↵
Finally, checking whether an array is beautiful can be implemented in $O(n\log n)$ using several approaches, or in $O(n)$ using a monotonic stack.↵
↵
Since we perform only a constant number of checks, the overall time complexity is **$O(n)$** per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
bool beautiful(vector<int>& a) {↵
int n = a.size();↵
vector<int> st, diff(n + 1);↵
↵
for (int i = 0; i < n; i++) {↵
while (!st.empty() && a[st.back()] < a[i])↵
st.pop_back();↵
↵
if (!st.empty() && a[st.back()] == a[i]) {↵
diff[st.back()]++;↵
diff[i + 1]--;↵
}↵
st.push_back(i);↵
}↵
↵
int cur = 0;↵
for (int i = 0; i < n; i++) {↵
cur += diff[i];↵
if (cur == 0) return false;↵
}↵
return true;↵
}↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (int &x : a) cin >> x;↵
↵
if (beautiful(a)) {↵
cout << 0 << '\n';↵
return;↵
}↵
↵
int pos = max_element(a.begin(), a.end()) - a.begin();↵
int mx = a[pos];↵
↵
auto check = [&](int i, int x) {↵
int old = a[i];↵
a[i] = x;↵
bool ok = beautiful(a);↵
a[i] = old;↵
if (ok) {↵
cout << 1 << '\n';↵
cout << i + 1 << ' ' << x << '\n';↵
}↵
return ok;↵
};↵
↵
if (check(0, mx)) return;↵
if (check(n - 1, mx)) return;↵
if (check(pos, 1)) return;↵
↵
cout << 2 << '\n';↵
cout << 1 << ' ' << mx << '\n';↵
cout << n << ' ' << mx << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 6, option1] Good Problem ↵
- [likes: 6, option2] Okay Problem ↵
- [likes: 6, option3] Bad Problem ↵
- [likes: 6, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271G]↵
↵
<spoiler summary = "Solution">↵
↵
First, let's determine when it is **impossible** to fill the grid.↵
↵
Suppose there are two $1\times 1$ pieces in the same row, with only $1\times 2$ pieces between them.↵
↵
For example:↵
↵
$$x\ |\ x\ x\ |\ x\ x\ |\ x\ x\ |\ x$$↵
↵
Since every $1\times 1$ piece must contain $1$, the first cell is forced to be $1$. This forces the next $1\times 2$ piece to be $[2,1]$, and the same applies to every following piece.↵
↵
We end up with:↵
↵
$$1\ |\ 2\ 1\ |\ 2\ 1\ |\ 2\ 1\ |\ 1$$↵
↵
Clearly, this is invalid because the last two adjacent cells both contain $1$.↵
↵
The same argument applies vertically to two $1\times 1$ pieces with only $2\times 1$ pieces between them.↵
↵
We claim that **these are the only cases where a valid filling is impossible**.↵
↵
Let's prove this by constructing a valid filling whenever neither case occurs.↵
↵
**Step 1: Fill all thin pieces.**↵
↵
First, put $1$ in every $1\times 1$ piece.↵
↵
Now, let's fill all $1\times y$ and $y\times 1$ pieces.↵
↵
We will only explain the construction for horizontal pieces, since vertical pieces can be handled in exactly the same way.↵
↵
Consider any two $1\times 1$ pieces in the same row.↵
↵
Since our impossible condition does not occur, there must be at least one $1\times y$ piece between them with $y\ge 3$.↵
↵
Choose the first such piece from the left and call it the **turning point**.↵
↵
We fill the pieces between the two $1\times 1$ pieces as follows:↵
↵
- For every piece before the turning point, write its numbers in decreasing order.↵
- For every piece after the turning point, write its numbers in increasing order.↵
- For the turning point itself, use the order $[y,1,2,3,\ldots,y-1]$.↵
↵
Notice that this guarantees that adjacent cells contain different numbers, including across the boundaries of the pieces.↵
↵
For portions of the row before the first $1\times 1$ piece, after the last one, or rows containing no $1\times 1$ pieces, we can simply choose a suitable increasing or decreasing order.↵
↵
We apply the same construction vertically to fill all remaining $y\times 1$ pieces.↵
↵
↵
↵
**Step 2: Fill the rows containing $1$.**↵
↵
Notice that by choosing our coloring patterns consistently in the previous step, the already-colored cells in each partially filled row contain the same value.↵
↵
Now, consider every partially filled row whose already-colored cells contain $1$.↵
↵
We can fill the gaps between these $1$ s using exactly the same turning-point construction from Step 1.↵
↵
This fills all such rows while ensuring that horizontally adjacent cells contain different numbers.↵
↵
↵
↵
**Step 3: Fill the remaining cells.**↵
↵
Now, let's consider the remaining unfilled rows.↵
↵
The important observation is that **these rows can be handled independently**, since the vertical constraints have already been taken care of by our construction.↵
↵
Furthermore, every gap we need to fill has the same value, say $x$, on both its left and right boundaries.↵
↵
Therefore, we only need to arrange the remaining numbers inside each piece so that adjacent values are different and neither boundary creates a conflict.↵
↵
We can use the same idea as before: arrange the values in increasing or decreasing order, and use a turning point whenever necessary.↵
↵
Since the required values are available and the vertical constraints are already satisfied, we can fill all remaining gaps.↵
↵
Thus, we have constructed a valid filling whenever neither of the two impossible configurations occurs, completing the proof.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 7, option1] Good Problem ↵
- [likes: 7, option2] Okay Problem ↵
- [likes: 7, option3] Bad Problem ↵
- [likes: 7, option4] Didn't Solve↵
</spoiler>↵
↵
↵
[problem:2271H2]↵
↵
<spoiler summary = "Solution">↵
Editorial will be Added when Axial isn't tired :(↵
↵
if you have any non slop solutions please comment them below↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 8, option1] Good Problem ↵
- [likes: 8, option2] Okay Problem ↵
- [likes: 8, option3] Bad Problem ↵
- [likes: 8, option4] Didn't Solve↵
</spoiler>↵
↵
↵
[problem:2271A]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> After performing $z$ operations, the robot's $x$-coordinate is exactly $z$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> After completing any operation, the $x$-coordinate and $y$-coordinate always have the same parity. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Try to find a construction to reach any point $(x,y)$ where $y\le x$ and $x$ and $y$ have the same parity. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Notice that after performing $z$ operations, the robot's $x$-coordinate will be exactly $z$, while its $y$-coordinate cannot exceed $z$.↵
↵
We will first consider the case $b\le a$, then handle the special case $b=a+1$.↵
↵
Notice that the robot can reach any point $(x,y)$ where $0\le y\le x$ and $x$ and $y$ have the same parity in exactly $x$ operations. To do so, we can first move up until reaching $y$, then alternate between moving up and down.↵
↵
But what if $x$ and $y$ have different parities?↵
↵
In this case, we can reach $(x,y-1)$ in exactly $x$ operations, since $x$ and $y-1$ have the same parity.↵
↵
Now, recall that in each operation, the robot moves vertically **before** moving horizontally. Therefore, we can perform one additional operation:↵
↵
$$(x,y-1)\rightarrow(x,y)\rightarrow(x+1,y).$$↵
↵
The robot visits $(x,y)$ during this operation, so the answer is $x+1$.↵
↵
Now, let's consider the remaining cases:↵
↵
- If $b=a+1$, we can use the same construction, since $a$ and $b$ have different parities. We reach $(a,b-1)=(a,a)$ in $a$ operations, then visit $(a,b)$ during the next operation. Thus, the answer is $a+1$.↵
- If $b>a+1$, reaching $(a,b)$ is impossible, since the robot can make at most $a+1$ vertical moves before leaving column $a$.↵
↵
Therefore, the answer is:↵
↵
- $-1$ if $b>a+1$.↵
- $a$ if $a$ and $b$ have the same parity.↵
- $a+1$ otherwise.↵
↵
The time complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int a, b;↵
cin >> a >> b;↵
if (b > a + 1) cout << -1 << '\n';↵
else if (a % 2 == b % 2) cout << a << '\n';↵
else cout << a + 1 << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) {↵
solve();↵
}↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 1, option1] Good Problem ↵
- [likes: 1, option2] Okay Problem ↵
- [likes: 1, option3] Bad Problem ↵
- [likes: 1, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271B]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Let $cnt[x]$ be the number of cards containing $x$. Consider the smallest $x$ such that $cnt[x]<2k$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> What happens if $cnt[x]=2k-1$? Can Alice and Bob have the same $\operatorname{mex}_k$? </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> If $cnt[x]\le 2k-2$, try finding a winning strategy for Bob by pairing cards with the same value. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
↵
Let $cnt[x]$ be the number of cards containing $x$.↵
↵
We will consider the integers $x=0,1,2,\ldots$ in increasing order, and find the first $x$ such that $cnt[x]<2k$.↵
↵
We claim that **Alice wins if and only if $cnt[x]=2k-1$**.↵
↵
Let's prove this by considering two cases.↵
↵
**Case 1: $cnt[x]=2k-1$.**↵
↵
We will show that it is impossible for Alice and Bob to have the same $\operatorname{mex}_k$, regardless of how they play.↵
↵
Suppose both players have the same $\operatorname{mex}_k=y$. We consider three cases:↵
↵
- If $y<x$, both players must have fewer than $k$ cards containing $y$. This is impossible because $cnt[y]\ge 2k$.↵
- If $y=x$, both players must again have fewer than $k$ cards containing $x$. This is impossible because $cnt[x]=2k-1$.↵
- If $y>x$, both players must have at least $k$ cards containing $x$. This is also impossible because $cnt[x]=2k-1<2k$.↵
↵
Therefore, there is no possible value of $y$ for which both players have the same $\operatorname{mex}_k$.↵
↵
Thus, **Alice always wins**, regardless of how either player plays.↵
↵
**Case 2: $cnt[x]\le 2k-2$.**↵
↵
We will show that Bob can always make both MEX values equal.↵
↵
Bob can use the following strategy: pair as many cards with the same value as possible, then pair the remaining cards arbitrarily. Whenever Alice takes a card, Bob takes the other card from its pair.↵
↵
This guarantees that each player receives either $\lfloor cnt[y]/2\rfloor$ or $\lceil cnt[y]/2\rceil$ cards containing any integer $y$.↵
↵
Now notice that:↵
↵
- For every $y<x$, we have $cnt[y]\ge 2k$, so both players receive at least $k$ cards containing $y$.↵
- For $y=x$, we have $cnt[x]\le 2k-2$, so both players receive fewer than $k$ cards containing $x$.↵
↵
Therefore, both players have $\operatorname{mex}_k=x$, and Bob wins.↵
↵
Thus, we only need to find the first $x$ with $cnt[x]<2k$. The answer is "YES" if $cnt[x]=2k-1$, and "NO" otherwise.↵
↵
The time complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
↵
while (t--) {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> cnt(n + 1, 0);↵
for (int i = 0; i < n; ++i) {↵
int a;↵
cin >> a;↵
++cnt[a];↵
}↵
↵
for (int x = 0; x <= n; ++x) {↵
if (cnt[x] < 2 * k) {↵
cout << (cnt[x] == 2 * k - 1 ? "YES\n" : "NO\n");↵
break;↵
}↵
}↵
}↵
↵
return 0;↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 2, option1] Good Problem ↵
- [likes: 2, option2] Okay Problem ↵
- [likes: 2, option3] Bad Problem ↵
- [likes: 2, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271C]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Consider the prefix XOR array $p$. A subarray $[l,r]$ has XOR $0$ if and only if $p_{l-1}=p_r$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> How does the beauty change when a prefix XOR appears for the first, second, or third time? </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Try constructing a prefix XOR array where every possible value appears exactly twice, while ensuring that $p_{i-1}\oplus p_i\le n$. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Let $x$ be the greatest power of $2$ not exceeding $n$.↵
↵
Define the prefix XOR array $p$ as follows:↵
↵
- $p_0=0$.↵
- $p_i=a_1\oplus a_2\oplus\cdots\oplus a_i$.↵
↵
Notice that a subarray $[l,r]$ has XOR equal to $0$ if and only if $p_{l-1}=p_r$.↵
↵
Also, since $a_i\le n<2x$, none of the elements has a set bit greater than or equal to $2x$. Therefore, every prefix XOR belongs to the range $[0,2x-1]$.↵
↵
Now, let's see what happens when we add a new prefix XOR $p_i$:↵
↵
- If $p_i$ has never appeared before, no new subarray with XOR $0$ is created, so the beauty increases by $1$.↵
- If $p_i$ has appeared exactly once, exactly one new subarray with XOR $0$ is created, so the beauty stays the same.↵
- If $p_i$ has appeared at least twice, the beauty decreases.↵
↵
Since there are only $2x$ possible prefix XOR values, and $p_0=0$ already exists, the **maximum possible beauty is at most $2x-1$**.↵
↵
To achieve this beauty with the maximum possible length, we want every prefix XOR from $0$ to $2x-1$ to appear exactly twice.↵
↵
This gives us $4x$ prefix XORs, corresponding to an array of length $4x-1$.↵
↵
Now, let's show how to construct such an array.↵
↵
Instead of constructing $a$ directly, we will construct the prefix XOR array $p$, then recover $a$ using $a_i=p_{i-1}\oplus p_i$.↵
↵
First, visit all integers from $0$ to $x-1$ in increasing order, then visit them again in decreasing order:↵
↵
$$0,1,\ldots,x-1,x-1,\ldots,1,0.$$↵
↵
After that, do the same for all integers from $x$ to $2x-1$:↵
↵
$$x,x+1,\ldots,2x-1,2x-1,\ldots,x+1,x.$$↵
↵
Clearly, every integer from $0$ to $2x-1$ appears exactly twice.↵
↵
We only need to verify that every $a_i=p_{i-1}\oplus p_i$ is at most $n$.↵
↵
Notice that:↵
↵
- The XOR of any two integers from $[0,x-1]$ is smaller than $x$.↵
- The XOR of any two integers from $[x,2x-1]$ is also smaller than $x$, since their highest set bits cancel.↵
- The only jump between these two ranges is from $0$ to $x$, whose XOR is exactly $x$.↵
↵
Therefore, every element of $a$ is at most $x\le n$, so our construction is valid.↵
↵
Since every prefix XOR appears exactly twice, we have exactly $2x$ subarrays with XOR $0$. Thus, the beauty is↵
↵
$$(4x-1)-2x=2x-1,$$↵
↵
which achieves the maximum possible beauty with the maximum possible length.↵
↵
The time complexity is $O(n)$ per test case.↵
↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
cin >> n;↵
↵
int x = 1;↵
while (2 * x <= n) x *= 2;↵
↵
vector<int> p;↵
for (int i = 0; i < x; i++) p.push_back(i);↵
for (int i = x - 1; i >= 0; i--) p.push_back(i);↵
for (int i = x; i < 2 * x; i++) p.push_back(i);↵
for (int i = 2 * x - 1; i >= x; i--) p.push_back(i);↵
↵
cout << (int)p.size() - 1 << '\n';↵
for (int i = 1; i < (int)p.size(); i++)↵
cout << (p[i] ^ p[i - 1]) << " \n"[i == (int)p.size() - 1];↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 3, option1] Good Problem ↵
- [likes: 3, option2] Okay Problem ↵
- [likes: 3, option3] Bad Problem ↵
- [likes: 3, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271D]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Notice that $|f(s+1)-f(s)|\le 1$. How can we use this property? </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Prove that the maximum value of $f(s)$ is achieved at some $s=l_i$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> After finding a position $pos$ with maximum $f(pos)$, try using binary search to find a position $s$ where $f(s)=k$, even though $f(s)$ is not monotonic. </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
Let $f(s)$ be the number of infected positions in the segment $[s,s+m-1]$.↵
↵
First, notice that when we increase $s$ by $1$, we remove the position $s$ and add the position $s+m$.↵
↵
Therefore, **$f(s)$ can change by at most $1$** when we increase $s$ by $1$.↵
↵
This observation will be useful later.↵
↵
Now, let's find the maximum possible value of $f(s)$.↵
↵
We claim that **the maximum is achieved at some $s=l_i$**.↵
↵
To see why, consider any starting position $s$:↵
↵
- If $s$ is infected but is not the beginning of an infection interval, we can move $s$ to the left by $1$. Since the newly added position is infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of that interval.↵
- If $s$ is not infected, we can move $s$ to the right by $1$. Since the removed position is not infected, $f(s)$ cannot decrease. We can repeat this until reaching the beginning of the next infection interval.↵
↵
Therefore, it is sufficient to check $f(l_i)$ for every interval.↵
↵
Let $mx$ be the maximum value we find, and let $pos$ be a position where $f(pos)=mx$.↵
↵
Now, we have three cases:↵
↵
- If $k>mx$, the answer is $-1$, since we cannot infect that many people.↵
- If $k=mx$, we can simply output $pos$.↵
- Otherwise, $k<mx$, and we will find a valid position using binary search.↵
↵
↵
Now, suppose $k<mx$. We know that $f(pos)=mx>k$, and we also know that $f(10^{15}+1)=0\le k$, since there are no infected positions after $10^{15}$.↵
↵
Therefore, we have two positions: one where $f(s)>k$, and another where $f(s)\le k$.↵
↵
Recall that **moving $s$ by $1$ changes $f(s)$ by at most $1$**. This means that somewhere between these two positions, there must be a position where $f(s)=k$.↵
↵
We can find such a position using binary search!↵
↵
Maintain two positions $l$ and $r$ such that $f(l)>k$ and $f(r)\le k$. Initially, set $l=pos$ and $r=10^{15}+1$.↵
↵
Let $mid=\lfloor(l+r)/2\rfloor$.↵
↵
- If $f(mid)>k$, set $l=mid$.↵
- Otherwise, set $r=mid$.↵
↵
Notice that we always keep one position with $f(s)>k$ and another with $f(s)\le k$, so we never lose the guarantee that a valid answer exists between them.↵
↵
Continue until $r=l+1$.↵
↵
Now, since $f(l)>k$ and $f(r)\le k$, and these positions are adjacent, we must have $f(r)=k$. Therefore, we can output $r$.↵
↵
**Note that $f(s)$ does not need to be monotonic for this binary search to work!** We only need the fact that $f(s)$ changes by at most $1$ between consecutive positions.↵
↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n;↵
long long m, k;↵
cin >> n >> m >> k;↵
↵
vector<long long> l(n), r(n), pref(n + 1);↵
for (int i = 0; i < n; i++) {↵
cin >> l[i] >> r[i];↵
pref[i + 1] = pref[i] + r[i] - l[i] + 1;↵
}↵
↵
auto f = [&](long long s) -> long long {↵
long long e = s + m - 1;↵
↵
int i = lower_bound(r.begin(), r.end(), s) - r.begin();↵
int j = upper_bound(l.begin(), l.end(), e) - l.begin() - 1;↵
↵
if (i > j) return 0;↵
↵
long long ans = pref[j + 1] - pref[i];↵
ans -= max(0LL, s - l[i]);↵
ans -= max(0LL, r[j] - e);↵
return ans;↵
};↵
↵
long long mx = -1, pos = 0;↵
for (int i = 0; i < n; i++) {↵
long long cur = f(l[i]);↵
if (cur > mx) {↵
mx = cur;↵
pos = l[i];↵
}↵
}↵
↵
if (k > mx) {↵
cout << -1 << '\n';↵
return;↵
}↵
↵
if (k == mx) {↵
cout << pos << '\n';↵
return;↵
}↵
↵
long long low = pos, high = 1000000000000001LL;↵
↵
while (high - low > 1) {↵
long long mid = (low + high) / 2;↵
if (f(mid) > k) low = mid;↵
else high = mid;↵
}↵
↵
cout << high << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 4, option1] Good Problem ↵
- [likes: 4, option2] Okay Problem ↵
- [likes: 4, option3] Bad Problem ↵
- [likes: 4, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271E]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Try solving a relaxed version where we can split any element, even if it is smaller than or equal to $k$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Show that we can perform all splits before any erasures, then process the erasures in reverse order. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> Binary search on the number of splits. When processing backward, consider the largest remaining element: should we erase it or split it? </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
First, let's solve a **relaxed version** of the problem, where we are allowed to split any element, even if it is already small enough to be erased.↵
↵
Let's find a greedy solution for this relaxed version.↵
↵
Suppose we perform exactly $c$ splits. Each split increases the number of elements by $1$, so we will need $n+c$ erasures.↵
↵
Therefore, the total number of operations is↵
↵
$$n+2c.$$↵
↵
Now, notice that **we can always perform all splits before any erasures**.↵
↵
We can prove this using an exchange argument. If a split happens after an erasure, we can swap these two operations. The split remains valid because splitting is always allowed in our relaxed version, and the erasure remains valid because $k$ only increases.↵
↵
By repeatedly applying this argument, we can rearrange the operations into the following order:↵
↵
$$\underbrace{\text{split},\ldots,\text{split}}_{c},\underbrace{\text{erase},\ldots,\text{erase}}_{n+c}.$$↵
↵
Now, let's binary search on the number of splits $c$.↵
↵
To check whether $c$ splits are sufficient, we will **process the erasures in reverse order**, starting from the last erasure and moving toward the first.↵
↵
The value of $k$ at the last operation is↵
↵
$$S=k+n+2c-1.$$↵
↵
Let $H$ be the largest remaining element.↵
↵
We have two cases:↵
↵
- **If $H>S$**, we must split $H$, since we cannot erase it now, and we certainly cannot erase it at any earlier operation, where $k$ is even smaller.↵
↵
- **If $H\le S$**, we claim that it is optimal to erase $H$ now.↵
↵
Let's prove the second case.↵
↵
Consider an optimal solution that does not erase $H$ at this moment. There are two possibilities:↵
↵
1. **It erases $H$ at an earlier operation.** In this case, we can simply swap that erasure with the current one. This is valid because $H\le S$, and the other element, being no larger than $H$, can also be erased earlier.↵
↵
2. **It splits $H$ instead.** Suppose it erases some smaller element $y$ at this moment. We can instead erase $H$ and split $y$. Since $y\le H$, the two elements produced by splitting $y$ are no larger than those produced by splitting $H$. Therefore, we can perform the same subsequent operations without making anything harder. If the element erased at this moment was itself produced by splitting $H$, we can simply erase $H$ instead and avoid those splits.↵
↵
Thus, in both cases, there exists an optimal solution that erases $H$ now.↵
↵
This proves our greedy strategy.↵
↵
Whenever we erase an element, we decrease $S$ by $1$, since we move to the previous erasure. Whenever we split an element, we replace it with two elements equal to $\lceil H/2\rceil$, without changing $S$.↵
↵
If we need more than $c$ splits, the check fails. Otherwise, it succeeds.↵
↵
We can implement this efficiently using a frequency array to maintain the remaining elements.↵
↵
Now, let $X$ be the minimum number of operations for the relaxed problem.↵
↵
Clearly, the answer to the original problem is **at least $X$**, since the relaxed problem allows everything the original problem allows.↵
↵
However, notice something important about our greedy construction: **we only split an element when $H>S$**.↵
↵
Since $S$ is at least the value of $k$ when that split would actually happen, we also have $H>k$ at that moment.↵
↵
Therefore, every split performed by our greedy solution is valid in the original problem as well!↵
↵
This means our solution to the relaxed problem is also a valid solution to the original problem, so the minimum number of operations is the same for both.↵
↵
Finally, if $c$ is the minimum number of splits found by binary search, the answer is↵
↵
$$\boxed{n+2c}.$$↵
↵
The time complexity is $O(n\log n)$ per test case, and the space complexity is $O(n)$.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<int> a(n);↵
int mx = 0;↵
for (int &x : a) {↵
cin >> x;↵
mx = max(mx, x);↵
}↵
↵
vector<int> freq(mx + 1);↵
for (int x : a) freq[x]++;↵
↵
auto ok = [&](int c) {↵
vector<int> cnt = freq;↵
int alive = n, used = 0, H = mx;↵
long long S = 1LL * k + n + 2LL * c - 1;↵
↵
while (alive > 0) {↵
while (cnt[H] == 0) H--;↵
↵
if (H <= S) {↵
cnt[H]--;↵
alive--;↵
S--;↵
} else {↵
if (used == c) return false;↵
cnt[H]--;↵
cnt[(H + 1) / 2] += 2;↵
alive++;↵
used++;↵
}↵
}↵
return true;↵
};↵
↵
int l = 0, r = max(0, mx - k);↵
while (l < r) {↵
int mid = (l + r) / 2;↵
if (ok(mid)) r = mid;↵
else l = mid + 1;↵
}↵
↵
cout << n + 2 * l << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 5, option1] Good Problem ↵
- [likes: 5, option2] Okay Problem ↵
- [likes: 5, option3] Bad Problem ↵
- [likes: 5, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271F]↵
↵
<spoiler summary = "Hints">↵
↵
<spoiler summary = "Hint 1"> Notice that we can always make the array beautiful using at most $2$ operations. </spoiler>↵
↵
↵
<spoiler summary = "Hint 2"> Let $mx$ be the maximum element. Try setting $a_1=mx$ or $a_n=mx$. </spoiler>↵
↵
↵
<spoiler summary = "Hint 3"> If neither works, can we make the array beautiful by changing one occurrence of $mx$ to something? </spoiler>↵
↵
</spoiler>↵
↵
<spoiler summary = "Solution">↵
↵
↵
First, notice that we can always make the array beautiful using at most **$2$ operations**, by setting $a_1=a_n=10^9$.↵
↵
Now, let's check whether the array is already beautiful. If it is, the answer is $0$.↵
↵
Otherwise, the answer must be either $1$ or $2$.↵
↵
We claim that **if the answer is $1$, at least one of the following three operations makes the array beautiful**.↵
↵
Let $mx$ be the maximum element of the array, and let $pos$ be any position such that $a_{pos}=mx$.↵
↵
The three operations are:↵
↵
1. Set $a_1=mx$.↵
2. Set $a_n=mx$.↵
3. Set $a_{pos}=1$.↵
↵
We can simply try each operation and check whether the resulting array is beautiful. If any of them works, the answer is $1$. Otherwise, the answer is $2$.↵
↵
Now, let's prove why these three cases are sufficient.↵
↵
Imagine the array looks like this:↵
↵
$$\underbrace{\text{xxxxx}}_{\text{left}}\quad mx\quad\underbrace{\text{xxxxx}}_{\text{right}}.$$↵
↵
Notice that setting $a_1=mx$ makes the entire left side covered by good pairs, while setting $a_n=mx$ does the same for the right side.↵
↵
If neither operation makes the array beautiful, this means there are still uncovered positions on both sides.↵
↵
Therefore, if we want to fix everything using only one operation, we must somehow fix both sides at once.↵
↵
The only remaining possibility is to **decrease a maximum element**, allowing good pairs to connect across it.↵
↵
Suppose changing this maximum element to some value $X$ makes the array beautiful.↵
↵
We claim that changing it to $1$ would also work.↵
↵
Why? Any new good pair that spans this position remains good if we decrease its value even further.↵
↵
The other possibility is that the new value $X$ creates two good pairs, one on each side, looking like this:↵
↵
$$X\quad\ldots\quad X\quad\ldots\quad X.$$↵
↵
Here, the middle $X$ is the element we changed, and both pairs are good.↵
↵
If we decrease the middle element to $1$, the two pairs can be replaced by one larger good pair:↵
↵
$$X\quad\ldots\quad 1\quad\ldots\quad X.$$↵
↵
Thus, decreasing the maximum element to $1$ is sufficient.↵
↵
lets also note if that max element occurs more than once this is useless.↵
↵
This proves that checking our three operations is enough to find an optimal solution.↵
↵
Finally, checking whether an array is beautiful can be implemented in $O(n\log n)$ using several approaches, or in $O(n)$ using a monotonic stack.↵
↵
Since we perform only a constant number of checks, the overall time complexity is **$O(n)$** per test case.↵
↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
bool beautiful(vector<int>& a) {↵
int n = a.size();↵
vector<int> st, diff(n + 1);↵
↵
for (int i = 0; i < n; i++) {↵
while (!st.empty() && a[st.back()] < a[i])↵
st.pop_back();↵
↵
if (!st.empty() && a[st.back()] == a[i]) {↵
diff[st.back()]++;↵
diff[i + 1]--;↵
}↵
st.push_back(i);↵
}↵
↵
int cur = 0;↵
for (int i = 0; i < n; i++) {↵
cur += diff[i];↵
if (cur == 0) return false;↵
}↵
return true;↵
}↵
↵
void solve() {↵
int n;↵
cin >> n;↵
vector<int> a(n);↵
for (int &x : a) cin >> x;↵
↵
if (beautiful(a)) {↵
cout << 0 << '\n';↵
return;↵
}↵
↵
int pos = max_element(a.begin(), a.end()) - a.begin();↵
int mx = a[pos];↵
↵
auto check = [&](int i, int x) {↵
int old = a[i];↵
a[i] = x;↵
bool ok = beautiful(a);↵
a[i] = old;↵
if (ok) {↵
cout << 1 << '\n';↵
cout << i + 1 << ' ' << x << '\n';↵
}↵
return ok;↵
};↵
↵
if (check(0, mx)) return;↵
if (check(n - 1, mx)) return;↵
if (check(pos, 1)) return;↵
↵
cout << 2 << '\n';↵
cout << 1 << ' ' << mx << '\n';↵
cout << n << ' ' << mx << '\n';↵
}↵
↵
int main() {↵
ios::sync_with_stdio(false);↵
cin.tie(nullptr);↵
↵
int t;↵
cin >> t;↵
while (t--) solve();↵
}↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 6, option1] Good Problem ↵
- [likes: 6, option2] Okay Problem ↵
- [likes: 6, option3] Bad Problem ↵
- [likes: 6, option4] Didn't Solve↵
</spoiler>↵
↵
[problem:2271G]↵
↵
<spoiler summary = "Solution">↵
↵
First, let's determine when it is **impossible** to fill the grid.↵
↵
Suppose there are two $1\times 1$ pieces in the same row, with only $1\times 2$ pieces between them.↵
↵
For example:↵
↵
$$x\ |\ x\ x\ |\ x\ x\ |\ x\ x\ |\ x$$↵
↵
Since every $1\times 1$ piece must contain $1$, the first cell is forced to be $1$. This forces the next $1\times 2$ piece to be $[2,1]$, and the same applies to every following piece.↵
↵
We end up with:↵
↵
$$1\ |\ 2\ 1\ |\ 2\ 1\ |\ 2\ 1\ |\ 1$$↵
↵
Clearly, this is invalid because the last two adjacent cells both contain $1$.↵
↵
The same argument applies vertically to two $1\times 1$ pieces with only $2\times 1$ pieces between them.↵
↵
We claim that **these are the only cases where a valid filling is impossible**.↵
↵
Let's prove this by constructing a valid filling whenever neither case occurs.↵
↵
**Step 1: Fill all thin pieces.**↵
↵
First, put $1$ in every $1\times 1$ piece.↵
↵
Now, let's fill all $1\times y$ and $y\times 1$ pieces.↵
↵
We will only explain the construction for horizontal pieces, since vertical pieces can be handled in exactly the same way.↵
↵
Consider any two $1\times 1$ pieces in the same row.↵
↵
Since our impossible condition does not occur, there must be at least one $1\times y$ piece between them with $y\ge 3$.↵
↵
Choose the first such piece from the left and call it the **turning point**.↵
↵
We fill the pieces between the two $1\times 1$ pieces as follows:↵
↵
- For every piece before the turning point, write its numbers in decreasing order.↵
- For every piece after the turning point, write its numbers in increasing order.↵
- For the turning point itself, use the order $[y,1,2,3,\ldots,y-1]$.↵
↵
Notice that this guarantees that adjacent cells contain different numbers, including across the boundaries of the pieces.↵
↵
For portions of the row before the first $1\times 1$ piece, after the last one, or rows containing no $1\times 1$ pieces, we can simply choose a suitable increasing or decreasing order.↵
↵
We apply the same construction vertically to fill all remaining $y\times 1$ pieces.↵
↵
↵
↵
**Step 2: Fill the rows containing $1$.**↵
↵
Notice that by choosing our coloring patterns consistently in the previous step, the already-colored cells in each partially filled row contain the same value.↵
↵
Now, consider every partially filled row whose already-colored cells contain $1$.↵
↵
We can fill the gaps between these $1$ s using exactly the same turning-point construction from Step 1.↵
↵
This fills all such rows while ensuring that horizontally adjacent cells contain different numbers.↵
↵
↵
↵
**Step 3: Fill the remaining cells.**↵
↵
Now, let's consider the remaining unfilled rows.↵
↵
The important observation is that **these rows can be handled independently**, since the vertical constraints have already been taken care of by our construction.↵
↵
Furthermore, every gap we need to fill has the same value, say $x$, on both its left and right boundaries.↵
↵
Therefore, we only need to arrange the remaining numbers inside each piece so that adjacent values are different and neither boundary creates a conflict.↵
↵
We can use the same idea as before: arrange the values in increasing or decreasing order, and use a turning point whenever necessary.↵
↵
Since the required values are available and the vertical constraints are already satisfied, we can fill all remaining gaps.↵
↵
Thus, we have constructed a valid filling whenever neither of the two impossible configurations occurs, completing the proof.↵
↵
↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 7, option1] Good Problem ↵
- [likes: 7, option2] Okay Problem ↵
- [likes: 7, option3] Bad Problem ↵
- [likes: 7, option4] Didn't Solve↵
</spoiler>↵
↵
↵
[problem:2271H2]↵
↵
<spoiler summary = "Solution">↵
Editorial will be Added when Axial isn't tired :(↵
↵
if you have any non slop solutions please comment them below↵
</spoiler>↵
↵
<spoiler summary = "Code">↵
~~~~↵
↵
~~~~↵
</spoiler>↵
↵
<spoiler summary="Rate The Problem!">↵
- [likes: 8, option1] Good Problem ↵
- [likes: 8, option2] Okay Problem ↵
- [likes: 8, option3] Bad Problem ↵
- [likes: 8, option4] Didn't Solve↵
</spoiler>↵
↵
