How many participants can possibly have solved all three problems?

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.

#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();}
}

Consider the cases $$$a\geq b$$$ and $$$a \lt b$$$ separately.

If Alice ever takes stones, she should take all of them.

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 \lt 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 \lt 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.

#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();}
}

If a prefix contains both $$$0$$$ and $$$1$$$, what are its bitwise AND and bitwise OR?

A sorted binary string is determined by one split point.

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.

#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();}
}

Look at how the height and position of each section change after an operation.

A section moving one position to the right gains $$$1$$$ height, while a section moving one position to the left loses $$$1$$$ height.

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.

#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();}
}

Use DP. Let $$$dp_i$$$ be the minimum number of operations needed to turn one $$$i$$$ into elements which are all at most $$$k$$$.

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 \gt 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 \lt 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.

Can you solve the problem for all $$$f(1),f(2),\ldots,f(n)$$$?

This was actually the original version of the problem!

#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();}
}

Work backwards from one copy of the value you want to create.

Process the values from large to small, and let $$$q$$$ be the number of copies of the current value that you need.

If you need $$$q$$$ copies of $$$x$$$ but only have $$$c \lt q$$$, the missing $$$q-c$$$ copies of $$$x$$$ each force another copy of every smaller value.

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 \gt 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 \lt 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.

Can you get a much smaller upper bound for the binary search?

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

#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();}
}

Process the tree from the leaves upward.

A node can always be brought back to its original value after changing it.

For every node $$$i$$$, its reachable values have the form $$$(a_i+g_ix)\bmod b_i$$$ for some integer $$$x$$$. Find $$$g_i$$$.

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.

#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();}
}

We only need to keep one occurrence of every value $$$1,2,\ldots,n$$$. What can we do with every other occurrence?

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?

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

Fix the position of the global minimum. The prefix minima and suffix minima can be optimized separately.

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 \lt \min(t_1,\ldots,t_{i-1})$$$. Similarly, we can push it to the back exactly when $$$t_i \lt \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 \gt 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 \gt 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)$$$.

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)$$$.

#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();}
}

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)$$$.

#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();}
}