[problem:2149A]↵
↵
<spoiler summary="Solution">↵
Let $Z$ be the number of zeros in the array, and $N$ be the number of elements equal to $-1$.↵
↵
Every zero must be incremented to $1$, which costs $Z$ operations.↵
If $N$ is odd, then after removing zeros the product is negative. To fix this, we must convert one $-1 \to 1$, which costs $2$ operations.↵
↵
Thus the answer is:↵
$\text{ans} = Z + 2 \cdot (N \bmod 2)$.↵
↵
The time complexity is $O(n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 340625093]↵
</spoiler>↵
↵
↵
↵
[problem:2149B]↵
↵
<spoiler summary="Solution">↵
Let $a$ be the sorted array. For each pair we want to minimize the maximum difference. If we pair far apart elements, the difference will be large. The optimal strategy is to pair consecutive elements after sorting: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$.↵
↵
The difference of each pair is $a_{2i}-a_{2i-1}$, and the maximum of these values is the minimized maximum difference.↵
↵
Thus the answer is:↵
$\text{ans} = \max \{a_{2}-a_{1},\ a_{4}-a_{3},\ \dots,\ a_{n}-a_{n-1}\}$.↵
↵
The time complexity is $O(n \log n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:340625068]↵
</spoiler>↵
↵
↵
↵
[problem:2149C]↵
↵
<spoiler summary="Solution">↵
Let $Z$ be the number of integers in $[0, k-1]$ that are missing from the array, and let $C$ be the number of elements equal to $k$.↵
↵
To make $\text{MEX}(a) = k$, every number from $0$ to $k-1$ must appear, which costs $Z$ operations. Also, $k$ must not appear in the array, so we need $C$ operations to remove them. While removing copies of $k$, we can directly replace them with missing numbers, so the total number of operations is the maximum of these two values.↵
↵
Thus, the answer is:↵
$\text{ans} = \max(Z, C)$.↵
↵
The time complexity is $O(n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 34061056625028]↵
</spoiler>↵
↵
↵
[problem:2149D]↵
↵
<spoiler summary="Solution">↵
Let the target be to make all occurrences of one letter contiguous. Do it for both letters and take the minimum.↵
↵
Fix a letter $c\in{a,b}$ and let its positions be $p_0<p_1<\dots<p_{m-1}$. If we place these $m$ copies into a consecutive block starting at some index $L$, the number of adjacent swaps needed is $$↵
\sum_{i=0}^{m-1} \bigl|\, p_i - (L+i) \,\bigr|↵
\;=\;↵
\sum_{i=0}^{m-1} \bigl|\, (p_i - i) - L \,\bigr|↵
$$↵
Set $b_i=p_i-i$. The function $\sum_i |b_i-L|$ is minimized when $L$ is a median of ${b_i}$. Hence the optimal cost to cluster all $c$'s is $$↵
\operatorname{cost}(c) = \sum_{i=0}^{m-1} \bigl|\, b_i - \operatorname{med}(b) \,\bigr|,↵
\quad \text{where } b_i = p_i - i.↵
$$↵
The answer is $\min(\operatorname{cost}(a),\operatorname{cost}(b))$.↵
↵
This counts the minimal number of adjacent swaps because each swap reduces the sum of pairwise inversions between the two types by exactly $1$, and aligning to a consecutive block achieves the minimum. The algorithm computes positions, builds $b_i$, takes the median, and sums absolute deviations — all in linear time after positions are known.↵
↵
The time complexity is $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 3406250054980]↵
</spoiler>↵
↵
[problem:2149E]↵
↵
<spoiler summary="Solution">↵
Let’s fix the left border $i$. Let the valid right borders be $j \ge i$ such that↵
↵
- $[a_i,\ldots,a_j]$ has exactly $k$ distinct numbers;↵
- $l \le j-i+1 \le r$.↵
↵
Maintain two sliding windows:↵
↵
- $x$ — the maximum right index such that $[i..x]$ has exactly $k$ distinct;↵
- $y$ — the maximum right index such that $[i..y-1]$ has at most $k$ distinct.↵
↵
All valid right endpoints lie in $[x, x+1, \dots, y-1]$. Intersect with the length constraint↵
$[\,i+l-1,\, i+l, \dots, i+r-1\,]$. The number of good subarrays starting at $i$ is↵
$$\max \!\Bigl(0, \; \min(y-1,\, i+r-1)\;-\;\max(x,\, i+l-1)\;+\;1\Bigr)$$↵
↵
Add this to the answer, then move $i$ forward and update the frequency counters.↵
↵
Each element is processed once by the two pointers; with coordinate compression the total time is $O(n\log n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:340611339]↵
</spoiler>↵
↵
[problem:2149F]↵
↵
<spoiler summary="Solution">↵
Suppose we use exactly $m$ rests. Then the $d$ moves split into $s=m+1$ consecutive runs of moves between rests. If a run has length $t$, its health cost is the triangular number↵
$$T(t) = \dfrac{t(t+1)}{2}$$↵
because the run's $j$-th move costs $j$ health.↵
↵
For fixed $m$, to minimize the total cost we make the run lengths as equal as possible. Let↵
$$a = \left\lfloor \dfrac{d}{s} \right\rfloor, \quad r = d \bmod s.$$↵
↵
Then $r$ runs have length $a+1$ and $s-r$ runs have length $a$, so the total health spent is↵
$$C(m) = r \cdot \dfrac{(a+1)(a+2)}{2} \;+\; (s-r) \cdot \dfrac{a(a+1)}{2}.$$↵
↵
Rests add health: each rest gives $+1$, so over the whole trip the available health is $h+m$. Because health must stay $\ge 1$ after every move, we need↵
$$C(m) \leq h + m - 1.$$↵
This gives a monotone predicate in $m$, so we binary search the smallest $m\in[0,d]$ satisfying it. The answer is the total number of turns:↵
$$\boxed{d + m}$$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 34061177224948]↵
</spoiler>↵
↵
↵
[problem:2149G]↵
↵
<spoiler summary="Solution (randomized method)">↵
We use a randomized method: for a query $[l,r]$, let $L=r-l+1$ and $T=\left\lfloor \tfrac{L}{3}\right\rfloor$. We repeatedly sample random positions from the segment, and each sampled value is treated as a candidate. If a value truly occurs more than $T$ times, then it occupies more than one third of the segment, so the probability of hitting it in one random draw is $$p > \frac{1}{3}.$$↵
After $k$ independent draws, the probability of missing it is at most $(\tfrac{2}{3})^k$, which becomes negligible for $k=50$.↵
↵
To check a candidate, we precompute for each distinct value $x$ the sorted list of its positions $f_x$. The exact frequency of $x$ in $[l,r]$ is $$\#_x(l,r) \;=\; \operatorname{upper\_bound}(f_x,r) - \operatorname{lower\_bound}(f_x,l).$$↵
↵
If $$\#_x(l,r)\;>\;T,$$ then $x$ is included in the answer.↵
↵
Since there are at most two true heavy elements, and each is found with high probability through random sampling, we collect all verified candidates, remove duplicates, and output them in sorted order.↵
↵
Each query runs in $O(k \log n)$, where $k$ is a small constant (e.g. $50$). This is efficient given the constraints, and the error probability is astronomically small.↵
</spoiler>↵
↵
<spoiler summary="Code (randomized method)">↵
[submission: 34060945724923]↵
</spoiler>↵
↵
↵
↵
↵
↵
<spoiler summary="Solution (Misra--Gries algorithm)">↵
It is a known fact that in any segment there can be at most two elements occurring more than one third of the time($> \left\lfloor \dfrac{L}{3} \right\rfloor$). Therefore, for each query, it is enough to maintain at most two candidates. ↵
↵
We build a segment tree where each node stores up to two candidate values with counters. The merge operation is exactly the [Misra-Gries](https://en.m.wikipedia.org/wiki/Misra%E2%80%93Gries_heavy_hitters_algorithm) algorithm with capacity $2$: ↵
if a value matches, we increase its count; ↵
if a slot is free, we put it there; ↵
otherwise we cancel counts.As a result, querying $[l,r]$ yields up to two potential answers. To check them, we precompute for each distinct value the sorted list of its positions. The exact frequency of a value $x$ in $[l,r]$ is↵
$$\#_x(l,r) \;=\; \operatorname{upper\_bound}(f_x,r) - \operatorname{lower\_bound}(f_x,l)$$↵
where $f_x$ is the list of indices where $x$ occurs. If this number is greater than $T$, then $x$ is included in the answer. After verifying at most two candidates, we output them in sorted order, or $-1$ if none qualify. ↵
</spoiler>↵
↵
↵
<spoiler summary="Code (Misra-Gries)">↵
[submission: 34060822024888]↵
</spoiler>↵
↵
↵
↵
<spoiler summary="Solution">↵
Let $Z$ be the number of zeros in the array, and $N$ be the number of elements equal to $-1$.↵
↵
Every zero must be incremented to $1$, which costs $Z$ operations.↵
If $N$ is odd, then after removing zeros the product is negative. To fix this, we must convert one $-1 \to 1$, which costs $2$ operations.↵
↵
Thus the answer is:↵
$\text{ans} = Z + 2 \cdot (N \bmod 2)$.↵
↵
The time complexity is $O(n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 340625093]↵
</spoiler>↵
↵
↵
↵
[problem:2149B]↵
↵
<spoiler summary="Solution">↵
Let $a$ be the sorted array. For each pair we want to minimize the maximum difference. If we pair far apart elements, the difference will be large. The optimal strategy is to pair consecutive elements after sorting: $(a_1,a_2), (a_3,a_4), \dots, (a_{n-1},a_n)$.↵
↵
The difference of each pair is $a_{2i}-a_{2i-1}$, and the maximum of these values is the minimized maximum difference.↵
↵
Thus the answer is:↵
$\text{ans} = \max \{a_{2}-a_{1},\ a_{4}-a_{3},\ \dots,\ a_{n}-a_{n-1}\}$.↵
↵
The time complexity is $O(n \log n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:340625068]↵
</spoiler>↵
↵
↵
↵
[problem:2149C]↵
↵
<spoiler summary="Solution">↵
Let $Z$ be the number of integers in $[0, k-1]$ that are missing from the array, and let $C$ be the number of elements equal to $k$.↵
↵
To make $\text{MEX}(a) = k$, every number from $0$ to $k-1$ must appear, which costs $Z$ operations. Also, $k$ must not appear in the array, so we need $C$ operations to remove them. While removing copies of $k$, we can directly replace them with missing numbers, so the total number of operations is the maximum of these two values.↵
↵
Thus, the answer is:↵
$\text{ans} = \max(Z, C)$.↵
↵
The time complexity is $O(n)$ per test case.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 3406
</spoiler>↵
↵
↵
[problem:2149D]↵
↵
<spoiler summary="Solution">↵
Let the target be to make all occurrences of one letter contiguous. Do it for both letters and take the minimum.↵
↵
Fix a letter $c\in{a,b}$ and let its positions be $p_0<p_1<\dots<p_{m-1}$. If we place these $m$ copies into a consecutive block starting at some index $L$, the number of adjacent swaps needed is $$↵
\sum_{i=0}^{m-1} \bigl|\, p_i - (L+i) \,\bigr|↵
\;=\;↵
\sum_{i=0}^{m-1} \bigl|\, (p_i - i) - L \,\bigr|↵
$$↵
Set $b_i=p_i-i$. The function $\sum_i |b_i-L|$ is minimized when $L$ is a median of ${b_i}$. Hence the optimal cost to cluster all $c$'s is $$↵
\operatorname{cost}(c) = \sum_{i=0}^{m-1} \bigl|\, b_i - \operatorname{med}(b) \,\bigr|,↵
\quad \text{where } b_i = p_i - i.↵
$$↵
The answer is $\min(\operatorname{cost}(a),\operatorname{cost}(b))$.↵
↵
This counts the minimal number of adjacent swaps because each swap reduces the sum of pairwise inversions between the two types by exactly $1$, and aligning to a consecutive block achieves the minimum. The algorithm computes positions, builds $b_i$, takes the median, and sums absolute deviations — all in linear time after positions are known.↵
↵
The time complexity is $O(n)$.↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 34062
</spoiler>↵
↵
[problem:2149E]↵
↵
<spoiler summary="Solution">↵
Let’s fix the left border $i$. Let the valid right borders be $j \ge i$ such that↵
↵
- $[a_i,\ldots,a_j]$ has exactly $k$ distinct numbers;↵
- $l \le j-i+1 \le r$.↵
↵
Maintain two sliding windows:↵
↵
- $x$ — the maximum right index such that $[i..x]$ has exactly $k$ distinct;↵
- $y$ — the maximum right index such that $[i..y-1]$ has at most $k$ distinct.↵
↵
All valid right endpoints lie in $[x, x+1, \dots, y-1]$. Intersect with the length constraint↵
$[\,i+l-1,\, i+l, \dots, i+r-1\,]$. The number of good subarrays starting at $i$ is↵
$$\max \!\Bigl(0, \; \min(y-1,\, i+r-1)\;-\;\max(x,\, i+l-1)\;+\;1\Bigr)$$↵
↵
Add this to the answer, then move $i$ forward and update the frequency counters.↵
↵
Each element is processed once by the two pointers; with coordinate compression the total time is $O(n\log n)$.↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission:340611339]↵
</spoiler>↵
↵
[problem:2149F]↵
↵
<spoiler summary="Solution">↵
Suppose we use exactly $m$ rests. Then the $d$ moves split into $s=m+1$ consecutive runs of moves between rests. If a run has length $t$, its health cost is the triangular number↵
$$T(t) = \dfrac{t(t+1)}{2}$$↵
because the run's $j$-th move costs $j$ health.↵
↵
For fixed $m$, to minimize the total cost we make the run lengths as equal as possible. Let↵
$$a = \left\lfloor \dfrac{d}{s} \right\rfloor, \quad r = d \bmod s.$$↵
↵
Then $r$ runs have length $a+1$ and $s-r$ runs have length $a$, so the total health spent is↵
$$C(m) = r \cdot \dfrac{(a+1)(a+2)}{2} \;+\; (s-r) \cdot \dfrac{a(a+1)}{2}.$$↵
↵
Rests add health: each rest gives $+1$, so over the whole trip the available health is $h+m$. Because health must stay $\ge 1$ after every move, we need↵
$$C(m) \leq h + m - 1.$$↵
This gives a monotone predicate in $m$, so we binary search the smallest $m\in[0,d]$ satisfying it. The answer is the total number of turns:↵
$$\boxed{d + m}$$↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Code">↵
[submission: 3406
</spoiler>↵
↵
↵
[problem:2149G]↵
↵
<spoiler summary="Solution (randomized method)">↵
We use a randomized method: for a query $[l,r]$, let $L=r-l+1$ and $T=\left\lfloor \tfrac{L}{3}\right\rfloor$. We repeatedly sample random positions from the segment, and each sampled value is treated as a candidate. If a value truly occurs more than $T$ times, then it occupies more than one third of the segment, so the probability of hitting it in one random draw is $$p > \frac{1}{3}.$$↵
After $k$ independent draws, the probability of missing it is at most $(\tfrac{2}{3})^k$, which becomes negligible for $k=50$.↵
↵
To check a candidate, we precompute for each distinct value $x$ the sorted list of its positions $f_x$. The exact frequency of $x$ in $[l,r]$ is $$\#_x(l,r) \;=\; \operatorname{upper\_bound}(f_x,r) - \operatorname{lower\_bound}(f_x,l).$$↵
↵
If $$\#_x(l,r)\;>\;T,$$ then $x$ is included in the answer.↵
↵
Since there are at most two true heavy elements, and each is found with high probability through random sampling, we collect all verified candidates, remove duplicates, and output them in sorted order.↵
↵
Each query runs in $O(k \log n)$, where $k$ is a small constant (e.g. $50$). This is efficient given the constraints, and the error probability is astronomically small.↵
</spoiler>↵
↵
<spoiler summary="Code (randomized method)">↵
[submission: 3406
</spoiler>↵
↵
↵
↵
↵
↵
<spoiler summary="Solution (Misra--Gries algorithm)">↵
It is a known fact that in any segment there can be at most two elements occurring more than one third of the time($> \left\lfloor \dfrac{L}{3} \right\rfloor$). Therefore, for each query, it is enough to maintain at most two candidates. ↵
↵
We build a segment tree where each node stores up to two candidate values with counters. The merge operation is exactly the [Misra-Gries](https://en.m.wikipedia.org/wiki/Misra%E2%80%93Gries_heavy_hitters_algorithm) algorithm with capacity $2$: ↵
if a value matches, we increase its count; ↵
if a slot is free, we put it there; ↵
otherwise we cancel counts.As a result, querying $[l,r]$ yields up to two potential answers. To check them, we precompute for each distinct value the sorted list of its positions. The exact frequency of a value $x$ in $[l,r]$ is↵
$$\#_x(l,r) \;=\; \operatorname{upper\_bound}(f_x,r) - \operatorname{lower\_bound}(f_x,l)$$↵
where $f_x$ is the list of indices where $x$ occurs. If this number is greater than $T$, then $x$ is included in the answer. After verifying at most two candidates, we output them in sorted order, or $-1$ if none qualify. ↵
</spoiler>↵
↵
↵
<spoiler summary="Code (Misra-Gries)">↵
[submission: 3406
</spoiler>↵
↵
↵
