Thanks for participating in [contest:2266]!↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent contest↵
- [likes:1,option2] Good contest↵
- [likes:1,option3] Average contest↵
- [likes:1,option4] Bad contest↵
- [likes:1,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty"> ↵
↵
- [likes:2,option1] Trivial contest↵
- [likes:2,option2] Easy contest↵
- [likes:2,option3] Average contest↵
- [likes:2,option4] Hard contest↵
- [likes:2,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266A]↵
↵
<spoiler summary="Hint">↵
↵
How many participants can possibly have solved all three problems?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily.↵
↵
Thus, the answer is $n-\min(a_1,a_2,a_3)$.↵
↵
The complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
int a, b, c; cin >> a >> b >> c;↵
int m = min({a,b,c});↵
cout << N-m << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:3,option1] Trivial problem↵
- [likes:3,option2] Easy problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Hard problem↵
- [likes:3,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:4,option1] Excellent problem↵
- [likes:4,option2] Good problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Bad problem↵
- [likes:4,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266B]↵
↵
<spoiler summary="Hint 1">↵
↵
Consider the cases $a\geq b$ and $a<b$ separately.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
If Alice ever takes stones, she should take all of them.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If $a\geq b$, Alice takes all $c$ stones immediately. There is nothing left for Bob to use to reduce her lead, so the score is $a+c-b$.↵
↵
Now suppose $a<b$. Alice can take $0$ stones, and Bob will also take $0$ because he is already ahead and taking more stones would only increase the score. This gives $b-a$. Otherwise, Alice should take all $c$ stones at once. Taking only part of them gives a difference between the two cases of taking none and taking all, so it cannot be better than both. Taking all gives $|a+c-b|$.↵
↵
If $a+c<b$, this is smaller than $b-a$. Otherwise, it equals $a+c-b$. Therefore, the answer is $\max(|a-b|,a+c-b)$.↵
↵
The complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int a, b, c; cin >> a >> b >> c;↵
cout << max(abs(a-b),(a+c-b)) << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:5,option1] Trivial problem↵
- [likes:5,option2] Easy problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Hard problem↵
- [likes:5,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:6,option1] Excellent problem↵
- [likes:6,option2] Good problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Bad problem↵
- [likes:6,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266C]↵
↵
<spoiler summary="Hint 1">↵
↵
If a prefix contains both $0$ and $1$, what are its bitwise AND and bitwise OR?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A sorted binary string is determined by one split point.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If a prefix contains both $0$ and $1$, its AND is $0$ and its OR is $1$, so its last character can be changed to either value.↵
↵
If $s_1=1$, the first character can never change, so the final string must be all ones. Every zero can be changed using OR, giving the number of zeros as the answer.↵
↵
Now suppose $s_1=0$. Fix the point after which the ones start. For a split after $i$, we need to change every one in $[1,i]$ and every zero in $[i+1,n]$. We can first change the required zeros on the right using OR, then change the required ones on the left using AND. A split inside the initial block of zeros is never better than moving it to the end of that block.↵
↵
So, scan every split while maintaining the number of ones on the left and zeros on the right, and take the minimum.↵
↵
The complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
string s; cin >> s;↵
int z = 0;↵
int o = 0;↵
for (int i = 0; i < N; i++) {z+=(s[i]=='0');}↵
if (s[0]=='1') {cout << z << endl; return;}↵
int aa = 1e9;↵
for (int i = 0; i < N; i++) {↵
o+=(s[i]=='1');↵
z-=(s[i]=='0');↵
aa=min(aa,o+z);↵
}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:7,option1] Trivial problem↵
- [likes:7,option2] Easy problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Hard problem↵
- [likes:7,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:8,option1] Excellent problem↵
- [likes:8,option2] Good problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Bad problem↵
- [likes:8,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266D]↵
↵
<spoiler summary="Hint 1">↵
↵
Look at how the height and position of each section change after an operation.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A section moving one position to the right gains $1$ height, while a section moving one position to the left loses $1$ height.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
During an operation, every section passed over moves one position to the right and gains $1$ height. The section being moved goes $j-i$ positions to the left and loses exactly $j-i$ height. Thus, for every section, $\text{height}-\text{position}$ never changes. The section initially at position $i$ therefore always keeps the value $a_i-i$.↵
↵
We can also reorder the sections however we want by building the desired order from left to right and repeatedly moving the required section into the next position.↵
↵
Suppose $k$ consecutive positions starting at $p$ are flat at height $h$. Their invariant values are $h-p,h-p-1,\ldots,h-p-k+1$, which are $k$ distinct consecutive integers. The reverse is also true: if $k$ sections have consecutive values $a_i-i$, placing them in decreasing order makes their heights equal.↵
↵
Therefore, the answer is the longest consecutive run among the distinct values $a_i-i$. Put them in a set and scan in increasing order.↵
↵
The complexity is $O(n\log n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
set<int> s;↵
for (int i = 1; i <= N; i++) {↵
int a; cin >> a;↵
s.insert(a-i);↵
}↵
int aa = 0;↵
int tt = 0;↵
int c = -1e9;↵
for (auto x : s) {↵
if (x!=c+1) {aa=max(aa,tt); tt=0;}↵
tt++;↵
c=x;↵
}↵
aa=max(aa,tt);↵
cout << aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:9,option1] Trivial problem↵
- [likes:9,option2] Easy problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Hard problem↵
- [likes:9,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:10,option1] Excellent problem↵
- [likes:10,option2] Good problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Bad problem↵
- [likes:10,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266E]↵
↵
<spoiler summary="Hint">↵
↵
Use DP. Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$. Clearly, $dp_i=0$ for $i\leq k$.↵
↵
For $i>k$, suppose we choose a prime divisor $p$ of $i$. One operation gives us $p$ copies of $i/p$, and these copies can then be handled independently. Thus, $dp_i=\min_{p\mid i,\ p\text{ prime}}(1+p\cdot dp_{i/p})$.↵
↵
Since $i/p<i$, compute the DP in increasing order. We can precompute the distinct prime divisors of every number with a sieve. Finally, the original elements are independent, so the answer is $\sum dp_{a_i}$.↵
↵
The complexity is $O(n\log\log n)$ per test case after preprocessing.↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
↵
Can you solve the problem for all $f(1),f(2),\ldots,f(n)$?↵
↵
This was actually the original version of the problem!↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
vector<long long> pf[200001];↵
long long dp[200001];↵
bool cmp[200001];↵
↵
void pre() {↵
for (long long i = 2; i <= 200000; i++) {↵
if (!cmp[i]) {↵
cmp[i]=true;↵
for (long long j = 2*i; j <= 200000; j+=i) {↵
pf[j].push_back(i);↵
cmp[j]=true;↵
}↵
pf[i].push_back(i);↵
}↵
}↵
}↵
↵
void solve() {↵
long long N, K; cin >> N >> K;↵
long long aa = 0;↵
vector<long long> dp(N+1,1e18);↵
for (long long i = 1; i <= N; i++) {↵
if (i<=K) {dp[i]=0;}↵
for (auto x : pf[i]) {dp[i]=min(dp[i],dp[i/x]*x+1);}↵
}↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
aa+=dp[a];↵
}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
pre();↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:11,option1] Trivial problem↵
- [likes:11,option2] Easy problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Hard problem↵
- [likes:11,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:12,option1] Excellent problem↵
- [likes:12,option2] Good problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Bad problem↵
- [likes:12,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266F]↵
↵
<spoiler summary="Hint 1">↵
↵
Work backwards from one copy of the value you want to create.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Process the values from large to small, and let $q$ be the number of copies of the current value that you need.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
If you need $q$ copies of $x$ but only have $c<q$, the missing $q-c$ copies of $x$ each force another copy of every smaller value.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
We check whether a value $M$ can appear, then binary search the largest valid $M$. The largest initial value is already present, so only larger values need to be checked.↵
↵
Work backwards from one copy of $M$. At first we need one copy of every value below it, so set $q=1$ and process the values downwards. Suppose we currently need $q$ copies of $x>0$, and there are $c$ copies of $x$ in the initial multiset. If $c\geq q$, we use $q$ of them and have $c-q$ extras. If $c<q$, the missing $q-c$ copies of $x$ each require another copy of every smaller value. Thus, $q$ becomes $q+(q-c)=2q-c$.↵
↵
So the transition is $q\leftarrow q+\max(0,q-c)$. Extra positive elements cannot save us at another positive level, but they can all be turned into zeros by taking them alone. We count these extras, and when we reach $0$, the check succeeds exactly when the initial zeros plus all extras are at least $q$.↵
↵
Missing values are easy to skip. If there are $d$ missing values in a row, then $q$ doubles $d$ times, so multiply it by $2^d$ at once. We can also cap $q$ once it becomes larger than the total number of elements to avoid overflow.↵
↵
If $M$ is possible, then every smaller value is also possible, since all of them have to exist while building $M$. Therefore, binary search works. After sorting the pairs, one check is $O(n)$.↵
↵
The complexity is $O(n\log n+n\log C)$ per test case, where $C$ is the binary search range.↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
↵
Can you get a much smaller upper bound for the binary search?↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus Answer">↵
↵
Let $mx=\max x_i$.↵
↵
You only need to search up to about $mx+50$. Once we go much further than $mx$, there are many consecutive missing values, and every missing value doubles $q$, so the required number of elements grows too quickly.↵
↵
Thus, we can binary search only on $[mx,mx+50]$, giving $O(n\log 50)$ checks after sorting.↵
↵
The exact proof and bound are left to the reader :)↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
bool check(long long mid, vector<pair<long long, long long>> &A) {↵
long long n = 1;↵
long long ex = 0;↵
long long p = mid;↵
for (long long i = 0; i < A.size(); i++) {↵
if (p-A[i].first+(63-__builtin_clzll(n))>60) {return false;}↵
n<<=(p-A[i].first-1);↵
if (!A[i].first) {ex+=A[i].second; break;}↵
if (A[i].second>n) {ex+=A[i].second-n;}↵
else {n=(n<<1)-A[i].second;}↵
p=A[i].first;↵
}↵
return (ex>=n);↵
}↵
↵
void solve() {↵
long long N; cin >> N;↵
vector<pair<long long, long long>> A;↵
long long lo = 0;↵
long long hi = 1000000100;↵
for (long long i = 0; i < N; i++) {↵
long long a, b; cin >> a >> b;↵
A.push_back({a,b});↵
lo=max(lo,a);↵
}↵
sort(A.rbegin(),A.rend());↵
if (A.back().first) {A.push_back({0,0});}↵
while (lo<hi) {↵
long long mid = (lo+hi+1)/2;↵
if (check(mid,A)) {lo=mid;}↵
else {hi=mid-1;}↵
}↵
cout << lo << endl;↵
}↵
↵
int main() {↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:13,option1] Trivial problem↵
- [likes:13,option2] Easy problem↵
- [likes:13,option3] Average problem↵
- [likes:13,option4] Hard problem↵
- [likes:13,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:14,option1] Excellent problem↵
- [likes:14,option2] Good problem↵
- [likes:14,option3] Average problem↵
- [likes:14,option4] Bad problem↵
- [likes:14,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266G]↵
↵
<spoiler summary="Hint 1">↵
↵
Process the tree from the leaves upward.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A node can always be brought back to its original value after changing it.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
For every node $i$, its reachable values have the form $(a_i+g_ix)\bmod b_i$ for some integer $x$. Find $g_i$.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
For every node $u$, let $g_u$ be such that its reachable values are exactly $(a_u+g_ux)\bmod b_u$. We compute $g_u$ from the leaves upward.↵
↵
Suppose $v$ is a child of $u$. If $g_v=b_v$, then $v$ is fixed at $a_v$. Otherwise, its value can change from $a_v$ by multiples of $g_v$. Let $S_u$ be the sum of the initial values of all direct children of $u$. We can add $S_u$ to $u$ by leaving all children at their initial values, and every non-fixed child $v$ lets us vary this amount by multiples of $g_v$. Therefore, $g_u=\gcd(b_u,S_u,g_v\text{ for all non-fixed children }v)$.↵
↵
For a leaf, this gives $g_u=b_u$, as expected. Once we know $g_u$, the largest reachable value is $a_u+\left\lfloor\frac{b_u-1-a_u}{g_u}\right\rfloor g_u$.↵
↵
These maxima can all be achieved together. We can first set a node to its maximum, then continue working strictly inside its children's subtrees without changing that node. So after computing all $g_u$ bottom-up, we simply sum the maximum reachable value of every node.↵
↵
The complexity is $O(n\log 10^9)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void dfs(long long node, long long par, vector<long long> &A, vector<long long> &B, vector<long long> &g, vector<vector<long long>> &adj) {↵
long long gc = 0;↵
long long tt = 0;↵
for (auto x : adj[node]) {↵
if (x != par) {↵
dfs(x,node,A,B,g,adj);↵
if (g[x]!=B[x]) {gc=gcd(gc,g[x]);}↵
tt+=A[x];↵
}↵
}↵
gc=gcd(gc,tt);↵
gc=gcd(gc,B[node]);↵
g[node]=gc;↵
}↵
↵
void solve() {↵
long long N; cin >> N;↵
vector<long long> A; A.push_back(-1);↵
vector<long long> B; B.push_back(-1);↵
vector<vector<long long>> adj(N+1);↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
A.push_back(a);↵
}↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
B.push_back(a);↵
}↵
for (long long i = 0; i < N-1; i++) {↵
long long a, b; cin >> a >> b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
vector<long long> g(N+1); //init to 0 for identity gcd↵
dfs(1,0,A,B,g,adj);↵
long long aa = 0;↵
for (long long i = 1; i <= N; i++) {aa+=((B[i]-A[i]-1)/g[i])*g[i]+A[i];}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:15,option1] Trivial problem↵
- [likes:15,option2] Easy problem↵
- [likes:15,option3] Average problem↵
- [likes:15,option4] Hard problem↵
- [likes:15,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:16,option1] Excellent problem↵
- [likes:16,option2] Good problem↵
- [likes:16,option3] Average problem↵
- [likes:16,option4] Bad problem↵
- [likes:16,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266H]↵
↵
<spoiler summary="Hint 1">↵
↵
We only need to keep one occurrence of every value $1,2,\ldots,n$. What can we do with every other occurrence?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Let $t_i$ be the arrival position of the occurrence of $i$ which stays in the final deque. When can $i$ be inserted without a malfunction?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
An element can be inserted normally exactly when $t_i$ is a prefix minimum or a suffix minimum of $t_1,t_2,\ldots,t_n$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Fix the position of the global minimum. The prefix minima and suffix minima can be optimized separately.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If some value from $1$ to $n$ never appears, the answer is $-1$. Otherwise, choose one occurrence of each value to keep. Every unused occurrence can simply be pushed to an end and immediately removed from that same end.↵
↵
Let $t_i$ be the position of the chosen occurrence of $i$. We can push $i$ to the front normally exactly when every chosen value which arrived earlier is larger than $i$, or $t_i<\min(t_1,\ldots,t_{i-1})$. Similarly, we can push it to the back exactly when $t_i<\min(t_{i+1},\ldots,t_n)$. Thus, a value avoids a malfunction exactly when $t_i$ is a prefix minimum or a suffix minimum. The global minimum is counted in both, so if there are $L$ prefix minima and $R$ suffix minima, we keep $L+R-1$ values for free.↵
↵
Now optimize the prefix minima. Process the values $1,2,\ldots,n$. Let $dp[p]$ be the maximum number of prefix minima so far when the smallest chosen arrival position is $p$. For an occurrence at position $t$, making it the new minimum gives $new[t]=1+\max_{p>t}dp[p]$. All of these transitions must be calculated before adding the states for the current value.↵
↵
An old state with minimum $p$ can stay unchanged only if the current value has some occurrence after $p$. If $last_i$ is its last occurrence, every state with $p>last_i$ must therefore be deleted. For value $1$, every occurrence simply starts with value $1$.↵
↵
After all values are processed, let $L[p]$ be the best number of prefix minima whose global minimum is at position $p$. Run the same DP with the values in reverse order to get $R[p]$ for suffix minima. For a fixed $p$, the two sides can be combined independently, sharing only the global minimum itself. Therefore, the maximum number of values which avoid a malfunction is $\max_p(L[p]+R[p]-1)$, and the answer is $n-\max_p(L[p]+R[p]-1)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation 1: Lazy Segment Tree">↵
↵
Store the DP in a segment tree. For an occurrence $t$, the transition needs the maximum on $(t,m]$. After calculating all transitions for the current value, clear the suffix after $last_i$ and insert the new states.↵
↵
A lazy segment tree supports the suffix clear and range maximum queries in $O(\log m)$, so the total complexity is $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Lazy Segment Tree)">↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation 2: Amortized Set Deletion">↵
↵
We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$.↵
↵
Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Amortized Set Deletion)">```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct lst { //cur range add range max, change accordingly, no need for l,r in range add range mx↵
vector<int> seg;↵
vector<bool> tg;↵
vector<int> lz;↵
int sz = 1;↵
int id = 0; //change sent↵
int acc(int x, int y) {return max(x,y);} //other more complex lst can do range set and range add↵
void pull(int n) {seg[n]=acc(seg[n<<1],seg[(n<<1)|1]);}↵
void apply(int n, int l, int r, int v) {seg[n]=v; tg[n]=true; lz[n]=v;} //if something else, change id, acc, apply, and how lz accumulates/replaces in push↵
void push(int n, int l, int r) {if (!tg[n]) {return;} tg[n]=false; apply(n<<1,l,(l+r)/2,lz[n]); apply((n<<1)|1,(l+r)/2+1,r,lz[n]); lz[n]=0;}↵
lst(vector<int> A) { //inp 0 index↵
while (sz<A.size()) {sz<<=1;}↵
seg.assign(2*sz,id);↵
tg.assign(2*sz,false); //in case 0 is a range set↵
lz.assign(2*sz,0);↵
for (int i = 0; i < A.size(); i++) {seg[sz+i]=A[i];}↵
for (int i = sz-1; i >= 1; i--) {pull(i);}↵
}↵
int qq(int n, int l, int r, int sl, int sr) {↵
if (sl>r||sr<l) {return id;}↵
if (l<=sl&&sr<=r) {return seg[n];}↵
push(n,sl,sr);↵
return acc(qq(n<<1,l,r,sl,(sl+sr)/2),qq((n<<1)|1,l,r,(sl+sr)/2+1,sr));↵
}↵
void uu(int n, int l, int r, int sl, int sr, int v) {↵
if (sl>r||sr<l) {return;}↵
if (l<=sl&&sr<=r) {apply(n,sl,sr,v); return;}↵
push(n,sl,sr);↵
uu(n<<1,l,r,sl,(sl+sr)/2,v);↵
uu((n<<1)|1,l,r,(sl+sr)/2+1,sr,v);↵
pull(n);↵
}↵
int q(int l, int r) {return qq(1,l,r,1,sz);}↵
void u(int l, int r, int v) {uu(1,l,r,1,sz,v);}↵
};↵
↵
↵
void solve() {↵
int N, M; cin >> N >> M;↵
vector<int> A;↵
for (int i = 0; i < N; i++) {↵
A.push_back(i+1);↵
}↵
vector<vector<int>> tt(N+1);↵
vector<int> ndp1(M+1);↵
for (int i = 1; i <= M; i++) {↵
int a; cin >> a;↵
tt[a].push_back(i);↵
}↵
for (int i = 1; i <= N; i++) {↵
if (tt[i].empty()) {cout << -1 << endl; return;}↵
}↵
vector<int> ii(M+1); // one sentinel at end so no RE↵
lst dp1(ii);↵
bool f = true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp1.q(t+1,M+1);↵
ndp1[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp1.u(t,t,ndp1[t]);↵
}↵
dp1.u(tt[x].back()+1,M+1,0);↵
if (f) {f=false;}↵
}↵
vector<int> ndp2(M+1);↵
reverse(A.begin(),A.end());↵
lst dp2(ii);↵
f=true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp2.q(t+1,M+1);↵
ndp2[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp2.u(t,t,ndp2[t]);↵
}↵
dp2.u(tt[x].back()+1,M+1,0);↵
if (f) {f=false;}↵
}↵
int aa = 0;↵
for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}↵
cout << N-aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation 2: Amortized Set Deletion">↵
↵
We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$.↵
↵
Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Amortized Set Deletion)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct tri { //inp zero index vector, transformed to 1 index↵
vector<int> s;↵
int sz = 1;↵
tri(vector<int> &A) {↵
while (sz<A.size()) {sz<<=1;}↵
s.assign(2*sz,0);↵
for (int i = 0; i < A.size(); i++) {s[i+sz] = A[i];}↵
for (int i = sz-1; i >= 1; i--) {s[i]=max(s[i<<1],s[(i<<1)|1]);}↵
}↵
void u(int i, int x) {↵
int p = sz+i-1; s[p] = x;↵
for (p>>=1; p; p>>=1) {s[p]=max(s[p<<1],s[(p<<1)|1]);}↵
}↵
int aa(int n, int l, int r, int sl, int sr) {↵
if (l<=sl&&sr<=r) {return s[n];}↵
else if (sr<l||sl>r) {return 0;}↵
else {return max(aa(n<<1,l,r,sl,(sl+sr)>>1),aa((n<<1)|1,l,r,((sl+sr)>>1)+1,sr));}↵
}↵
int q(int l, int r) {return aa(1,l,r,1,sz);}↵
};↵
↵
void solve() {↵
int N, M; cin >> N >> M;↵
vector<int> A;↵
for (int i = 0; i < N; i++) {↵
A.push_back(i+1);↵
}↵
vector<vector<int>> tt(N+1);↵
vector<int> ndp1(M+1);↵
for (int i = 1; i <= M; i++) {↵
int a; cin >> a;↵
tt[a].push_back(i);↵
}↵
for (int i = 1; i <= N; i++) {↵
if (tt[i].empty()) {cout << -1 << endl; return;}↵
}↵
vector<int> ii(M+1); // one sentinel at end so no RE↵
tri dp1(ii);↵
set<int> act;↵
bool f = true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp1.q(t+1,M+1);↵
ndp1[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp1.u(t,ndp1[t]);↵
act.insert(t);↵
}↵
while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp1.u((*act.rbegin()),0); act.erase(*act.rbegin());}↵
if (f) {f=false;}↵
}↵
vector<int> ndp2(M+1);↵
act.clear();↵
reverse(A.begin(),A.end());↵
tri dp2(ii);↵
f=true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp2.q(t+1,M+1);↵
ndp2[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp2.u(t,ndp2[t]);↵
act.insert(t);↵
}↵
while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp2.u((*act.rbegin()),0); act.erase(*act.rbegin());}↵
if (f) {f=false;}↵
}↵
int aa = 0;↵
for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}↵
cout << N-aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:17,option1] Trivial problem↵
- [likes:17,option2] Easy problem↵
- [likes:17,option3] Average problem↵
- [likes:17,option4] Hard problem↵
- [likes:17,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:18,option1] Excellent problem↵
- [likes:18,option2] Good problem↵
- [likes:18,option3] Average problem↵
- [likes:18,option4] Bad problem↵
- [likes:18,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
<spoiler summary="Rate the contest!">↵
↵
<spoiler summary="Quality">↵
↵
- [likes:1,option1] Excellent contest↵
- [likes:1,option2] Good contest↵
- [likes:1,option3] Average contest↵
- [likes:1,option4] Bad contest↵
- [likes:1,option5] Horrible contest↵
↵
</spoiler>↵
↵
<spoiler summary="Difficulty"> ↵
↵
- [likes:2,option1] Trivial contest↵
- [likes:2,option2] Easy contest↵
- [likes:2,option3] Average contest↵
- [likes:2,option4] Hard contest↵
- [likes:2,option5] Impossible contest↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266A]↵
↵
<spoiler summary="Hint">↵
↵
How many participants can possibly have solved all three problems?↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily.↵
↵
Thus, the answer is $n-\min(a_1,a_2,a_3)$.↵
↵
The complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
int a, b, c; cin >> a >> b >> c;↵
int m = min({a,b,c});↵
cout << N-m << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:3,option1] Trivial problem↵
- [likes:3,option2] Easy problem↵
- [likes:3,option3] Average problem↵
- [likes:3,option4] Hard problem↵
- [likes:3,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:4,option1] Excellent problem↵
- [likes:4,option2] Good problem↵
- [likes:4,option3] Average problem↵
- [likes:4,option4] Bad problem↵
- [likes:4,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266B]↵
↵
<spoiler summary="Hint 1">↵
↵
Consider the cases $a\geq b$ and $a<b$ separately.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
If Alice ever takes stones, she should take all of them.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If $a\geq b$, Alice takes all $c$ stones immediately. There is nothing left for Bob to use to reduce her lead, so the score is $a+c-b$.↵
↵
Now suppose $a<b$. Alice can take $0$ stones, and Bob will also take $0$ because he is already ahead and taking more stones would only increase the score. This gives $b-a$. Otherwise, Alice should take all $c$ stones at once. Taking only part of them gives a difference between the two cases of taking none and taking all, so it cannot be better than both. Taking all gives $|a+c-b|$.↵
↵
If $a+c<b$, this is smaller than $b-a$. Otherwise, it equals $a+c-b$. Therefore, the answer is $\max(|a-b|,a+c-b)$.↵
↵
The complexity is $O(1)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int a, b, c; cin >> a >> b >> c;↵
cout << max(abs(a-b),(a+c-b)) << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:5,option1] Trivial problem↵
- [likes:5,option2] Easy problem↵
- [likes:5,option3] Average problem↵
- [likes:5,option4] Hard problem↵
- [likes:5,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:6,option1] Excellent problem↵
- [likes:6,option2] Good problem↵
- [likes:6,option3] Average problem↵
- [likes:6,option4] Bad problem↵
- [likes:6,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266C]↵
↵
<spoiler summary="Hint 1">↵
↵
If a prefix contains both $0$ and $1$, what are its bitwise AND and bitwise OR?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A sorted binary string is determined by one split point.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If a prefix contains both $0$ and $1$, its AND is $0$ and its OR is $1$, so its last character can be changed to either value.↵
↵
If $s_1=1$, the first character can never change, so the final string must be all ones. Every zero can be changed using OR, giving the number of zeros as the answer.↵
↵
Now suppose $s_1=0$. Fix the point after which the ones start. For a split after $i$, we need to change every one in $[1,i]$ and every zero in $[i+1,n]$. We can first change the required zeros on the right using OR, then change the required ones on the left using AND. A split inside the initial block of zeros is never better than moving it to the end of that block.↵
↵
So, scan every split while maintaining the number of ones on the left and zeros on the right, and take the minimum.↵
↵
The complexity is $O(n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
string s; cin >> s;↵
int z = 0;↵
int o = 0;↵
for (int i = 0; i < N; i++) {z+=(s[i]=='0');}↵
if (s[0]=='1') {cout << z << endl; return;}↵
int aa = 1e9;↵
for (int i = 0; i < N; i++) {↵
o+=(s[i]=='1');↵
z-=(s[i]=='0');↵
aa=min(aa,o+z);↵
}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:7,option1] Trivial problem↵
- [likes:7,option2] Easy problem↵
- [likes:7,option3] Average problem↵
- [likes:7,option4] Hard problem↵
- [likes:7,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:8,option1] Excellent problem↵
- [likes:8,option2] Good problem↵
- [likes:8,option3] Average problem↵
- [likes:8,option4] Bad problem↵
- [likes:8,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266D]↵
↵
<spoiler summary="Hint 1">↵
↵
Look at how the height and position of each section change after an operation.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A section moving one position to the right gains $1$ height, while a section moving one position to the left loses $1$ height.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
During an operation, every section passed over moves one position to the right and gains $1$ height. The section being moved goes $j-i$ positions to the left and loses exactly $j-i$ height. Thus, for every section, $\text{height}-\text{position}$ never changes. The section initially at position $i$ therefore always keeps the value $a_i-i$.↵
↵
We can also reorder the sections however we want by building the desired order from left to right and repeatedly moving the required section into the next position.↵
↵
Suppose $k$ consecutive positions starting at $p$ are flat at height $h$. Their invariant values are $h-p,h-p-1,\ldots,h-p-k+1$, which are $k$ distinct consecutive integers. The reverse is also true: if $k$ sections have consecutive values $a_i-i$, placing them in decreasing order makes their heights equal.↵
↵
Therefore, the answer is the longest consecutive run among the distinct values $a_i-i$. Put them in a set and scan in increasing order.↵
↵
The complexity is $O(n\log n)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void solve() {↵
int N; cin >> N;↵
set<int> s;↵
for (int i = 1; i <= N; i++) {↵
int a; cin >> a;↵
s.insert(a-i);↵
}↵
int aa = 0;↵
int tt = 0;↵
int c = -1e9;↵
for (auto x : s) {↵
if (x!=c+1) {aa=max(aa,tt); tt=0;}↵
tt++;↵
c=x;↵
}↵
aa=max(aa,tt);↵
cout << aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:9,option1] Trivial problem↵
- [likes:9,option2] Easy problem↵
- [likes:9,option3] Average problem↵
- [likes:9,option4] Hard problem↵
- [likes:9,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:10,option1] Excellent problem↵
- [likes:10,option2] Good problem↵
- [likes:10,option3] Average problem↵
- [likes:10,option4] Bad problem↵
- [likes:10,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266E]↵
↵
<spoiler summary="Hint">↵
↵
Use DP. Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
Let $dp_i$ be the minimum number of operations needed to turn one $i$ into elements which are all at most $k$. Clearly, $dp_i=0$ for $i\leq k$.↵
↵
For $i>k$, suppose we choose a prime divisor $p$ of $i$. One operation gives us $p$ copies of $i/p$, and these copies can then be handled independently. Thus, $dp_i=\min_{p\mid i,\ p\text{ prime}}(1+p\cdot dp_{i/p})$.↵
↵
Since $i/p<i$, compute the DP in increasing order. We can precompute the distinct prime divisors of every number with a sieve. Finally, the original elements are independent, so the answer is $\sum dp_{a_i}$.↵
↵
The complexity is $O(n\log\log n)$ per test case after preprocessing.↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
↵
Can you solve the problem for all $f(1),f(2),\ldots,f(n)$?↵
↵
This was actually the original version of the problem!↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
vector<long long> pf[200001];↵
long long dp[200001];↵
bool cmp[200001];↵
↵
void pre() {↵
for (long long i = 2; i <= 200000; i++) {↵
if (!cmp[i]) {↵
cmp[i]=true;↵
for (long long j = 2*i; j <= 200000; j+=i) {↵
pf[j].push_back(i);↵
cmp[j]=true;↵
}↵
pf[i].push_back(i);↵
}↵
}↵
}↵
↵
void solve() {↵
long long N, K; cin >> N >> K;↵
long long aa = 0;↵
vector<long long> dp(N+1,1e18);↵
for (long long i = 1; i <= N; i++) {↵
if (i<=K) {dp[i]=0;}↵
for (auto x : pf[i]) {dp[i]=min(dp[i],dp[i/x]*x+1);}↵
}↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
aa+=dp[a];↵
}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
pre();↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:11,option1] Trivial problem↵
- [likes:11,option2] Easy problem↵
- [likes:11,option3] Average problem↵
- [likes:11,option4] Hard problem↵
- [likes:11,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:12,option1] Excellent problem↵
- [likes:12,option2] Good problem↵
- [likes:12,option3] Average problem↵
- [likes:12,option4] Bad problem↵
- [likes:12,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266F]↵
↵
<spoiler summary="Hint 1">↵
↵
Work backwards from one copy of the value you want to create.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Process the values from large to small, and let $q$ be the number of copies of the current value that you need.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
If you need $q$ copies of $x$ but only have $c<q$, the missing $q-c$ copies of $x$ each force another copy of every smaller value.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
We check whether a value $M$ can appear, then binary search the largest valid $M$. The largest initial value is already present, so only larger values need to be checked.↵
↵
Work backwards from one copy of $M$. At first we need one copy of every value below it, so set $q=1$ and process the values downwards. Suppose we currently need $q$ copies of $x>0$, and there are $c$ copies of $x$ in the initial multiset. If $c\geq q$, we use $q$ of them and have $c-q$ extras. If $c<q$, the missing $q-c$ copies of $x$ each require another copy of every smaller value. Thus, $q$ becomes $q+(q-c)=2q-c$.↵
↵
So the transition is $q\leftarrow q+\max(0,q-c)$. Extra positive elements cannot save us at another positive level, but they can all be turned into zeros by taking them alone. We count these extras, and when we reach $0$, the check succeeds exactly when the initial zeros plus all extras are at least $q$.↵
↵
Missing values are easy to skip. If there are $d$ missing values in a row, then $q$ doubles $d$ times, so multiply it by $2^d$ at once. We can also cap $q$ once it becomes larger than the total number of elements to avoid overflow.↵
↵
If $M$ is possible, then every smaller value is also possible, since all of them have to exist while building $M$. Therefore, binary search works. After sorting the pairs, one check is $O(n)$.↵
↵
The complexity is $O(n\log n+n\log C)$ per test case, where $C$ is the binary search range.↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus">↵
↵
Can you get a much smaller upper bound for the binary search?↵
↵
</spoiler>↵
↵
<spoiler summary="Bonus Answer">↵
↵
Let $mx=\max x_i$.↵
↵
You only need to search up to about $mx+50$. Once we go much further than $mx$, there are many consecutive missing values, and every missing value doubles $q$, so the required number of elements grows too quickly.↵
↵
Thus, we can binary search only on $[mx,mx+50]$, giving $O(n\log 50)$ checks after sorting.↵
↵
The exact proof and bound are left to the reader :)↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
bool check(long long mid, vector<pair<long long, long long>> &A) {↵
long long n = 1;↵
long long ex = 0;↵
long long p = mid;↵
for (long long i = 0; i < A.size(); i++) {↵
if (p-A[i].first+(63-__builtin_clzll(n))>60) {return false;}↵
n<<=(p-A[i].first-1);↵
if (!A[i].first) {ex+=A[i].second; break;}↵
if (A[i].second>n) {ex+=A[i].second-n;}↵
else {n=(n<<1)-A[i].second;}↵
p=A[i].first;↵
}↵
return (ex>=n);↵
}↵
↵
void solve() {↵
long long N; cin >> N;↵
vector<pair<long long, long long>> A;↵
long long lo = 0;↵
long long hi = 1000000100;↵
for (long long i = 0; i < N; i++) {↵
long long a, b; cin >> a >> b;↵
A.push_back({a,b});↵
lo=max(lo,a);↵
}↵
sort(A.rbegin(),A.rend());↵
if (A.back().first) {A.push_back({0,0});}↵
while (lo<hi) {↵
long long mid = (lo+hi+1)/2;↵
if (check(mid,A)) {lo=mid;}↵
else {hi=mid-1;}↵
}↵
cout << lo << endl;↵
}↵
↵
int main() {↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:13,option1] Trivial problem↵
- [likes:13,option2] Easy problem↵
- [likes:13,option3] Average problem↵
- [likes:13,option4] Hard problem↵
- [likes:13,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:14,option1] Excellent problem↵
- [likes:14,option2] Good problem↵
- [likes:14,option3] Average problem↵
- [likes:14,option4] Bad problem↵
- [likes:14,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266G]↵
↵
<spoiler summary="Hint 1">↵
↵
Process the tree from the leaves upward.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
A node can always be brought back to its original value after changing it.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
For every node $i$, its reachable values have the form $(a_i+g_ix)\bmod b_i$ for some integer $x$. Find $g_i$.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
For every node $u$, let $g_u$ be such that its reachable values are exactly $(a_u+g_ux)\bmod b_u$. We compute $g_u$ from the leaves upward.↵
↵
Suppose $v$ is a child of $u$. If $g_v=b_v$, then $v$ is fixed at $a_v$. Otherwise, its value can change from $a_v$ by multiples of $g_v$. Let $S_u$ be the sum of the initial values of all direct children of $u$. We can add $S_u$ to $u$ by leaving all children at their initial values, and every non-fixed child $v$ lets us vary this amount by multiples of $g_v$. Therefore, $g_u=\gcd(b_u,S_u,g_v\text{ for all non-fixed children }v)$.↵
↵
For a leaf, this gives $g_u=b_u$, as expected. Once we know $g_u$, the largest reachable value is $a_u+\left\lfloor\frac{b_u-1-a_u}{g_u}\right\rfloor g_u$.↵
↵
These maxima can all be achieved together. We can first set a node to its maximum, then continue working strictly inside its children's subtrees without changing that node. So after computing all $g_u$ bottom-up, we simply sum the maximum reachable value of every node.↵
↵
The complexity is $O(n\log 10^9)$ per test case.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (C++)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
void dfs(long long node, long long par, vector<long long> &A, vector<long long> &B, vector<long long> &g, vector<vector<long long>> &adj) {↵
long long gc = 0;↵
long long tt = 0;↵
for (auto x : adj[node]) {↵
if (x != par) {↵
dfs(x,node,A,B,g,adj);↵
if (g[x]!=B[x]) {gc=gcd(gc,g[x]);}↵
tt+=A[x];↵
}↵
}↵
gc=gcd(gc,tt);↵
gc=gcd(gc,B[node]);↵
g[node]=gc;↵
}↵
↵
void solve() {↵
long long N; cin >> N;↵
vector<long long> A; A.push_back(-1);↵
vector<long long> B; B.push_back(-1);↵
vector<vector<long long>> adj(N+1);↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
A.push_back(a);↵
}↵
for (long long i = 0; i < N; i++) {↵
long long a; cin >> a;↵
B.push_back(a);↵
}↵
for (long long i = 0; i < N-1; i++) {↵
long long a, b; cin >> a >> b;↵
adj[a].push_back(b);↵
adj[b].push_back(a);↵
}↵
vector<long long> g(N+1); //init to 0 for identity gcd↵
dfs(1,0,A,B,g,adj);↵
long long aa = 0;↵
for (long long i = 1; i <= N; i++) {aa+=((B[i]-A[i]-1)/g[i])*g[i]+A[i];}↵
cout << aa << endl;↵
}↵
↵
int main() {↵
long long T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:15,option1] Trivial problem↵
- [likes:15,option2] Easy problem↵
- [likes:15,option3] Average problem↵
- [likes:15,option4] Hard problem↵
- [likes:15,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:16,option1] Excellent problem↵
- [likes:16,option2] Good problem↵
- [likes:16,option3] Average problem↵
- [likes:16,option4] Bad problem↵
- [likes:16,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
[problem:2266H]↵
↵
<spoiler summary="Hint 1">↵
↵
We only need to keep one occurrence of every value $1,2,\ldots,n$. What can we do with every other occurrence?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 2">↵
↵
Let $t_i$ be the arrival position of the occurrence of $i$ which stays in the final deque. When can $i$ be inserted without a malfunction?↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 3">↵
↵
An element can be inserted normally exactly when $t_i$ is a prefix minimum or a suffix minimum of $t_1,t_2,\ldots,t_n$.↵
↵
</spoiler>↵
↵
<spoiler summary="Hint 4">↵
↵
Fix the position of the global minimum. The prefix minima and suffix minima can be optimized separately.↵
↵
</spoiler>↵
↵
<spoiler summary="Solution">↵
↵
If some value from $1$ to $n$ never appears, the answer is $-1$. Otherwise, choose one occurrence of each value to keep. Every unused occurrence can simply be pushed to an end and immediately removed from that same end.↵
↵
Let $t_i$ be the position of the chosen occurrence of $i$. We can push $i$ to the front normally exactly when every chosen value which arrived earlier is larger than $i$, or $t_i<\min(t_1,\ldots,t_{i-1})$. Similarly, we can push it to the back exactly when $t_i<\min(t_{i+1},\ldots,t_n)$. Thus, a value avoids a malfunction exactly when $t_i$ is a prefix minimum or a suffix minimum. The global minimum is counted in both, so if there are $L$ prefix minima and $R$ suffix minima, we keep $L+R-1$ values for free.↵
↵
Now optimize the prefix minima. Process the values $1,2,\ldots,n$. Let $dp[p]$ be the maximum number of prefix minima so far when the smallest chosen arrival position is $p$. For an occurrence at position $t$, making it the new minimum gives $new[t]=1+\max_{p>t}dp[p]$. All of these transitions must be calculated before adding the states for the current value.↵
↵
An old state with minimum $p$ can stay unchanged only if the current value has some occurrence after $p$. If $last_i$ is its last occurrence, every state with $p>last_i$ must therefore be deleted. For value $1$, every occurrence simply starts with value $1$.↵
↵
After all values are processed, let $L[p]$ be the best number of prefix minima whose global minimum is at position $p$. Run the same DP with the values in reverse order to get $R[p]$ for suffix minima. For a fixed $p$, the two sides can be combined independently, sharing only the global minimum itself. Therefore, the maximum number of values which avoid a malfunction is $\max_p(L[p]+R[p]-1)$, and the answer is $n-\max_p(L[p]+R[p]-1)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation 1: Lazy Segment Tree">↵
↵
Store the DP in a segment tree. For an occurrence $t$, the transition needs the maximum on $(t,m]$. After calculating all transitions for the current value, clear the suffix after $last_i$ and insert the new states.↵
↵
A lazy segment tree supports the suffix clear and range maximum queries in $O(\log m)$, so the total complexity is $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Lazy Segment Tree)">↵
↵
↵
<spoiler summary="Implementation 2: Amortized Set Deletion">↵
↵
We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$.↵
↵
Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Amortized Set Deletion)">
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct lst { //cur range add range max, change accordingly, no need for l,r in range add range mx↵
vector<int> seg;↵
vector<bool> tg;↵
vector<int> lz;↵
int sz = 1;↵
int id = 0; //change sent↵
int acc(int x, int y) {return max(x,y);} //other more complex lst can do range set and range add↵
void pull(int n) {seg[n]=acc(seg[n<<1],seg[(n<<1)|1]);}↵
void apply(int n, int l, int r, int v) {seg[n]=v; tg[n]=true; lz[n]=v;} //if something else, change id, acc, apply, and how lz accumulates/replaces in push↵
void push(int n, int l, int r) {if (!tg[n]) {return;} tg[n]=false; apply(n<<1,l,(l+r)/2,lz[n]); apply((n<<1)|1,(l+r)/2+1,r,lz[n]); lz[n]=0;}↵
lst(vector<int> A) { //inp 0 index↵
while (sz<A.size()) {sz<<=1;}↵
seg.assign(2*sz,id);↵
tg.assign(2*sz,false); //in case 0 is a range set↵
lz.assign(2*sz,0);↵
for (int i = 0; i < A.size(); i++) {seg[sz+i]=A[i];}↵
for (int i = sz-1; i >= 1; i--) {pull(i);}↵
}↵
int qq(int n, int l, int r, int sl, int sr) {↵
if (sl>r||sr<l) {return id;}↵
if (l<=sl&&sr<=r) {return seg[n];}↵
push(n,sl,sr);↵
return acc(qq(n<<1,l,r,sl,(sl+sr)/2),qq((n<<1)|1,l,r,(sl+sr)/2+1,sr));↵
}↵
void uu(int n, int l, int r, int sl, int sr, int v) {↵
if (sl>r||sr<l) {return;}↵
if (l<=sl&&sr<=r) {apply(n,sl,sr,v); return;}↵
push(n,sl,sr);↵
uu(n<<1,l,r,sl,(sl+sr)/2,v);↵
uu((n<<1)|1,l,r,(sl+sr)/2+1,sr,v);↵
pull(n);↵
}↵
int q(int l, int r) {return qq(1,l,r,1,sz);}↵
void u(int l, int r, int v) {uu(1,l,r,1,sz,v);}↵
};↵
↵
↵
void solve() {↵
int N, M; cin >> N >> M;↵
vector<int> A;↵
for (int i = 0; i < N; i++) {↵
A.push_back(i+1);↵
}↵
vector<vector<int>> tt(N+1);↵
vector<int> ndp1(M+1);↵
for (int i = 1; i <= M; i++) {↵
int a; cin >> a;↵
tt[a].push_back(i);↵
}↵
for (int i = 1; i <= N; i++) {↵
if (tt[i].empty()) {cout << -1 << endl; return;}↵
}↵
vector<int> ii(M+1); // one sentinel at end so no RE↵
lst dp1(ii);↵
bool f = true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp1.q(t+1,M+1);↵
ndp1[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp1.u(t,t,ndp1[t]);↵
}↵
dp1.u(tt[x].back()+1,M+1,0);↵
if (f) {f=false;}↵
}↵
vector<int> ndp2(M+1);↵
reverse(A.begin(),A.end());↵
lst dp2(ii);↵
f=true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp2.q(t+1,M+1);↵
ndp2[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp2.u(t,t,ndp2[t]);↵
}↵
dp2.u(tt[x].back()+1,M+1,0);↵
if (f) {f=false;}↵
}↵
int aa = 0;↵
for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}↵
cout << N-aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Implementation 2: Amortized Set Deletion">↵
↵
We can also use a normal segment tree together with a set of active positions. Whenever a state with position greater than $last_i$ becomes invalid, remove the largest such position from the set and set its segment tree value to $0$.↵
↵
Each position is inserted once and deleted at most once in one pass, so there are only $O(m)$ deletions in total. The total complexity is again $O(m\log m)$.↵
↵
</spoiler>↵
↵
<spoiler summary="Code (Amortized Set Deletion)">↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
struct tri { //inp zero index vector, transformed to 1 index↵
vector<int> s;↵
int sz = 1;↵
tri(vector<int> &A) {↵
while (sz<A.size()) {sz<<=1;}↵
s.assign(2*sz,0);↵
for (int i = 0; i < A.size(); i++) {s[i+sz] = A[i];}↵
for (int i = sz-1; i >= 1; i--) {s[i]=max(s[i<<1],s[(i<<1)|1]);}↵
}↵
void u(int i, int x) {↵
int p = sz+i-1; s[p] = x;↵
for (p>>=1; p; p>>=1) {s[p]=max(s[p<<1],s[(p<<1)|1]);}↵
}↵
int aa(int n, int l, int r, int sl, int sr) {↵
if (l<=sl&&sr<=r) {return s[n];}↵
else if (sr<l||sl>r) {return 0;}↵
else {return max(aa(n<<1,l,r,sl,(sl+sr)>>1),aa((n<<1)|1,l,r,((sl+sr)>>1)+1,sr));}↵
}↵
int q(int l, int r) {return aa(1,l,r,1,sz);}↵
};↵
↵
void solve() {↵
int N, M; cin >> N >> M;↵
vector<int> A;↵
for (int i = 0; i < N; i++) {↵
A.push_back(i+1);↵
}↵
vector<vector<int>> tt(N+1);↵
vector<int> ndp1(M+1);↵
for (int i = 1; i <= M; i++) {↵
int a; cin >> a;↵
tt[a].push_back(i);↵
}↵
for (int i = 1; i <= N; i++) {↵
if (tt[i].empty()) {cout << -1 << endl; return;}↵
}↵
vector<int> ii(M+1); // one sentinel at end so no RE↵
tri dp1(ii);↵
set<int> act;↵
bool f = true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp1.q(t+1,M+1);↵
ndp1[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp1.u(t,ndp1[t]);↵
act.insert(t);↵
}↵
while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp1.u((*act.rbegin()),0); act.erase(*act.rbegin());}↵
if (f) {f=false;}↵
}↵
vector<int> ndp2(M+1);↵
act.clear();↵
reverse(A.begin(),A.end());↵
tri dp2(ii);↵
f=true;↵
for (auto x : A) {↵
for (auto t : tt[x]) {↵
int rr = dp2.q(t+1,M+1);↵
ndp2[t]=(rr?rr+1:rr+(f));↵
}↵
for (auto t : tt[x]) {↵
dp2.u(t,ndp2[t]);↵
act.insert(t);↵
}↵
while (!act.empty()&&(*act.rbegin()>tt[x].back())) {dp2.u((*act.rbegin()),0); act.erase(*act.rbegin());}↵
if (f) {f=false;}↵
}↵
int aa = 0;↵
for (int i = 1; i <= M; i++) {aa=max(aa,dp1.q(i,i)+dp2.q(i,i)-1);}↵
cout << N-aa << endl;↵
}↵
↵
int main() {↵
int T; cin >> T;↵
while (T--) {solve();}↵
}↵
```↵
↵
</spoiler>↵
↵
<spoiler summary="Rate the problem!">↵
↵
<spoiler summary="Difficulty">↵
↵
- [likes:17,option1] Trivial problem↵
- [likes:17,option2] Easy problem↵
- [likes:17,option3] Average problem↵
- [likes:17,option4] Hard problem↵
- [likes:17,option5] Impossible problem↵
↵
</spoiler>↵
↵
<spoiler summary="Quality">↵
↵
- [likes:18,option1] Excellent problem↵
- [likes:18,option2] Good problem↵
- [likes:18,option3] Average problem↵
- [likes:18,option4] Bad problem↵
- [likes:18,option5] Horrible problem↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
