We choose $$$c$$$ between $$$a$$$ and $$$b$$$ $$$(a \leq c \leq b)$$$. The distance is $$$(c - a) + (b - c) = b - a$$$. Note that the distance does not depend on the the position $$$c$$$ at all.

for _ in range(int(input())):
    a,b = map(int,input().split())
    print(b-a)

Implement the statement. Iterate from $$$n-1$$$ to $$$0$$$ and use the .find() method in std::string in C++ (or .index() in python) to find the '#' character.

import sys
input=lambda:sys.stdin.readline().rstrip()

for i in range(int(input())):
    n=int(input())
    print(*reversed([input().index("#")+1 for i in range(n)]))

Consider the $$$x$$$ and $$$y$$$ directions separately and calculate the jumps we need in each direction. The number of jumps we need in the $$$x$$$ direction is $$$\lceil \frac{x}{k} \rceil$$$ and similarily $$$\lceil \frac{y}{k} \rceil$$$ in the $$$y$$$ direction. Now let's try to combine them to obtain the total number of jumps. Let's consider the following cases:

• $$$\lceil \frac{y}{k} \rceil \geq \lceil \frac{x}{k} \rceil$$$. In this case, there will need to be $$$\lceil \frac{y}{k} \rceil - \lceil \frac{x}{k} \rceil$$$ extra jumps in the $$$y$$$ direction. While Freya performs these extra jumps, she will choose $$$d = 0$$$ for the $$$x$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{y}{k} \rceil$$$ jumps.

• $$$\lceil \frac{x}{k} \rceil > \lceil \frac{y}{k} \rceil$$$. We can use the same reasoning as the previous case, but there's a catch. Since Freya is initially facing the $$$x$$$ direction, for the last jump, she does not need to jump in the $$$y$$$ direction. In total, there will need to be $$$2 \cdot \lceil \frac{x}{k} \rceil - 1$$$ jumps.

for _ in range(int(input())):
    x,y,k = map(int,input().split())
    print(max(2*((x+k-1)//k)-1,2*((y+k-1)//k)))

Initially, the obvious case one might first consider is an upright right triangle (specifically, the triangle with one of its sides parallel to the $$$y$$$-axis). This side can only be made with two points in the form $$$(x, 0)$$$ and $$$(x,1)$$$. We only need to search third point. Turns out, the third point can be any other unused vertex! If the third point has $$$y = 0$$$, then it will be an upright triangle, but if the third point has $$$y = 1$$$, it will simply be upside down.

One of the other case is in the form of $$$(x,0), (x+1,1), (x+2, 0)$$$. Let's see why this is a right triangle. Recall that in right triangle, the sum of the squares of two of the sides must equal to the square of the third side. The length between the first and the second point is $$$\sqrt 2$$$ because it is the diagonal of $$$1$$$ by $$$1$$$ unit block. Similarily, the second and third point also has length $$$\sqrt 2$$$. Obviously, the length between the first and third point is $$$2$$$. Since we have $$$\sqrt 2^2 + \sqrt 2^2 = 2^2$$$, this is certainly a right triangle. Of course, we can flip the $$$y$$$ values of each point and it will still be a valid right triangle, just upside down.

from collections import Counter
for _ in range(int(input())):
    n = int(input())
    nums = []
    for i in range(n):
        x,y = map(int,input().split())
        nums.append((x,y))
    ans = 0
    b = Counter(x[0] for x in nums)
    check = set(nums)
    for i in b:
        if b[i]==2: ans += n-2
    for p in check:
        if (p[0]-1,p[1]^1) in check and (p[0]+1,p[1]^1) in check: 
            ans +=1
    print(ans)
    

We can rewrite $$$x$$$ as $$$|a_1+\dots+a_i-(a_{i+1}+\dots+a_n)|$$$. Essentially, we want to minimize the absolute value difference between the sums of the prefix and the suffix. With absolute value problems. it's always good to consider the positive and negative cases separately. We will consider the prefix greater than the suffix separately with the less than case.

We can use binary search to search for the greatest $$$i$$$ such that $$$a_1 + \dots + a_i \leq a_{i+1} + \dots + a_n$$$. Note that here, the positive difference is minimized. If we move to $$$i+1$$$, then the negative difference is minimized (since the sum of prefix will now be less than the sum of suffix). The answer is the minimum absolute value of both cases.

To evaluate $$$a_1 + \dots + a_i$$$ fast, we can use the sum of arithmetic sequence formula.

from collections import Counter
def val(mid):
    val1 = (mid+k-1+k)*mid//2
    val2 = (k+n-1+k)*n//2 - val1
    return val1,val2
for _ in range(int(input())):
    n,k = map(int,input().split())
    lo = 1
    hi = n
    curr = 1
    while lo <= hi:
        mid = (lo+hi)//2
        a,b = val(mid)
        if b>a:
            curr = mid
            lo = mid+1
        else:
            hi = mid-1
    a1,b1 = val(curr)
    a2,b2 = val(curr+1)
    print(min(b1-a1,a2-b2))

import sys
input=sys.stdin.readline

from math import floor,sqrt

f=lambda x: (2*x*x + x*(4*k-2) + (n-n*n-2*k*n))//2

t=int(input())
for _ in range(t):
    n,k=map(int,input().split())
    D=4*k*k + 4*k*(n-1) + (2*n*n-2*n+1)
    i=(floor(sqrt(D))-(2*k-1))//2
    ans=min(abs(f(i)),abs(f(i+1)))
    print(ans) 

Let's duplicate the array $$$a$$$ and concatenate it with itself. Now, $$$a$$$ should have length $$$2n$$$ and $$$a_i = a_{i-n}$$$ for all $$$n < i \leq 2n$$$. Now, the $$$j$$$'th element of the $$$i$$$'th rotation is $$$a_{i+j-1}$$$.

It can be shown for any integer $$$x$$$, it belongs in rotation $$$\lfloor \frac{x-1}{n} \rfloor + 1$$$ and at position $$$(x-1) \mod n + 1$$$. Let $$$rl$$$ denote the rotation for $$$l$$$ and $$$rr$$$ denote the rotation for $$$r$$$. If $$$rr - rl > 1$$$, we are adding $$$rr-rl-1$$$ full arrays to our answer. The leftovers is just the suffix of rotation $$$rl$$$ starting at position $$$l$$$ and the prefix of rotation of $$$rr$$$ starting at position $$$r$$$. This can be done with prefix sums. You may need to handle $$$rl=rr$$$ separately.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
    int t;
    cin >> t;
    while (t--) {
        ll n, q;
        cin >> n >> q;
        vector<ll> a(n), ps(1);
        for (ll &r : a) {
            cin >> r;
            ps.push_back(ps.back() + r);
        }
        for (ll &r : a) {
            ps.push_back(ps.back() + r);
        }
        while (q--) {
            ll l, r;
            cin >> l >> r;
            l--; r--;
            ll i = l / n, j = r / n;
            l %= n; r %= n;
            cout << ps[n] * (j - i + 1) - (ps[i + l] - ps[i]) - (ps[j + n] - ps[j + r + 1]) << "\n";
        }
    }
}

We first make the sequence $$$b_i=a_i-i$$$ for all $$$i$$$. Now, if $$$b_i=b_j$$$, then $$$i$$$ and $$$j$$$ are in correct relative order.

Now, to solve the problem, we precompute the answer for every window of $$$k$$$, and then each query is a lookup. We use a sliding window, maintaining a multiset of frequencies of values of $$$b$$$ in the current window. To move from the window $$$[i\ldots i+k-1]$$$ to $$$i+1 \ldots i+k$$$, we lower the frequency of $$$b_i$$$ by $$$1$$$, and increase the frequency of $$$b_{i+k}$$$ by $$$1$$$.

#include "bits/stdc++.h"
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define endl '\n'
#define int long long
#define f first
#define mp make_pair
#define s second
using namespace std;

void solve(){
    int n, k, q; cin >> n >> k >> q;
    int a[n + 1]; for(int i = 1; i <= n; i++) cin >> a[i];
    map <int,int> m;
    multiset <int> tot;
    for(int i = 1; i <= n; i++) tot.insert(0);
    for(int i = 1; i < k; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
    }
    int ret[n + 1];
    for(int i = k; i <= n; i++){
        tot.erase(tot.find(m[a[i] - i]));
        m[a[i] - i]++;
        tot.insert(m[a[i] - i]);
        int p = i - k + 1;
        ret[p] = k - *tot.rbegin();
        tot.erase(tot.find(m[a[p] - p]));
        m[a[p] - p]--;
        tot.insert(m[a[p] - p]);
    }
    while(q--){
        int l, r ; cin >> l >> r;
        cout << ret[l] << endl;
    }
    tot.clear();
    m.clear();
}

signed main()
{
    fast;
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

First, read the solution to the easy version of the problem to compute the answer for every window of $$$k$$$. Let $$$c_i=f([a_i, ..., a_{i+k-1}])$$$. Now, the problem simplifies to finding

$$$\sum_{j=l}^{r-k+1} ( \min_{i=l}^{j} c_i)$$$

We will answer the queries offline in decreasing order of $$$l$$$. We maintain a lazy segment tree. We have a variable $$$x$$$ sweeping from $$$n-k$$$ to $$$0$$$. As the variable sweeps leftwards, in node $$$i$$$ of the segment tree, we keep track of $$$\min_{j=x}^{i}c_i$$$.

To decrease the value of $$$x$$$, we note that the range $$$[x-1, y]$$$ in the segment tree will be set to $$$c_{x-1}$$$, where $$$y$$$ is the largest value such that $$$c_y>c_{x-1}$$$ but $$$c_{y+1}\leq c_{x-1}$$$ (or $$$y=n-1$$$). To find the $$$y$$$ for each $$$x$$$, we may either walk/binary search in the segment tree, or use a monotonic stack.

#include "bits/stdc++.h"
#define int long long

template <typename T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
    os << "[ ";
    for (const auto& elem : vec) {
        os << elem << " ";
    }
    os << "]";
    return os;
}

using namespace std;

int getAns(int& k, multiset<int>& ms) { return k - (*ms.rbegin()); }
struct SegTree {
    int n;
    vector<int> tree, setLazy, begin, end;
    void prop(int i) {
        if (setLazy[i] != -100) {
            setLazy[2 * i + 1] = setLazy[2 * i] = setLazy[i];
            tree[2 * i] = tree[2 * i + 1] =
                setLazy[i] * (end[2 * i + 1] - begin[2 * i + 1] + 1);
            setLazy[i] = -100;
        }
    }
    SegTree(int nn) {
        n = 1;
        while (n < nn) n *= 2;
        tree.resize(2 * n);
        setLazy.resize(2 * n, -100);
        begin.resize(2 * n);
        end.resize(2 * n);
        for (int i = n; i < 2 * n; i++) {
            begin[i] = end[i] = i - n;
        }
        for (int i = n - 1; i > 0; i--) {
            begin[i] = begin[2 * i];
            end[i] = end[2 * i + 1];
        }
    }
    void rangeSet(int i, int amt, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) {
            tree[i] = amt * (hi - lo + 1);
            setLazy[i] = amt;
            return;
        }
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            rangeSet(2 * i, amt, lo, min(hi, end[2 * i]));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            rangeSet(2 * i + 1, amt, max(lo, begin[2 * i + 1]), hi);
        }
        tree[i] = tree[2 * i] + tree[2 * i + 1];
    }
    int query(int i, int lo, int hi) {
        if (i < n) prop(i);
        if (begin[i] == lo && end[i] == hi) return tree[i];
        int ans = 0;
        if (begin[2 * i] <= hi && end[2 * i] >= lo) {
            ans += query(2 * i, lo, min(end[2 * i], hi));
        }
        if (begin[2 * i + 1] <= hi && end[2 * i + 1] >= lo) {
            ans += query(2 * i + 1, max(lo, begin[2 * i + 1]), hi);
        }
        return ans;
    }
};
signed main() {
    int t;
    cin >> t;
    while (t--) {
        int n, k, q;
        cin >> n >> k >> q;
        vector<int> v(n);
        for (int i = 0; i < n; i++) {
            cin >> v[i];
            v[i] = v[i] - i;
        }
        vector<int> ans(n);  // ans[i] is answer from i to i+k-1
        map<int, int> mp;
        multiset<int> active;
        for (int i = 0; i < k; i++) {
            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
        }
        ans[0] = getAns(k, active);
        for (int i = k; i < n; i++) {
            // erase v[i-k]
            active.erase(active.find(mp[v[i - k]]));
            mp[v[i - k]]--;
            if (mp[v[i - k]] != 0) active.insert(mp[v[i - k]]);

            if (mp[v[i]] == 0) {
                mp[v[i]] = 1;
                active.insert(1);
            } else {
                active.erase(active.find(mp[v[i]]));
                mp[v[i]]++;
                active.insert(mp[v[i]]);
            }
            ans[i - k + 1] = getAns(k, active);
        }
        vector<array<int, 3>> queries(q);
        vector<int> an(q);
        for (int i = 0; i < q; i++) {
            queries[i][2] = i;
            cin >> queries[i][0] >> queries[i][1];
            queries[i][0]--;
            queries[i][1]--;
            queries[i][0] *= -1;
        }
        sort(begin(queries), end(queries));
        for (int i = 0; i < q; i++) queries[i][0] *= -1;
        SegTree st(n);
        st.rangeSet(1, ans[n - k], n - k, n - k);
        int cur = n - k;
        stack<pair<int, int>> s;
        s.push({ans[n - k], n - k});
        for (int i = 0; i < q; i++) {
            while (cur != queries[i][0]) {
                cur--;
                int here = cur;
                while (s.size() && s.top().first > ans[cur]) {
                    here = s.top().second;
                    s.pop();
                }
                s.push({ans[cur], here});
                st.rangeSet(1, ans[cur], cur, here);
            }
            an[queries[i][2]] =
                st.query(1, queries[i][0], queries[i][1] - k + 1);
        }
        for (auto x : an) cout << x << endl;
    }
}

Let $$$p_i$$$ be the smallest value $$$j>i$$$ such that $$$c_j<c_i.$$$ We can calculate these values using a monotonic stack and iterating through $$$c$$$ backwards. If such $$$j$$$ does not exist, then we let $$$p_i=n.$$$ Then $$$f(h,i)=c_i$$$ for all $$$i\le h-k+1<p_i.$$$ Further, $$$f(h,i)=c_{p_i}$$$ for $$$p_i\le h-k+1<p_{p_i},$$$ and so on.

Now, let $$$w(0,i)=i,$$$ and $$$w(h,i)=p_{w(h-1,i)}$$$ for $$$h>0.$$$ To calculate the answer for a query $$$(l,r),$$$ consider the largest value of $$$j$$$ such that $$$w(j,l)\le r.$$$ Then we can take the sum $$$c_{w(j,l)}\cdot(r-w(j,l)+1)+\sum_{i=1}^jc_{w(i-1,l)}\cdot(w(i,l)-w(i-1,l)).$$$

Now it remains to quickly calculate this sum. We can use binary lifting to solve this. Specifically, we create an $$$n\times20$$$ data table where $$$d[i][j]=\sum_{h=1}^{2^j}c_{w(h-1,i)}\cdot(w(h,i)-w(h-1,i)),$$$ if $$$w(2^j,i)$$$ exists, and $$$-1$$$ otherwise. We can precompute this table recursively, as $$$d[i][0]=c_i\cdot(w(1,i)-i)$$$ and $$$d[i][j]=d[i][j-1]+d[w(2^{j-1},i)][j-1].$$$

Then, to answer queries, we iterate $$$j$$$ from $$$19$$$ to $$$0,$$$ and if $$$w(2^j,l)\le r,$$$ we add $$$d[l][j]$$$ to our answer, and set $$$l=w(2^j,l).$$$ At the end, we add $$$c_l\cdot(r-l+1)$$$ to our answer.

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(3 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> l(n, -1);
    stack<pii> t;
    for (int i = k - 1; i < n; i++) {
        while (!t.empty()) {
            if (t.top().se <= v[i]) break;
            l[t.top().fi] = i;
            t.pop();
        }
        t.push({i, v[i]});
    }
    vector<vector<pii>> w(n, vector<pii>(20, {-1, -1}));
    for (int i = n - 1; i >= k - 1; i--) {
        w[i][0].se = l[i];
        if (l[i] < 0) {
            w[i][0].fi = (n - i) * v[i];
            continue;
        }
        w[i][0].fi = (l[i] - i) * v[i];
        for (int j = 1; j < 20; j++) {
            if (w[w[i][j - 1].se][j - 1].se < 0) break;
            w[i][j].se = w[w[i][j - 1].se][j - 1].se;
            w[i][j].fi = w[i][j - 1].fi + w[w[i][j - 1].se][j - 1].fi;
        }
    }
    while (q--) {
        int l, r, ans = 0;
        cin >> l >> r;
        l--;
        r--;
        l += k - 1;
        for (int j = 19; ~j; j--) {
            if (w[l][j].se < 0) continue;
            if (w[l][j].se > r) continue;
            ans += w[l][j].fi;
            l = w[l][j].se;
        }
        cout << ans + v[l] * (r - l + 1) << "\n";
    }
}
int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) solve();
}

I decided to write the Editorial for this problem in a step-by-step manner. Some of the steps are really short and meant to be used as hints but i decided to have a uniform naming for everything.

#include <bits/stdc++.h>
#define int long long
#define ll long long 
#define pii pair<int,int> 
#define piii pair<pii,pii>
#define fi first
#define se second
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
struct segtree {
    const static int INF = 1e18, INF2 = 0;
    int l, r;
    segtree* lc, * rc;
    int v = INF, v2=0, v3=0, v4=0;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r) return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    int op(int a, int b) {
        return min(a,b); 
    }
    int op2(int a, int b) {
        return a+b; 
    }
    void add(int qi, int qv, int h, int h4=0) {
        if (r < qi || l > qi) return;
        if (l == r) { if (v==INF) v=qv; v2+=qv, v3+=qv*h; v4+=qv*h4; return;}
        lc->add(qi, qv, h, h4); rc->add(qi, qv, h, h4);
        v = op(lc->v, rc->v);
        v2 = op2(lc->v2, rc->v2); 
        v3 = op2(lc->v3, rc->v3); 
        v4 = op2(lc->v4, rc->v4); 
    }
    int qrr(int ql, int qx) {
        if (v>=qx||r<ql) return 1e9; 
        if (l==r) return l; 
        int k=lc->qrr(ql,qx); 
        if (k<1e9) return k; 
        return rc->qrr(ql,qx); 
    }
    int q2(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v2;
        return op2(lc->q2(ql, qr), rc->q2(ql, qr));
    }
    int q3(int ql, int qr) {
        if (l > qr || r < ql) return INF2;
        if (ql <= l && r <= qr) return v3;
        return op2(lc->q3(ql, qr), rc->q3(ql, qr));
    }
    int q4(int ql, int qr) {
        if (l > qr || r < ql) return INF2; 
        if (ql <= l && r <= qr) return v4; 
        return op2(lc->q4(ql, qr), rc->q4(ql, qr)); 
    }
};
segtree mem[2000005];int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }
void solve() {
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> a(n);
    for (int &r : a) cin >> r;
    vector<int> c(2 * n), v(n);
    multiset<int> s;
    for (int i = 0; i < k; i++) c[a[i] - i + n - 1]++;
    for (int r : c) s.insert(r);
    v[k - 1] = k - *s.rbegin();
    for (int i = k; i < n; i++) {
        int x = a[i] - i + n - 1, y = a[i - k] - i + k + n - 1;
        c[x]++;
        s.erase(s.find(c[x] - 1));
        s.insert(c[x]);
        c[y]--;
        s.erase(s.find(c[y] + 1));
        s.insert(c[y]);
        v[i] = k - *s.rbegin();
    }
    vector<int> ans(q);
    vector<vector<pii>> w(n); 
    segtree co(0, n+2), lb(0, n+2), e(0,n+2),e2(0,n+2); 
    vector<int> rb(n); 
    stack<int> t; 
    for (int i = 0; i < q; i++) {
        int l,r; cin >> l >> r; 
        w[l+k-2].push_back({i,r-1}); 
    }
    for (int i = n-1; ~i; i--) {
        e.add(i,v[i],i,i*i); 
        int j=min(n,e.qrr(i,v[i])); 
        rb[i]=j; 
        e.add(j-1,-v[i],i,i*i);
        e2.add(j,v[i]*(j-i),i);
        while (!t.empty()) {
            int x=t.top(); 
            if (v[x]<v[i]) break;
            t.pop(); 
            co.add(rb[x],v[x]*(rb[x]-x)*(x-i),0); 
            lb.add(x,v[x]*(x-i),x);
            lb.add(rb[x]-1,-v[x]*(x-i),x); 
            e.add(x,-v[x],x,x*x);
            e.add(rb[x]-1,v[x],x,x*x);
            e2.add(rb[x],-v[x]*(rb[x]-x),x); 
        }
        t.push(i); 
        int l=i;
        for (auto [p,r]:w[i]) {
            int x=e.q2(l,r), y=e.q3(l,r), z=e.q4(l,r);
            int f=y*(r+1)-z, g=x*(r+1)-y; 
            int lx=lb.q2(l,r), ly=lb.q3(l,r); 
            ans[p]=co.q2(l,r+1)+lx*(r+1)-ly+e2.q3(l,r+1)-e2.q2(l,r+1)*(i-1)+f-g*(i-1);
        }
    }
    for (int r:ans) cout << r << "\n";
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t = 1; cin >> t;
	while (t--) solve();
}

If $$$n$$$ is a multiple of $$$4$$$, then you can have $$$\frac{n}{4}$$$ cows. Otherwise, you must have at least one chicken, so you can have $$$\frac{n-2}{4}$$$ cows and $$$1$$$ chicken.

#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--){
        int n;
        cin >> n;

        cout << (n + 2) / 4 << "\n";
    }
}

Let's define every $$$k$$$ by $$$k$$$ block of cells by its value in the top left corner, since all cells in the block must have the same value. So, we can just print out the value of the cell in every $$$k$$$'th row and every $$$k$$$'th column.

#include <bits/stdc++.h>
using namespace std; 

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--){
        int n, k;
        cin >> n >> k;

        char A[n][n];
        
        for (auto &row : A)
            for (char &c : row)
                cin >> c;
        
        for (int i = 0; i < n; i += k){
            for (int j = 0; j < n; j += k){
                cout << A[i][j];
            }
            cout << "\n";
        }
    }
}

For two strings to be the same after sorting, they must have the same occurrences of every possible lowercase letter. To answer the query for a range $$$[l, r]$$$, we must ensure that after the operations, $$$cnt_c = cnt2_c$$$ must where $$$cnt_c$$$ is the number of times character $$$c$$$ occurs in the range for $$$a$$$ and $$$cnt2_c$$$ is defined similarly for $$$b$$$. Both $$$cnt_c$$$ and $$$cnt2_c$$$ can be obtained by doing prefix sums for character $$$c$$$ specifically. Note that since there are only $$$26$$$ possible $$$c$$$, you can afford to create $$$26$$$ length $$$n$$$ prefix sum arrays.

In one operation, you can replace one occurrence of a character $$$c$$$ with another character $$$c2$$$. Essentially, you are subtracting one from $$$cnt_c$$$ and adding one to $$$cnt_{c2}$$$. Obviously, you must choose $$$c$$$ and $$$c2$$$ such that $$$cnt_c > cnt2_c$$$ and $$$cnt_{c2} < cnt2_{c2}$$$. So, we only have to focus on $$$c$$$ or $$$c2$$$ since one decreasing will automatically lead to the other increase. The answer is just the sum of $$$cnt_c - cnt2_c$$$ if $$$cnt_c > cnt2_c$$$ over all possible lowercase characters $$$c$$$.

#include <bits/stdc++.h>
using namespace std; 

void solve(){
    int n, q;
    cin >> n >> q;

    vector<vector<int>> pre1(n + 1, vector<int>(26, 0));
    vector<vector<int>> pre2(n + 1, vector<int>(26, 0));

    for (int i = 1; i <= n; i++){
        char c;
        cin >> c;
        pre1[i][c - 'a']++;

        for (int j = 0; j < 26; j++)
            pre1[i][j] += pre1[i - 1][j];
    }
    for (int i = 1; i <= n; i++){
        char c;
        cin >> c;
        pre2[i][c - 'a']++;

        for (int j = 0; j < 26; j++)
            pre2[i][j] += pre2[i - 1][j];
    }
    while (q--){
        int l, r;
        cin >> l >> r;

        int dif = 0;

        for (int c = 0; c < 26; c++){
            int v1 = pre1[r][c] - pre1[l - 1][c];
            int v2 = pre2[r][c] - pre2[l - 1][c];

            dif += abs(v1 - v2);
        }
        cout << dif / 2 << "\n";
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

There are several solutions to this problem, The easiest way is to just fix either $$$a$$$, $$$b$$$ or $$$c$$$. Let's fix $$$a$$$. Since $$$ab + ac + bc \leq n$$$, we know at the minimum, $$$ab \leq n$$$. Divide on both sides to get $$$b \leq \frac{n}{a}$$$. When $$$a = 1$$$, there are $$$n$$$ choices for $$$b$$$. When $$$a = 2$$$, there are $$$\frac{n}{2}$$$ choices for $$$b$$$. So in total, there are $$$n + \frac{n}{2} + \frac{n}{3} + ... + \frac{n}{n}$$$ total choices for $$$b$$$. This is just the harmonic series, so over all possible $$$a$$$, there are about $$$n \log n$$$ choices for $$$b$$$. Therefore, we can afford to loop through both $$$a$$$ and $$$b$$$.

Now that we have $$$a$$$ and $$$b$$$, all that's left is to solve for $$$c$$$. Let's solve for $$$c$$$ in both equations. In the first equation, we can factor $$$c$$$ out to obtain $$$ab + c(a+b) \leq n$$$. So, $$$c \leq \frac{n-ab}{a+b}$$$. In the second equation, $$$c \leq x - a - b$$$. Since we want the $$$c$$$ to satisfy both inequalities, we must choose the stricter one. So, the number of possible $$$c$$$ is $$$\min(\frac{n-ab}{a+b},x-a-b)$$$.

The answer is the sum of number of possible $$$c$$$ over all possible $$$a$$$ and $$$b$$$.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int tc;
    cin >> tc;

    while (tc--){
        int n, x;
        cin >> n >> x;

        long long ans = 0;
        
        for (int a = 1; a <= min(n, x); a++){
            for (int b = 1; a * b <= n and a + b <= x; b++){
                int highestC = min((n - a * b) / (a + b), x - (a + b));
                ans += highestC;
            }
        }
        cout << ans << "\n";
    }
}

How can we efficiently check if a range contains the same amount of zeroes and ones? Let's create an array $$$a$$$ where $$$a_i = -1$$$ if $$$s_i = 0$$$ and $$$a_i = 1$$$ if $$$s_i = 1$$$. Let's denote $$$p$$$ as the prefix sum array of $$$a$$$. We want the contribution of $$$-1$$$ by the zeroes to cancel out with the ones, so if $$$p_r - p_{l-1} = 0$$$, then the range $$$[l, r]$$$ contain equal amounts of zeroes and ones. We can rephrase the problem as the following: for each subrange $$$[l, r]$$$, count the number of pairs $$$(x,y)$$$ such that $$$p_{x-1} = p_y$$$.

Let's fix $$$p_{x-1}$$$ and keep track of all potential $$$y$$$ such that $$$y > x$$$ and $$$p_{x-1} = p_{y}$$$. How many subarrays will cover $$$[x, y]$$$? Well, we have $$$x+1$$$ options as $$$l$$$ and $$$n-y+1$$$ options as $$$r$$$, so the range $$$[x,y]$$$ contributes to $$$(x+1) \cdot (n-y+1)$$$ subarrays. We just need to calculate this expression for all potential $$$y$$$ now. Let's denote the all possible $$$y$$$ as $$$y_1, y_2, ... y_k$$$. We are asked to find the sum of $$$(x+1) \cdot (n-y_1+1) + (x+1) \cdot (n-y_2+1) + \dots + (x+1) \cdot (n-y_k+1)$$$. Let's factor $$$(x+1)$$$ out, and we have $$$(x+1) \cdot ((n-y_1+1)+(n-y_2+1)+\dots+(n-y_k+1))$$$. Since, the second part of the expression is just the sum of all $$$(n-y_i+1)$$$, we can first precalculate that sum and since $$$y > x$$$, subtract as we sweep from left to right.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;
 
template<ll M>
struct modint {
 
    static ll _pow(ll n, ll k) {
        ll r = 1;
        for (; k > 0; k >>= 1, n = (n*n)%M)
            if (k&1) r = (r*n)%M;
        return r;
    }
 
    ll v; modint(ll n = 0) : v(n%M) { v += (M&(0-(v<0))); }
    
    friend string to_string(const modint n) { return to_string(n.v); }
    friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
    friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
    template<typename T> explicit operator T() { return T(v); }
 
    friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
    friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
    friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
    friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
    friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
    friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }
 
    modint& operator+=(const modint n) { v += n.v; v -= (M&(0-(v>=M))); return *this; }
    modint& operator-=(const modint n) { v -= n.v; v += (M&(0-(v<0))); return *this; }
    modint& operator*=(const modint n) { v = (v*n.v)%M; return *this; }
    modint& operator/=(const modint n) { v = (v*_pow(n.v, M-2))%M; return *this; }
    friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
    friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
    friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
    friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
    modint& operator++() { return *this += 1; }
    modint& operator--() { return *this -= 1; }
    modint operator++(int) { modint t = *this; return *this += 1, t; }
    modint operator--(int) { modint t = *this; return *this -= 1, t; }
    modint operator+() { return *this; }
    modint operator-() { return modint(0) -= *this; }
 
    modint pow(const ll k) const {
        return k < 0 ? _pow(v, M-1-(-k%(M-1))) : _pow(v, k);
    }
    modint inv() const { return _pow(v, M-2); }
};
 
using mint = modint<int(MOD)>;
 
 
int main(){
	int t; cin >> t;
	while(t--){
		string s; cin >> s;
		int n = s.size();
		vector<int> p(n+1);
		for(int i = 1; i <= n; i++){
			p[i] = p[i-1] + (s[i-1] == '0' ? -1 : 1);
		}
		vector<vector<ll>> sums(2 * n + 1);
		for(int i = 0; i <= n; i++){
			sums[p[i] + n].push_back(i);
		}
		mint ans = 0;
		for(auto& v: sums){
			int N = v.size();
			vector<ll> j_sum(N+1);
			for(int i = N - 1; i >= 0; i--){
				j_sum[i] = j_sum[i+1] + v[i];
			}
			for(int i = 0; i < N - 1; i++){
				ll left = N - i - 1;
				ans += v[i] * n * left;
				ans -= v[i] * j_sum[i+1];
				ans += v[i] * left;
				ans += n * left;
				ans -= j_sum[i+1];
				ans += left;
			}
		}
		cout << ans << "\n";
	}
}

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

const int MOD = 1e9 + 7;

void solve(){
    string S;
    cin >> S;

    int n = S.size();
    S = " " + S;

    vector<int> P(n + 1, 0);

    for (int i = 1; i <= n; i++){
        P[i] = (S[i] == '1' ? 1 : -1) + P[i - 1];
    }

    map<int, ll> cnt;
    ll ans = 0;

    for (int i = 0; i <= n; i++){
        ans = (ans + (n - i + 1) * cnt[P[i]]) % MOD;
        cnt[P[i]] = (cnt[P[i]] + (i + 1)) % MOD;
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Let's first solve the problem in $$$\mathcal{O}(k)$$$. One possible solution is to loop through each operation and take the largest $$$a_i$$$ each time, and set $$$a_i = \max(0, a_i - b_i)$$$. This can be done with a set or a priority queue.

With that in mind, let's binary search for the largest $$$x$$$ such that every value we add to our score has been greater or equal to $$$x$$$ for all $$$k$$$ operations. Define $$$f(x)$$$ as the number of operations required for every $$$a_i$$$ to be less than $$$x$$$. Specifically, $$$f(x) = \sum_{i=1}^n \lceil \frac{a_i-x}{b_i} \rceil$$$. We are searching for the smallest $$$x$$$ such that $$$f(x) \leq k$$$. Once we've found $$$x$$$, we can subtract $$$f(x)$$$ from $$$k$$$. Note that now, $$$k$$$ must be less than to $$$n$$$ (otherwise we can another operation on all $$$a_i$$$). So, it suffices to run the slow solution for these remaining operations (as long as $$$a_i > 0$$$). Alternatively, we can notice that the remaining operations will all add $$$x-1$$$ to our answer (assuming $$$x > 0$$$).

To obtain the sum of all $$$a_i$$$ we collected when calculating $$$f(x)$$$, we can use the arithmetic sequence sum formula. For each $$$i$$$, the number of terms in the sequence is $$$t = \lceil \frac{a_i-x}{b_i} \rceil$$$. The first term of the sequence is $$$f = a_i - b_i \cdot (t-1)$$$. The last term is $$$a_i$$$. Using the formula, we can add $$$\frac{t}{2}(f+a_i)$$$ to the answer.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        vector<int> a(n), b(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        for (int i = 0; i < n; i++) cin >> b[i];

        int ok = 0, ng = 1e9+1;
        while (ng - ok > 1) {
            int mid = (ok + ng) / 2;

            long long sum = 0;
            for (int i = 0; i < n; i++) {
                if (a[i] >= mid)
                    sum += (a[i] - mid) / b[i] + 1;
            }

            if (sum >= k) ok = mid;
            else ng = mid;
        }

        long long ans = 0;
        int s = 0;

        for (int i = 0; i < n; i++) {
            if (a[i] >= ok) {
                int m = (a[i] - ok) / b[i] + 1;
                ans += 1LL * m * a[i] - 1LL * m * (m - 1) / 2 * b[i];
                s += m;
            }
        }

        ans -= 1LL * ok * (s - k);

        cout << ans << "\n";
    }

    return 0;
}

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

void solve(){
    int n, k;
    cin >> n >> k;

    vector<int> A(n), B(n);
    
    for (int &i : A)
        cin >> i;
    for (int &i : B)
        cin >> i;

    auto getInfo = [&](int cutoff){
        ll ops = 0;
        ll sum = 0;

        for (int i = 0; i < n; i++){
            ll a = A[i];
            ll b = B[i];

            if (cutoff > a)
                continue;

            // a - uses * b >= cutoff
            ll uses = (a - cutoff) / b;
            sum += (uses + 1) * a - b * uses * (uses + 1) / 2; 
            ops += uses + 1;

            sum = min(sum, 2 * (ll)1e18);
        }
        return make_pair(sum, ops);
    };

    int L = 0, H = 1e9 + 5;

    while (L < H){
        int M = (L + H) / 2;
        getInfo(M).second <= k ? H = M : L = M + 1;
    }

    auto [ans, opsUse] = getInfo(L);
    cout << ans + (k - opsUse) * max(L - 1, 0) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

There are two configurations to satisfy every friendship $$$(a, b)$$$: activate all the roads from $$$a \rightarrow a+1 \rightarrow \dots \rightarrow b$$$ or $$$b \leftarrow \dots \leftarrow n \leftarrow 1 \leftarrow \dots \leftarrow a$$$. Let's fix a road we deactivate. Say it goes from $$$i \rightarrow i+1$$$. Observe that the configuration for all friendships is fixed to one of the two cases. For example, if $$$a \leq i < b$$$, then we must use the second configuration.

We can try fixing every road and taking the minimum of number of roads. This can be done with sweep line. Once we reach $$$i = a$$$ for any friendship, we toggle to the second configuration. Once we reach $$$b$$$, we toggle back to the first. We can track maintained roads by performing a range addition on a lazy propagated segment tree for each point covered by the current configuration. The number of roads required is $$$n$$$ minus the number of occurrences of zeroes in the segment tree, which can be tracked with Counting Minimums in a Segment Tree.

#include <bits/stdc++.h>
using namespace std;

class LazySegmentTree {
    struct Node {
        int min_val;
        int count;
        int lazy;
    };

    std::vector<Node> tree;
    int n;

    void buildTree(int v, int tl, int tr) {
        if (tl == tr) {
            tree[v] = {0, 1, 0};
        } else {
            int tm = (tl + tr) / 2;
            buildTree(v*2, tl, tm);
            buildTree(v*2+1, tm+1, tr);
            merge(v);
        }
    }

    void apply(int v, int tl, int tr, int val) {
        tree[v].min_val += val;
        tree[v].lazy += val;
    }

    void push(int v, int tl, int tr) {
        if (tree[v].lazy != 0) {
            int tm = (tl + tr) / 2;
            apply(v*2, tl, tm, tree[v].lazy);
            apply(v*2+1, tm+1, tr, tree[v].lazy);
            tree[v].lazy = 0;
        }
    }

    void merge(int v) {
        if (tree[v*2].min_val < tree[v*2+1].min_val) {
            tree[v].min_val = tree[v*2].min_val;
            tree[v].count = tree[v*2].count;
        } else if (tree[v*2].min_val > tree[v*2+1].min_val) {
            tree[v].min_val = tree[v*2+1].min_val;
            tree[v].count = tree[v*2+1].count;
        } else {
            tree[v].min_val = tree[v*2].min_val;
            tree[v].count = tree[v*2].count + tree[v*2+1].count;
        }
    }

    void updateRange(int v, int tl, int tr, int l, int r, int addend) {
        if (l > r) return;
        if (l == tl && r == tr) {
            apply(v, tl, tr, addend);
        } else {
            push(v, tl, tr);
            int tm = (tl + tr) / 2;
            updateRange(v*2, tl, tm, l, std::min(r, tm), addend);
            updateRange(v*2+1, tm+1, tr, std::max(l, tm+1), r, addend);
            merge(v);
        }
    }

    std::pair<int, int> queryRange(int v, int tl, int tr, int l, int r) {
        if (l > r) return {INT_MAX, 0};
        if (l <= tl && tr <= r) {
            return {tree[v].min_val, tree[v].count};
        }
        push(v, tl, tr);
        int tm = (tl + tr) / 2;
        auto left = queryRange(v*2, tl, tm, l, std::min(r, tm));
        auto right = queryRange(v*2+1, tm+1, tr, std::max(l, tm+1), r);
        if (left.first < right.first) {
            return left;
        } else if (left.first > right.first) {
            return right;
        } else {
            return {left.first, left.second + right.second};
        }
    }

public:
    LazySegmentTree(int _n) {
    	n = _n;
        tree.resize(4*n);
        buildTree(1, 0, n-1);
    }

    void updateRange(int l, int r, int addend) {
        updateRange(1, 0, n-1, l, r, addend);
    }

    std::pair<int, int> queryRange(int l, int r) {
        return queryRange(1, 0, n-1, l, r);
    }
    
    int get_maintained(){
    	pair<int, int> res = queryRange(0, n-1);
    	assert(res.first == 0);
    	return n - res.second;
    };
};


void solve() {
	int n, m; cin >> n >> m;
	vector<pair<int, int>> p(m);
	for(int i = 0; i < m; i++){
		cin >> p[i].first >> p[i].second;
		p[i].first--; p[i].second--;
	}
	LazySegmentTree st(n);
	for(pair<int, int> i: p){
		st.updateRange(i.first, i.second - 1, 1);
	}
	int ans = st.get_maintained();
	vector<vector<int>> start(n), end(n);
	for(int i = 0; i < m; i++){
		start[p[i].first].push_back(i);
		end[p[i].second].push_back(i);
	}
	for(int i = 0; i < n; i++){
		for(int j: start[i]){
			st.updateRange(p[j].first, p[j].second - 1, -1);
			st.updateRange(p[j].second, n - 1, 1);
			st.updateRange(0, p[j].first - 1, 1);
		}
		for(int j: end[i]){
			st.updateRange(p[j].second, n - 1, -1);
			st.updateRange(0, p[j].first - 1, -1);
			st.updateRange(p[j].first, p[j].second - 1, 1);
		}
		ans = min(ans, st.get_maintained());
	}
	cout << ans << "\n";
}

signed main() {
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

Consider the $$$n$$$-gon formed by the houses, with each road becoming an edge of the polygon. We draw diagonals between houses if they are friends. Let each diagonal arbitrarily "cover" one side of the polygon, where every road contained within one section split by the diagonal is covered by the diagonal.

We claim that two roads can both be deleted if and only if they are covered by the same set of diagonals. First, this is equivalent to saying that when we draw a line between these two roads, they do not intersect any of our drawn diagonals. (This is since if any diagonal covers one road and not another, then they must be on opposite sides of the diagonal, so drawing a line between the two roads must intersect that diagonal. The converse also holds.)

Now note that if two roads are on opposite sides of a diagonal, they cannot both be deleted, as then there is no path along maintained roads that connects the two endpoints of the diagonals, or the two houses that are friends.

So it suffices to count the most frequent set of covered diagonals over all roads.

We can represent a diagonal cover for some road using a xor hashing, where each diagonal is assigned a random number, and the roads that are covered by that diagonal are xor'd by this number.

By using $$$64$$$-bit integers, the probability of collision is negligible, as each 64-bit integer has equal probability of representing a unique set of diagonals, and we have at most $$$n$$$ represented sets.

For each pair of friends, we want to xor all values in a range by some random number. This can be done with a prefix xor array in $$$\mathcal{O}(1)$$$ per pair of friends. Counting the most frequent value at the end will take $$$\mathcal{O}(n \log n)$$$ time if a map is used or $$$\mathcal{O}(n)$$$ if an unordered map is used. In all, this solution runs in $$$\mathcal{O}(n \log n + m)$$$ or $$$\mathcal{O}(n + m)$$$ time.

#include <bits/stdc++.h>
#define int long long
using namespace std;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int n,m,a,b,k,t; 

void solve() {
	cin >> n >> m;
	vector<int> v(n); 
	while (m--) {
		k=rng(); cin >> a >> b;
		v[a-1]^=k;
		v[b-1]^=k;
	}
	map<int,int> c;
	for (int r:v) m=max(m,c[a^=r]++); 
	cout << n-m-1 << "\n"; 
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> t;
	while (t--) solve();
}

We can construct a solution by fixing all $$$x_i$$$ as $$$x_c$$$ or all $$$y_i$$$ as $$$y_c$$$. For example, if we fix all $$$y_i$$$ as $$$y_c$$$, then we can output pairs $$$(x_c-1, y_c), (x_c+1, y_c), (x_c-2, y_c), (x_c+2, y_c), ... , (x_c- \lfloor \frac{k}{2} \rfloor, y_c), (x_c + \lfloor \frac{k}{2} \rfloor, y_c)$$$. If the $$$k$$$ is odd, we need one more pair, so just output $$$(x_c, y_c)$$$.

#include <iostream>
using namespace std;

int main() {
	int t; cin >> t;
	while(t--){
		int x, y, k; cin >> x >> y >> k;
		for(int i = 0; i < k - k % 2; i++){
			cout << x - (i & 1 ? 1 : -1) * (i / 2 + 1) << " " << y << "\n";
		} 
		if(k & 1){
			cout << x << " " << y << "\n";
		}
	}
}

We can always construct a solution such that the number of pairs $$$(i, j)$$$ is $$$1$$$ where the only pair is $$$(1, n)$$$. There exists several constructions, such as rotating $$$p$$$ once or increment all $$$p_i$$$ (and $$$p_i = n$$$ turns into $$$p_i = 1$$$).

Consider the former construction, where $$$q = [p_2, p_3, ..., p_n, p_1]$$$. For an arbitrarily interval $$$[i, j]$$$, $$$p[i..j]$$$ and $$$q[i..j]$$$ will have exactly $$$1$$$ element that's different, disregarding ordering. Since we have a permutation and all elements are distinct, the sum in the range will never be the same. The only exception is the entire array, of course.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		vector<int> p(n);
		for(int& i: p) cin >> i;
		rotate(p.begin(), p.begin() + 1, p.end());
		for(int i: p) cout << i << " ";
		cout << "\n";
	}
}

First, solve for $$$k = 0$$$. Find some nice characterization about $$$med(c_i)$$$ and thus the maximum score.

Divide into $$$2$$$ cases where we either increment the max element or the median.

Apply binary search

Let's forget about the operations of adding $$$1$$$ to $$$a_i$$$ and figure out how to find an array's score. Assume the array $$$a$$$ is sorted in increasing order as the order doesnt change the problem.

First observe how $$$med(c_i)$$$ changes with respect to $$$i$$$. $$$med(c_i)$$$ is always either $$$a_{\lfloor \frac{n}{2} \rfloor}$$$ or $$$a_{\lfloor \frac{n + 2}{2} \rfloor}$$$. You can prove this formally by considering different positions of $$$i$$$ with respect to the initial median position. Specifically, for all $$$i \le \lfloor \frac{n}{2} \rfloor$$$, $$$med(c_i) = a_{\lfloor \frac{n + 2}{2} \rfloor}$$$, and for other $$$i$$$, $$$med(c_i) = a_{\lfloor \frac{n}{2} \rfloor}$$$.

Claim 1 : The score of the final array (after sorting in increasing order) is $$$a_n + med(c_n)$$$

Hence, our score can be nicely characterized by "max + median of the others".

Claim 2 : Either we will use all $$$k$$$ operations on the element which eventually becomes max element in our array, or we will use all operations trying to improve $$$med(c_n)$$$ and keep max element constant.

Thus, we are in $$$2$$$ cases now, either increase max, or increase median of the rest. We will solve the problem considering both cases separately.

Case $$$1$$$ : We do operations on the element which becomes max eventually.

Case 2 : We do operations to increase the median of the others.

Thus, the problem is solved in $$$O(N \cdot log (MAX))$$$. The code is nicely written and commented, you may want to check it out.

#include <bits/stdc++.h> 
using namespace std;

int main(){
    int t; cin >> t;
    
    while (t--){
        int n, k; cin >> n >> k;
        
        vector <pair<int, int>> a(n);
        for (auto &x : a) cin >> x.first;
        for (auto &x : a) cin >> x.second;
        sort(a.begin(), a.end());
        
        long long ans = 0;
        // case 1 : increment max 
        for (int i = 0; i < n; i++) if (a[i].second == 1){
            // find med(c_i) 
            int mc;
            if (i < n / 2) mc = a[n / 2].first;
            else mc = a[(n - 2) / 2].first;
            
            ans = max(ans, 0LL + a[i].first + k + mc);
        }
        
        // case 2 : increment median
        int lo = 0, hi = 2e9;
        while (lo != hi){
            int mid = (1LL + lo + hi) / 2;
            
            int z = 0;
            vector <int> smaller_list;
            for (int i = 0; i < n - 1; i++){
                if (a[i].first >= mid){
                    z++;
                } else if (a[i].second == 1){
                    smaller_list.push_back(mid - a[i].first); // list of numbers smaller than x but b[i] = 1 
                }
            }
            
            reverse(smaller_list.begin(), smaller_list.end()); // list will be sorted in ascending, but we want sorted in descending, as greedily changing largest elements 
            int kk = k;
            for (auto x : smaller_list) if (kk >= x){
                kk -= x;
                z++;
            }
            
            if (z >= (n + 1) / 2) lo = mid;
            else hi = mid - 1;
        }
        
        ans = max(ans, 0LL + a[n - 1].first + lo);
        
        cout << ans << "\n";
    }
    return 0;
}

First, let's consider if there was no alternative bridges. Then obviously, if Bessie starts at island $$$i$$$ and keeps moving forwards, it is impossible for Elsie to move past island $$$i$$$ since the bridge would have already collapsed. From this, we can deduce that Bessie cannot let Elsie use these alternative bridges to overtake the island Bessie is on, or else Elsie will always reach the end first.

Therefore, Bessie will keep moving right in hopes of breaking enough bridges so that it is impossible to for Elsie to overtake Bessie. This can be simplified to: consider we are at island $$$i$$$ and $$$t$$$ units of time has passed, for all alternative bridges that Elsie can take with an endpoint $$$v > i + t$$$, we have to reach $$$v$$$ before her.

Let $$$d_i$$$ denote the minimum amount of time Elsie takes to reach island $$$i$$$. For the first case, consider all bridges with endpoints $$$v > S$$$, then $$$d_v \geq v - S - 1$$$ must hold true since we want to reach $$$v$$$ before Elsie does when we keep going right. We can rearrange the equation as $$$S \geq v - d_v - 1$$$. To make sure this holds true for all bridges, we just have to make sure this is true for the maximum value of $$$v - d_v$$$.

All $$$d_i$$$ can be calculated using a linear sweep to the right, and we can track all $$$v - d_v$$$ with a sweep to the left. Note that we cannot take a bridge if it starts past $$$S$$$, so we need to track the maximum with a multiset and erasing as we sweep.

Time Complexity is $$$\mathcal{O}(n \log n)$$$. There exists other solutions using prefix sums in $$$\mathcal{O}(n)$$$ and segment tree in $$$\mathcal{O}(n \log n)$$$

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i = (a); i >= (b); --i)
#define trav(a,x) for(auto& a: x)

void solve() {
	int n, m; cin >> n >> m;
	vector<vector<int>> g(n), rg(n);
	FOR(i,0,m){
		int u, v; cin >> u >> v;
		--u; --v;
		g[u].pb(v);
		rg[v].pb(u);
	}
	FOR(i,0,n-1) g[i].pb(i+1);
	vector<int> dist(n, -1);
	queue<int> q;
	dist[0] = 0;
	q.push(0);
	while(!q.empty()){
		int f = q.front();
		q.pop();
		trav(i, g[f]){
			if(dist[i] == -1){
				dist[i] = dist[f] + 1;
				q.push(i);
			}
		}
	}
	multiset<int> max_good_rights;
	vector<vector<int>> to_erase(n);
	string ans = string(n - 1, '0');
	ROF(i,n-1,0){
		trav(j, rg[i]){
			int max_right = i - dist[j];
			max_good_rights.insert(max_right);
			to_erase[j].pb(max_right);
		}
		trav(j, to_erase[i]){
			max_good_rights.erase(max_good_rights.find(j));
		}
		if(i < n - 1){
			int max_good_right = max_good_rights.empty() ? -1 : *prev(max_good_rights.end());
			if(i >= max_good_right - 1){
				ans[i] = '1';
			}
		}
	}
	cout << ans << endl;
}

signed main() {
	cin.tie(0) -> sync_with_stdio(0);
	int t = 1;
	cin >> t;
	for(int test = 1; test <= t; test++){
		solve();
	}
}

Consider the ball with the maximum number. Let this ball be $$$m$$$. That ball can clearly be the last ball remaining. And if we are able to merge some ball $$$i$$$ with ball $$$m$$$ (whilst removing $$$m$$$), then ball $$$i$$$ can also be the last ball remaining.

We can do a divide and conquer solution. For some range $$$[l,r]$$$, let $$$m$$$ be the ball with the maximum value. Clearly, $$$m$$$ can be the last ball remaining if we only consider the range $$$[l, r]$$$.

Let's first recurse on $$$[l,m)$$$ and $$$(m,r]$$$. Let $$$s_l=a_l+a_{l+1}+\cdots+a_{m-1}$$$ (i.e. the sum of the left half). If $$$s_l < a_m$$$ then no ball in the left half can be the last one remaining. Otherwise, the results (i.e. whether each ball can be the last one standing) for range $$$[l,r]$$$ for balls in $$$[l,m)$$$ is the results we computer when recursing onto $$$[l,m)$$$. The same reasoning holds for the right half.

We can use a sparse table to find the maximum ball in any range. This leads to a $$$\mathcal{O}(n\log n)$$$ solution.

#include <bits/stdc++.h>
using namespace std; 

#define ll long long
#define pll pair<ll, ll>

const int MAX = 2e5 + 5;

int n, x, ans; ll A[MAX], bad[MAX], P[MAX]; pll rmq[MAX][18];

void dnq(int l, int r){
    if (l >= r)
        return;
    
    int lg = 31 - __builtin_clz(r - l + 1);
    int mid = max(rmq[l][lg], rmq[r - (1 << lg) + 1][lg]).second;
    
    dnq(l, mid - 1);
    dnq(mid + 1, r);

    ll sum1 = P[mid - 1] - P[l - 1];
    ll sum2 = P[r] - P[mid];

    // Left half bad
    if (A[mid] > sum1){
        bad[l] += 1;
        bad[mid] += -1;
    }
    // Right half bad
    if (A[mid] > sum2){
        bad[mid + 1] += 1;
        bad[r + 1] += -1;
    }
}

void solve(){
    cin >> n >> x;

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        bad[i] = 0;
        rmq[i][0] = {A[i], i};
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    
    dnq(1, n);

    ans = 0;

    for (int i = 1; i <= n; i++){
        bad[i] += bad[i - 1];
        ans += !bad[i];
    }
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

For some ball $$$i$$$, let $$$l_i$$$ and $$$r_i$$$ be the first balls on the left and right that have a value greater than $$$a_i$$$.

Proccess the balls from largest $$$a_i$$$ to smallest $$$a_i$$$. For each ball $$$i$$$, let $$$\text{ans}_i$$$ denote whether it can be the last ball remaining. We know that if we merge ball $$$i$$$ with some ball $$$j$$$ (while discarding $$$j$$$) and $$$\text{ans}_j=1$$$, then $$$\text{ans}_i=1$$$. Furthermore, we know that balls $$$l_i$$$ and $$$r_i$$$ can freely merge with balls $$$j$$$ where $$$j$$$ is in interval $$$[l_i+1 \ldots r_i-1]$$$ while discarding $$$j$$$ (i.e. $$$\text{ans}_{l_i}$$$ and $$$\text{ans}_{r_i}$$$ would have taken this into account).

This motivates the following idea. Let $$$s$$$ be the sum of values in $$$[l_i+1 \ldots r_i-1]$$$. If $$$s \geq a_{l_i}$$$ then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{l_i}$$$. Similarly, if $$$s \geq a_{r_i}$$$, then we do $$$\text{ans}_i := \text{ans}_i |\text{ans}_{r_i}$$$. This solution runs in $$$\mathcal{O}(n \log n)$$$ due to sorting.

#include <bits/stdc++.h>
using namespace std; 

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<int> A(n + 5);
    vector<ll> P(n + 5);
    vector<int> ans(n + 5, 0);
    vector<int> ord(n);
    set<int> S{0, n + 1};

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];
        ord.push_back(i);
    }
    sort(ord.begin(), ord.end(), [&](int a, int b){
        return A[a] > A[b];
    });
    for (int i : ord){
        int l = *(--S.lower_bound(i));
        int r = *S.lower_bound(i);
        ll sum = P[r - 1] - P[l];

        if (i == ord[0])
            ans[i] = true;
        if (sum >= A[l])
            ans[i] |= ans[l];
        if (sum >= A[r])
            ans[i] |= ans[r];
        
        S.insert(i);
    }
    cout << accumulate(ans.begin(), ans.end(), 0) << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Consider the naive greedy solution. We continuously merge with the balls on the left and right without removing our ball until we can't anymore or our ball is the final remaining one.

Suppose at some point in this greedy approach, we can not merge with the balls on our left and right anymore without discarding our ball. Let our ball be $$$i$$$. Then we have the following cases.

1. There is a ball $$$l$$$ on the left of $$$i$$$ and ball $$$r$$$ on the right of $$$i$$$. Then: $$$\min(a_l,a_r) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$.
2. There is a ball $$$l$$$ on the left of $$$i$$$ but no ball on the right of $$$i$$$. Then: $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{\text{last}}$$$.
3. There exists no ball on the left of $$$i$$$ but a ball $$$r$$$ on the right of $$$i$$$. Then: $$$a_r > a_1+a_2+\cdots+a_{r-1}$$$.

For some ball $$$i$$$, if there exists some $$$l$$$ and/or some $$$r$$$ such that one of the above is true, then there exists no way for our ball to be the last one remaining. Otherwise, the ball can be the last one remaining.

Let $$$p$$$ be the prefix sum array of $$$a$$$ (i.e. $$$p_i=a_1+a_2+\cdots+a_i$$$).

For some ball $$$i$$$, we want to do the following.

1. Find the smallest $$$r_1$$$ such that there exists some $$$l$$$ such that ($$$l, r_1$$$) is a pair (i.e. $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$). Finding this is more difficult than the other cases and will be focused on later.
2. Find the smallest $$$r_2$$$ such that $$$a_{r_2} > a_1+a_2+\cdots+a_{{r_r}-1}$$$. We can rewrite it as as $$$a_{r_2} > p_{r_2-1}$$$ and it can easily be found.
3. Find the smallest $$$r_l$$$ such that there exists no $$$l$$$ on the left of $$$i$$$ such that $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r_l}$$$. We can rewrite the inequality as finding the first $$$r_l$$$ such that $$$p_{r_l} \geq a_l + p_l$$$ which can be done with binary search.

Suppose at some $$$i$$$, we know its $$$r_l$$$, $$$r_1$$$, and $$$r_{2}$$$. Then we know ball $$$i$$$ can be the last one remaining for prefixes spanning from $$$r_l$$$ to $$$\min(r_1-1, r_{2}-1)$$$ so we can do a range add with prefix sums.

The only thing we have not resolved yet is how to find the smallest $$$r_1$$$ for some $$$i$$$ such that $$$\min(a_l,a_{r_1}) > a_{l+1}+a_{l+2}+\cdots+a_{r_1-1}$$$.

Let's iterate over $$$r$$$. For each $$$r$$$ we want to find the leftmost $$$l$$$ such that $$$\min(a_l,a_{r}) > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$

A key observation is that we can write the following inequality as $$$a_l > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ and $$$a_r > a_{l+1}+a_{l+2}+\cdots+a_{r-1}$$$ (both have to be true).

Using prefix sums, the equations can be rewritten as $$$a_l + p_l > p_{r-1}$$$ and $$$p_l > p_{r-1} - a_r$$$.

So some $$$(l,r)$$$ works if the equation above is satisfied. Consider the second part $$$p_l > p_{r-1} - a_r$$$. We can binary search to find the range of available $$$l$$$ that satisfy this. Specifically, let $$$l_b$$$ be the lower bound of the range. Then, any $$$l$$$ in $$$[l_b...i)$$$ satisfies this.

Now, let's try to satisfy $$$a_l + p_l > p_{r-1}$$$. Unfortunately, $$$a_l + p_l$$$ is not monotonic so the method above will not work. Instead, we can create a sparse table over all $$$a_i + p_i$$$. Then we can binary search to find the first $$$l_{opt}$$$ such that the maximum in range $$$[l_b,l_{opt}]$$$ (which can be found with the sparse table) is greater than $$$p_{r-1}$$$.

Circling back, $$$r_1$$$ is the minimum $$$r$$$ of an interval covering $$$i$$$ which can be found with things such as sweepline. In all, this solution runs in $$$\mathcal{O}(n \log n)$$$ time.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve(){
    int n, x;
    cin >> n >> x;

    vector<ll> A(n + 5, 0);
    vector<ll> P(n + 5, 0);
    vector<vector<ll>> rmq(n + 5, vector<ll>(18, 0));

    for (int i = 1; i <= n; i++){
        cin >> A[i];
        P[i] = P[i - 1] + A[i];        
        rmq[i][0] = A[i] + P[i];
    }
    for (int j = 1; j <= 17; j++)
        for (int i = 1; i + (1 << j) - 1 <= n; i++)
            rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);

    vector<vector<int>> add(n + 5), rem(n + 5);

    auto ins = [&](int l, int r, int v){
        l = max(l, 1);

        if (l > r)
            return;

        add[l].push_back(v);
        rem[r + 1].push_back(v);
    };
    for (int r = 1; r <= n; r++){
        // r is a roadblock
        if (A[r] > P[r - 1])
            ins(1, r - 1, r);

        // Find leftmost l possible
        int lowerB = upper_bound(P.begin() + 1, P.begin() + n + 1, P[r - 1] - A[r]) - P.begin();
        int lo = lowerB, hi = r - 1;

        while (lo < hi){
            int mid = (lo + hi) / 2;

            // Query lowerB...mid
            int lg = 31 - __builtin_clz(mid - lowerB + 1);
            ll val = max(rmq[lowerB][lg], rmq[mid - (1 << lg) + 1][lg]);

            val > P[r - 1] ? hi = mid : lo = mid + 1;
        }
        ins(lo + 1, r - 1, r);
    }

    multiset<int> badR{n + 1};
    vector<int> ans(n + 5, 0);
    ll worst = 0; 

    for (int i = 1; i <= n; i++){
        for (int v : add[i])
            badR.insert(v);
        for (int v : rem[i])
            badR.erase(badR.find(v));

        int l = lower_bound(P.begin() + i, P.begin() + n + 1, worst) - P.begin();
        int r = *badR.begin();

        // Active for interval [l...r)
        if (l <= r){
            ans[l]++;
            ans[r]--;
        }
        worst = max(worst, A[i] + P[i]);
    }
    
    for (int i = x; i <= n; i++){
        ans[i] += ans[i - 1];
        cout << ans[i] << " \n"[i == n];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		string a, b; cin >> a >> b;
		swap(a[0], b[0]);
		cout << a << " " << b << endl;
	}
}

To maximize the number of multiples of $$$x$$$ less than $$$n$$$, it optimal to choose a small $$$x$$$, in this case, $$$2$$$. The only exception is $$$n = 3$$$, where it is optimal to choose $$$3$$$ instead, since both $$$2$$$ and $$$3$$$ have only one multiple less than $$$3$$$.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		cout << (n == 3 ? 3 : 2) << endl;
 	}
}

The only element that can be the sum of all other elements is the maximum element, since all elements are positive. Therefore, for each prefix $$$i$$$ from $$$1$$$ to $$$n$$$, check if $$$sum(a_1, a_2, ..., a_i) - max(a_1, a_2, ..., a_i) = max(a_1, a_2, ..., a_i)$$$. The sum and max of prefixes can be tracked with variables outside the loop.

#include <iostream>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int n; cin >> n;
		int a[n];
		for(int i = 0; i < n; i++)
			cin >> a[i];
		long long sum = 0;
		int mx = 0, ans = 0;;
		for(int i = 0; i < n; i++){
			sum += a[i];
			mx = max(mx, a[i]);
			if(sum - mx == mx) 
				ans++;
		}
		cout << ans << endl;
	}
}

Note that the manhattan circle is always in a diamond shape, symmetric from the center. Let's take notice of some special characteristics that can help us. One way is to find the top and bottom points of the circle. Note that these points will have columns at the center of the circle, so here we can acquire the value of $$$k$$$. To find $$$h$$$, since the circle is symmetric, it is just the middle of the rows of the top and bottom points.

Note that we never needed to find the value of $$$r$$$.

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;

int main(){
	int t; cin >> t;
	while(t--){
		int n, m; cin >> n >> m;
		vector<vector<char>> g(n, vector<char>(m));
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cin >> g[i][j];
			}
		}
		pair<int, int> top = {INF, INF}, bottom = {-INF, -INF};
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(g[i][j] == '#'){
					top = min(top, {i, j});
					bottom = max(bottom, {i, j});
				}
			}
		}
		assert(top.second == bottom.second);
		cout << (top.first + bottom.first) / 2 + 1 << " " << top.second + 1 << endl;
	}
}

Since the side lengths of $$$S$$$ has to multiply to $$$k$$$, all three side lengths of $$$S$$$ has to be divisors of $$$k$$$. Let's denote the side lengths of $$$S$$$ along the $$$x$$$, $$$y$$$, and $$$z$$$ axes as $$$a$$$, $$$b$$$, and $$$c$$$ respectively. For $$$S$$$ to fit in $$$B$$$ , $$$a \leq x$$$, $$$b \leq y$$$, and $$$c \leq z$$$ must hold. Because of the low constraints, we can afford to loop through all possible values of $$$a$$$ and $$$b$$$, and deduce that $$$c=\frac{k}{a \cdot b}$$$ (make sure $$$c \leq z$$$ and $$$c$$$ is an integer). To get the amount of ways we can place $$$S$$$, we can just multiply the amount of shifting space along each axes, and that just comes down to $$$(x−a+1) \cdot (y−b+1) \cdot (z−c+1)$$$. The answer is the maximum among all possible values of $$$a$$$, $$$b$$$, and $$$c$$$ .

The time complexity is $$$\mathcal{O}(n^2)$$$ where $$$n$$$ is at most $$$2000$$$.

#include <iostream>
using namespace std;
using ll = long long;

int main(){
	int t; cin >> t;
	while(t--){
		ll x, y, z, k; cin >> x >> y >> z >> k;
		ll ans = 0;
		for(int a = 1; a <= x; a++){
			for(int b = 1; b <= y; b++){
				if(k % (a * b)) continue;
				ll c = k / (a * b);
				if(c > z) continue;
				ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);
				ans = max(ans, ways);
			}
		}
		cout << ans << "\n";
	}
}

Unfortunately, there was a lot of hacks on this problem, and we're sorry for it. Since our intended solution is not binary search, we didn't really take overflow using binary search seriously. I (cry) prepared this problem and I only took into account about overflow with big cooldown, but I forgot overflow can happen on attacks as well. I apologize and we will do better next time!

Since the sum of $$$h$$$ is bounded by $$$2 \cdot 10^5$$$, and each attack deals at least $$$1$$$ damage. If we assume every turn we can make at least one attack, the sum of turns to kill the boss in every test case is bounded by $$$2 \cdot 10^5$$$. This means that we can afford to simulate each turn where we make at least one attack.

But what if we cannot make an attack on this turn? Since the cooldown for each attack can be big, we cannot increment turns one by one. We must jump to the next turn we can make an attack. This can be done by retrieving the first element of a sorted set, where the set stores pairs {$$$t$$$, $$$i$$$} which means {next available turn you can use this attack, index of this attack} for all $$$i$$$. Here, we can set the current turn to $$$t$$$ and use all attacks in the set with first element in the pair equal to $$$t$$$. Remember to insert the pair to {$$$c_i + t$$$, $$$i$$$} back into the set after processing the attacks.

The time complexity is $$$\mathcal{O}(h \log n)$$$.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int t; cin >> t;
	while(t--){
		int h, n; cin >> h >> n;
		vector<int> a(n), c(n);
		for(int& i: a) cin >> i;
		for(int& i: c) cin >> i;
		set<pair<long long, int>> S;
		for(int i = 0; i < n; i++){
			S.insert({1, i});
		}
		long long last_turn = 1;
		while(h > 0){
			auto [turn, i] = *S.begin();
			S.erase(S.begin());
			last_turn = turn;
			h -= a[i];
			S.insert({turn + c[i], i});
		}
		cout << last_turn << "\n";
	}
}

// comment "tomato" if you see this comment

Try to solve this if $$$1 \le h \le 10^9$$$.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve(){
    ll h, n;
    cin >> h >> n;

    vector<ll> A(n), C(n);

    for (ll &i : A)
        cin >> i;
    for (ll &i : C)
        cin >> i;
    
    auto chk = [&](ll t){
        ll dmg = 0;
        for (int i = 0; i < n and dmg < h; i++){
            ll cnt = (t - 1) / C[i] + 1;

            if (cnt >= h)
                return true;

            dmg += cnt * A[i];
        }
        return dmg >= h;
    };

    ll L = 1, H = 1e12;

    while (L < H){
        ll M = (L + H) / 2;
        chk(M) ? H = M : L = M + 1;
    }
    cout << L << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

To satisfy $$$D(k \cdot n) = k \cdot D(n)$$$, each digit $$$d$$$ in $$$n$$$ must become $$$k \cdot d$$$ after multiplying $$$n$$$ by $$$k$$$. In other words, none of $$$n$$$'s digits can carry over to the next digit upon multiplication. From this, we can deduce that each digit in $$$n$$$ must be less than or equal to $$$\lfloor \frac{9}{k} \rfloor$$$. Only thing left is to count all such numbers in the range of $$$10^l$$$ inclusive and $$$10^r$$$ exclusive.

Every number below $$${10}^r$$$ has $$$r$$$ or less digits. For numbers with less than $$$r$$$ digits, let's pad the beginning with zeroes until it becomes a $$$r$$$ digit number (for example, if $$$r = 5$$$, then $$$69$$$ becomes $$$00069$$$). This allows us to consider numbers with less than $$$r$$$ digits the same way as numbers with exactly $$$r$$$ digits. For each digit, we have $$$\lfloor \frac{9}{k} \rfloor + 1$$$ choices (including zero), and there are $$$r$$$ digits, so the total number of numbers that satisfies the constraint below $$${10}^r$$$ is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r$$$.

To get the count of numbers in range, it suffices to subtract all valid numbers less than $$$10^l$$$. Therefore, the answer is $$$(\lfloor \frac{9}{k} \rfloor + 1)^r - (\lfloor \frac{9}{k} \rfloor + 1)^l$$$. To exponentiate fast, we can use modular exponentiation.

MOD = int(1e9+7)
t = int(input())
for _ in range(t):
    l, r, k = map(int, input().split())
    print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD)

Let's first solve the problem if we can only select and fill rows. Columns can be handled in the exact same way.

For each row $$$r$$$, we need to find the size of the component formed by filling row $$$r$$$ (i.e. the size of the component containing row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$).

The size of the component containing row $$$r$$$ if we set all cells in row $$$r$$$ to be $$$\texttt{#}$$$ will be the sum of:

1. The number of $$$\texttt{.}$$$ in row $$$r$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_r$$$ denote this value for some row $$$r$$$.
2. The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.

The challenge is computing the second term quickly. For some component, let $$$s$$$ be the size of the component and let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component will contain cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$. Note that we can find these values with a dfs. Since the component will contribute $$$s$$$ to rows in $$$[r_{min}-1,r_{min},\ldots r_{max}+1]$$$, we add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.

We find the maximum $$$F_r+R_r$$$ and then handle columns in the same way. This solution runs in $$$\mathcal{O}(nm)$$$ time.

#include <bits/stdc++.h>
using namespace std;

int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
vector<vector<bool>> vis; vector<vector<char>> A;

void dfs(int i, int j){
    if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
        return;
    
    vis[i][j] = true;

    sz++;
    minR = min(minR, i);
    maxR = max(maxR, i);
    minC = min(minC, j);
    maxC = max(maxC, j);

    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}

void solve(){
    cin >> n >> m;

    R.assign(n + 5, 0);
    C.assign(m + 5, 0);
    freeR.assign(n + 5, 0);
    freeC.assign(m + 5, 0);
    vis.assign(n + 5, vector<bool>(m + 5, false));
    A.assign(n + 5, vector<char>(m + 5, ' '));

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> A[i][j];

            if (A[i][j] == '.'){
                freeR[i]++;
                freeC[j]++;
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (vis[i][j] or A[i][j] == '.')
                continue;

            // Reset
            sz = 0;
            minR = 1e9;
            maxR = -1e9;
            minC = 1e9;
            maxC = -1e9;

            dfs(i, j);

            // Expand by 1 since adjacent cells also connect
            minR = max(minR - 1, 1);
            maxR = min(maxR + 1, n);
            minC = max(minC - 1, 1);
            maxC = min(maxC + 1, m);
            
            // Update prefix sums
            R[minR] += sz;
            R[maxR + 1] -= sz;

            C[minC] += sz;
            C[maxC + 1] -= sz;
        }
    }

    ans = 0;

    for (int i = 1; i <= n; i++){
        R[i] += R[i - 1];
        ans = max(ans, freeR[i] + R[i]);
    }
    for (int i = 1; i <= m; i++){
        C[i] += C[i - 1];
        ans = max(ans, freeC[i] + C[i]);
    }

    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

For each row $$$r$$$ and column $$$c$$$, we need to find the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ (i.e. the size of the component containing row $$$r$$$ and column $$$c$$$ if we set all cells in both row $$$r$$$ and column $$$c$$$ to be $$$\texttt{#}$$$).

Extending the reasoning in H1, for some row $$$r$$$ and column $$$c$$$, consider the sum of:

1. The number of $$$\texttt{.}$$$ in row $$$r$$$ or column $$$c$$$ since these cells will be set to $$$\texttt{#}$$$. Let $$$F_{r,c}$$$ denote this value for some row $$$r$$$ and column $$$c$$$.
2. The sum of sizes of components containing a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ (i.e. components that are touching row $$$r$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$R_r$$$ denote this value for some row $$$r$$$.
3. The sum of sizes of components containing a cell in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ (i.e. components that are touching column $$$c$$$). This is since these components will be part of the component containing row $$$r$$$ and column $$$c$$$. Let $$$C_c$$$ denote this value for some column $$$c$$$.

However, components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$ will be overcounted (since it will be counted in both terms $$$2$$$ and $$$3$$$) (you can think of it as components touching both row $$$r$$$ and column $$$c$$$). Thus, we need to subtract the sum of sizes of components that contain a cell in either row $$$r-1$$$, $$$r$$$, or $$$r+1$$$ as well as in either column $$$c-1$$$, $$$c$$$, or $$$c+1$$$. Let $$$B_{r,c}$$$ denote this for some row $$$r$$$ and column $$$c$$$.

Then the size of the component formed by filling both row $$$r$$$ and column $$$c$$$ will be $$$F_{r,c}+R_r+C_c-B_{r,c}$$$ and we want to find the maximum value of this.

Let's try to calculate these values efficiently. Consider some component.

1. Let $$$s$$$ be its size.
2. Let $$$r_{min}$$$ and $$$r_{max}$$$ denote the minimum and maximum row of a cell in the component. This means that the component contains cells with rows $$$r_{min},r_{min+1},...,r_{max}$$$.
3. Let $$$c_{min}$$$ and $$$c_{max}$$$ denote the minimum and maximum column of a cell in the component. This means that the component contains cells with columns $$$c_{min},c_{min+1},...,c_{max}$$$.

All these values can be found with a dfs. We then do the following updates:

1. Add $$$s$$$ to $$$R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$$$. This can be done naively or with prefix sums.
2. Add $$$s$$$ to $$$C_{c_{min}-1},C_{c_{min}},\ldots,C_{c_{max}+1}$$$. This can be done naively or with prefix sums.
3. Add $$$s$$$ to the subrectangle of $$$B$$$ with top left at ($$$r_{min}-1,c_{min}-1$$$) and bottom right at ($$$r_{max}+1,c_{max}+1$$$). This can be done with 2D prefix sums. (Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions.)

We do this for each component. Also, calculating $$$F_{r,c}$$$ can be done by looking at the number of $$$\texttt{.}$$$ in row $$$r$$$, column $$$c$$$, and checking whether we overcounted a $$$\texttt{.}$$$ at ($$$r,c$$$). In all, this solution runs in $$$\mathcal{O}(nm)$$$ time.

#include <bits/stdc++.h>
using namespace std;

int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
vector<vector<int>> RC; vector<vector<bool>> vis; vector<vector<char>> A;

void dfs(int i, int j){
    if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
        return;
    
    vis[i][j] = true;

    sz++;
    minR = min(minR, i);
    maxR = max(maxR, i);
    minC = min(minC, j);
    maxC = max(maxC, j);

    dfs(i - 1, j);
    dfs(i + 1, j);
    dfs(i, j - 1);
    dfs(i, j + 1);
}

void solve(){
    cin >> n >> m;

    R.assign(n + 5, 0);
    C.assign(m + 5, 0);
    freeR.assign(n + 5, 0);
    freeC.assign(m + 5, 0);
    RC.assign(n + 5, vector<int>(m + 5, 0));
    vis.assign(n + 5, vector<bool>(m + 5, false));
    A.assign(n + 5, vector<char>(m + 5, ' '));

    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> A[i][j];

            if (A[i][j] == '.'){
                freeR[i]++;
                freeC[j]++;
            }
        }
    }
    
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (vis[i][j] or A[i][j] == '.')
                continue;

            // Reset
            sz = 0;
            minR = 1e9;
            maxR = -1e9;
            minC = 1e9;
            maxC = -1e9;

            dfs(i, j);

            // Expand by 1 since adjacent cells also connect
            minR = max(minR - 1, 1);
            maxR = min(maxR + 1, n);
            minC = max(minC - 1, 1);
            maxC = min(maxC + 1, m);
            
            // Update prefix sums
            R[minR] += sz;
            R[maxR + 1] -= sz;

            C[minC] += sz;
            C[maxC + 1] -= sz;

            RC[minR][minC] += sz;
            RC[maxR + 1][minC] -= sz;
            RC[minR][maxC + 1] -= sz;
            RC[maxR + 1][maxC + 1] += sz;
        }
    }

    for (int i = 1; i <= n; i++)
        R[i] += R[i - 1];

    for (int i = 1; i <= m; i++)
        C[i] += C[i - 1];

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            RC[i][j] += RC[i - 1][j] + RC[i][j - 1] - RC[i - 1][j - 1];
    
    ans = 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ans = max(ans, (R[i] + C[j] - RC[i][j]) + (freeR[i] + freeC[j] - (A[i][j] == '.')));
    
    cout << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Solve for $$$k = 1$$$.

Solve for $$$k = n$$$.

What other $$$k$$$ work for a given $$$n$$$?

Read the hints.

For $$$k=1$$$, the construction $$$1,2,3\dots n$$$ will always work because in any other cyclic shift, $$$n$$$ will be before $$$1$$$.

Now, consider what happens if we want to find an array with two or more cyclic shifts that are sorted. If we consider two of these cyclic shifts, notice they are actually shifts of each other as well.

So, there should be a sorted array, and a shift of it which is also sorted. What this means is that some of the first elements in the array move to the back and stays sorted, which can only happen if all values in the array are equal.

If the array has all equal values, this gives us our construction for $$$k=n$$$. As we have seen, for $$$k>1$$$, only $$$k=n$$$ is possible. Thus, for any other $$$k$$$ not equal to $$$1$$$ or $$$n$$$, we can print $$$-1$$$.

#include <iostream>
using namespace std;
int main(){
	int t; cin >> t;
	while(t--){
		int n, k; cin >> n >> k;
		if(k == 1) for(int i = 0; i < n; i++) cout << i + 1 << " ";
		else if(k == n) for(int i = 0; i < n; i++) cout << 1 << " ";
		else cout << -1;
		cout << "\n";
	}
}

We will construct the solution forward.

Separate the $$$a_i$$$'s given into negative and positive cases. What does this tell us about the $$$\texttt{MEX}$$$?

We can find $$$p_1, p_2, ... , p_n$$$ in order, looking at positive and negative cases. Note that $$$a_i \neq 0$$$ because $$$p_i$$$ would equal $$$\texttt{MEX}$$$($$$p_1 \dots p_i$$$), which can never happen.

• If $$$a_i > 0$$$, then $$$\texttt{MEX}$$$($$$p_1, p_2, ... p_i$$$) must increase from $$$\texttt{MEX}$$$($$$p_1, p_2, ... p_{i-1}$$$), so we know $$$p_i$$$ must equal $$$\texttt{MEX}$$$($$$p_1, p_2, ... p_{i-1}$$$).
• Otherwise, the $$$\texttt{MEX}$$$ stays the same, so $$$p_i$$$ is just simply $$$\texttt{MEX}$$$($$$p_1, p_2, ... p_{i-1}$$$) — $$$a_i$$$.

Thus, we can just maintain the $$$\texttt{MEX}$$$ and find each $$$p_i$$$ as we go forward.

Note that this is also a way to show $$$p$$$ is always unique.

#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n; cin >> n;
	vector<int> a(n);
	for(int& i: a) cin >> i;
	vector<int> p(n), has(n + 1);
	int mex = 0;
	for(int i = 0; i < n; i++){
		if(a[i] >= 0){
			p[i] = mex;
		}
		else{
			p[i] = mex - a[i];
		}
		has[p[i]] = true;
		while(has[mex]) mex++;
	}
	for(int i: p) cout << i << " ";
	cout << "\n";
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

We will construct the solution backwards.

The $$$\texttt{MEX}$$$ is determined at the last index, since all of $$$0, 1 \dots n-1$$$ appear in $$$p$$$.

Read the hints.

Since we know the $$$\texttt{MEX}$$$ of the last position is $$$n$$$, then $$$n - p_n = a_n$$$. From this equation, we can find that $$$p_n = n - a_n$$$.

Now, because we know $$$p_n$$$, we can determine the $$$\texttt{MEX}$$$ of the first $$$n-1$$$ numbers. Like how we found $$$p_n$$$, we can do a similar process for finding $$$p_{n-1}$$$. Doing this for $$$i = n, n - 1 \dots 1$$$ will get us a valid answer $$$p$$$.

Note that this is also a way to show $$$p$$$ is always unique.

Ignoring $$$n$$$ for now, let's just focus on the $$$x$$$ chosen vertices. Sort the $$$x$$$ vertices and connect adjacent vertices to form its own smaller polygon. By drawing out some cases or if you're familiar with triangulation (video that proves by induction), you can form $$$x - 2$$$ triangles by drawing diagonals in a polygon with $$$x$$$ vertices. If you don't know it, one possible construction that always work is fixing one vertex $$$v$$$ and drawing diagonals to every other vertex not adjacent to $$$v$$$. Now, let's consider the original $$$n$$$-sided polygon. In additional to the aforementioned construction, to close the $$$x$$$-sided polygon up: for every non-adjacent vertex in the chosen vertices based on the bigger $$$n$$$-sided polygon, draw a diagonal between them. Through this construction, we can always guarantee $$$x - 2$$$ triangles.

However, this doesn't account for all triangles, as some triangles can form sides with the bigger $$$n$$$-sided polygon. These triangles occur exactly when two adjacent vertex in $$$x$$$ have exactly one vertex not in $$$x$$$ between them but part of the bigger polygon. This is because one side is from the diagonals we drew, and the other two sides form from the $$$n$$$-sided polygon.

Therefore, the answer is $$$x - 2$$$ + (number of adjacent chosen vertices $$$2$$$ apart). Note that the first chosen vertex is also adjacent to last chosen vertex in $$$x$$$.

Read the solution to the easy version first.

We can now reduce the problem to the following: For every vertex we choose, we can make one more triangle. For every chosen vertices two apart, we can make one more triangle. Let's focus on the latter condition. To maximize the effect of our $$$y$$$ vertices, we want to prioritize vertices $$$v$$$ that satisfy the following: the vertex is not included in $$$x$$$ and there is a chosen vertex two apart. Let's denote such $$$v$$$ as good.

Let vertex $$$a$$$ and $$$b$$$ $$$(a < b)$$$ be adjacent chosen vertices in the $$$x$$$-sided polygon. There are $$$g = b - a - 1$$$ vertices for us to choose between them. There are two cases: if $$$g$$$ is odd, then we can choose $$$\lfloor \frac{g}{2} \rfloor$$$ vertices to form $$$\lfloor \frac{g}{2}\rfloor + 1$$$ extra triangles. This is because all of the vertices we choose will be good. if $$$g$$$ is even, then we can choose $$$\frac{g}{2}$$$ vertices to make $$$\frac{g}{2}$$$ extra triangles. This is because one of the vertices we choose will not be good. This shows that it is always optimal to process smaller and odd $$$g$$$ first.

After processing these adjacent gaps, if we have any leftover vertices, we can just ignore them. This is because since we have maximized the number of good vertices, even though any further vertex we place will increase the answer by $$$1$$$, it will break two good vertices which will decrease the answer by $$$1$$$.

#include <bits/stdc++.h>
using namespace std;

void solve(){
	int n, x, y; cin >> n >> x >> y;
	int initial_y = y;
	vector<int> chosen(x);
	for(int& i: chosen) cin >> i;
	sort(chosen.begin(), chosen.end());
	int ans = x - 2;
	int triangles_from_even_g = 0;
	vector<int> odd_g;
	auto process_gap = [&](int g) -> void{
		if(g <= 1){
			// already two apart
			ans += g;
		}
		else if(g % 2 == 1){
			odd_g.push_back(g / 2);
		}
		else{
			triangles_from_even_g += g / 2;
		}
	};
	for(int i = 0; i < x - 1; i++){
		process_gap(chosen[i + 1] - chosen[i] - 1);
	}
	process_gap((chosen[0] + n) - chosen[x - 1] - 1);
	sort(odd_g.begin(), odd_g.end());
	for(int g: odd_g){
		if(y >= g){
			// all vertices are good, so we can make g + 1 triangles
			ans += g + 1;
			y -= g;
		}
		else{
			ans += y;
			y = 0;
			break;
		}
	}
	int even_triangles = min(triangles_from_even_g, y);
	y -= even_triangles;
	ans += even_triangles;
	int used_vertices = initial_y - y;
	ans += used_vertices;
	cout << ans << "\n";
}

int main(){
	cin.tie(0) -> sync_with_stdio(0);
	int T = 1;
	cin >> T;
	while(T--) solve();
}

/*   /\_/\
*   (= ._.)
*   / >  \>
*/

We can solve this with dynamic programming. Let $$$\texttt{dp}[i]$$$ store a list of all $$$\min(k, 2^i)$$$ highest beauties of a painting in non-increasing order if you only paint cells $$$1,2,\ldots ,i$$$.

Transitioning boils down to finding the $$$k$$$ largest elements from $$$n$$$ non-increasing lists. Try to do this in $$$\mathcal{O}((n + k) \log n)$$$ time.

Let $$$\texttt{dp}[i]$$$ store a list of all $$$\min(k, 2^i)$$$ highest beauties of a painting in non-increasing order if you only paint cells $$$1,2,\ldots ,i$$$.

Let's define merging two lists as creating a new list that stores the $$$k$$$ highest values from the two lists.

First, let's look at a slow method of transitioning. We iterate over the left endpoint $$$l$$$ such that $$$l \ldots i$$$ is a maximal painted interval. At each $$$l$$$, we merge $$$\texttt{dp}[l - 2]$$$, with $$$a_{l,i}$$$ added to each value, into $$$\texttt{dp}[i]$$$. We also merge $$$\texttt{dp}[i - 1]$$$ into $$$\texttt{dp}[i]$$$ to handle the case in which we do not paint cell $$$i$$$. If implemented well, transitioning takes $$$\mathcal{O}(nk)$$$ time leading to an $$$\mathcal{O}(n^2k)$$$ solution which is too slow.

We can speed this up. This merging process boils down to finding the $$$k$$$ largest elements from $$$n$$$ non-increasing lists in $$$\mathcal{O}((n + k) \log n)$$$ time. We can use a priority queue that stores ($$$\texttt{element}, \texttt{index}$$$) for each list. We can do the following $$$k$$$ times: add the top of the priority queue to our answer, advance its index, and update the priority queue accordingly. This allows us to transition in $$$\mathcal{O}((n + k) \log n)$$$ time which leads to an $$$\mathcal{O}((n^2 + nk) \log n)$$$ solution.

Bonus: find an $$$\mathcal{O}(n^2 + k)$$$ solution.

#include <bits/stdc++.h>
using namespace std;
 
void solve(){
    int n, k;
    cin >> n >> k;
 
    int A[n + 1][n + 1];
 
    for (int i = 1; i <= n; i++)
        for (int j = i; j <= n; j++)
            cin >> A[i][j];
    
    // dp[i] = Answer if we consider 1...i
    vector<int> dp[n + 1];
    dp[0] = {0};
 
    for (int i = 1; i <= n; i++){
        priority_queue<array<int, 3>> pq;
 
        // Don't create an interval
        pq.push({dp[i - 1][0], i - 1, 0});
 
        // Create interval j+2...i (transition from j)
        for (int j = i - 2; j >= -1; j--){
            pq.push({(j < 0 ? 0 : dp[j][0]) + A[j + 2][i], j, 0});
        }
 
        while (pq.size() and dp[i].size() < k){
            auto [val, j, num] = pq.top(); pq.pop();
            dp[i].push_back(val);
            
            if (j < 0 or num + 1 >= dp[j].size())
                continue;
            
            // Don't create interval
            if (j == i - 1)
                pq.push({dp[i - 1][num + 1], i - 1, num + 1});
            
            // Create interval j+2...i (transition from j)
            else 
                pq.push({dp[j][num + 1] + A[j + 2][i], j, num + 1});
        }
    }
    for (int i : dp[n])
        cout << i << " ";
    cout << "\n";
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); 
    int tc; 
    cin >> tc;
 
    while (tc--) 
        solve();
}

Think about the gaps between $$$(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$$$. Let the gaps be $$$g_1,g_2,...,g_n$$$. What effect do the moves have on the gaps?

WLOG let the first cow be FJ's cow. FN wins if all $$$g_i$$$ are even. Otherwise FJ wins. Note that the game will always end.

Try to count the number of ways FN wins. We can iterate over the sum of $$$g_i$$$ and use stars and bars as well as other counting techniques.

Consider the gaps between $$$(a_1,b_1), (a_2,b_2), ... ,(a_n,b_n)$$$. In the example below, '$$$\texttt{a}$$$' represents FJ's cow, '$$$\texttt{b}$$$' represents FN's cow, and '$$$\texttt{.}$$$' represents an empty space. The gaps are $$$[2,3]$$$.

Consider the gaps $$$g_1,g_2,...,g_n$$$. When a farmer moves, they choose some non-empty subset of non-zero $$$g_i$$$ and add or subtract $$$1$$$ from every element in the subset (so long such move is possible). The game ends when some farmer cannot move (which implies that all $$$g_i$$$ must be $$$0$$$ when the game ends).

WLOG let the first cow be FJ's cow. The winner of the game is determined as follows:

1) If all $$$g_i$$$ are even, then FN wins. If FJ pushes the cows corresponding to gaps $$$i_1, i_2, \ldots, i_k$$$ some direction in a move, then $$$g_{i_1}, g_{i_2}, \ldots g_{i_k}$$$ will change by $$$1$$$ and become odd. FN can then push the cows corresponding to gaps $$$i_1, i_2, \ldots, i_k$$$ left so that $$$g_{i_1}, g_{i_2}, \ldots g_{i_k}$$$ will become even again. Therefore, all $$$g_i$$$ will be even when it's FJ's turn and at least one $$$g_i$$$ will be odd when it's FN's turn. Since the game ends when all $$$g_i$$$ are $$$0$$$ (which is even), then FJ will lose. Note that the game will always end. This is since the sum of positions of FN's cows will always be decreasing since FN will always push some cow left.

2) Otherwise, FJ wins since he can subtract $$$1$$$ to all odd $$$g_i$$$ in his first move to make all elements even. Then it's FN's turn and all $$$g_i$$$ are even so by the reasoning above, FJ wins.

Let's use complementary counting and determine the number of ways FN wins (which is when all $$$g_i$$$ are even). We can iterate over the sum, $$$s$$$ ($$$s$$$ is even), of all $$$g_i$$$. At each $$$s$$$, we can use stars and bars to find how many such $$$g_1,g_2,...,g_n$$$ (all $$$g_i$$$ are even) sum to $$$s$$$. Specifically, the number of ways are $$$\frac{s}{2} + n - 1 \choose n - 1$$$. The number of ways to place the cows in the available positions given the gaps will be $$$2 \cdot {l - s - n \choose n}$$$. We multiply by $$$2$$$ since we can alternate starting with either FJ's cow or FN's cow.

Finally, we subtract this result from the total number of configurations, $$$2 \cdot {l \choose 2 \cdot n}$$$, to get the number of ways FJ wins. This runs in $$$\mathcal{O}(l)$$$ time.

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MAX = 2e6 + 5, MOD = 998244353;

ll fact[MAX], ifact[MAX];

ll bpow(ll a, int p){
    ll ans = 1;

    for (;p; p /= 2, a = (a * a) % MOD) 
        if (p & 1) 
            ans = (ans * a) % MOD;

    return ans;
}
ll ncr(int n, int r){
    if (n < 0)
        return 0;
    if (r > n)
        return 0;

    return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}
void solve(){
    int l, n;
    cin >> l >> n;
 
    ll all_even = 0;
 
    for (int s = 0; s <= l; s += 2){
        all_even += 2 * ncr(s / 2 + n - 1, n - 1) % MOD * ncr(l - s - n, n) % MOD;
        all_even %= MOD;
    }
    cout << (2 * ncr(l, 2 * n) % MOD - all_even + MOD) % MOD << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    for (int i = 0; i < MAX; i++)
        fact[i] = !i ? 1 : fact[i - 1] * i % MOD;
    
    for (int i = MAX - 1; i >= 0; i--)
        ifact[i] = (i == MAX - 1) ? bpow(fact[MAX - 1], MOD - 2) : ifact[i + 1] * (i + 1) % MOD;

    int tc;
    cin >> tc;

    while (tc--)
        solve();
}

Consider the case where all $$$f(i)$$$ are integers. Decreasing any $$$a_i$$$ will decrease $$$\lfloor f(n) \rfloor$$$. So solutions that iterate over the last few elements will not work.

If $$$n \ge 6$$$, changing $$$a_1$$$ will only affect $$$\lfloor f(n) \rfloor$$$ by at most $$$1$$$.

We can take the floor each time we square root. Specifically, we can define $$$f$$$ as:

• $$$f(1) = \lfloor \sqrt{a_1} \rfloor$$$
• For all $$$i > 1$$$, $$$f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$$$

This allows us to work with integers.

We can divide our array into blocks of size $$$b \ge 6$$$ (note that the value of $$$b$$$ depends on the solution). How can we use hint $$$2$$$? What should we store for each block?

Let's first look at the impact of earlier numbers on the final result. Earlier numbers can still influence $$$\lfloor f(n) \rfloor$$$ when $$$n$$$ is large. Suppose that all $$$f(i)$$$ are integers. Then decreasing any $$$a_i$$$ will decrease $$$\lfloor f(n) \rfloor$$$.

However, it is clear that the impact of earlier number on $$$\lfloor f(n) \rfloor$$$ is still extremely small. A key observation is that when $$$n \ge 6$$$, changing $$$a_1$$$ will only affect $$$\lfloor f(n) \rfloor$$$ by at most $$$1$$$.

Another observation is that we can take the floor each time we square root. Specifically, we can define $$$f$$$ as:

• $$$f(1) = \lfloor \sqrt{a_1} \rfloor$$$
• For all $$$i > 1$$$, $$$f(i) = \lfloor \sqrt{f(i-1)+a_i} \rfloor$$$

This allows us to work with integers. From here on, we work with this new definition of $$$f$$$.

Let's divide our array into blocks of size $$$b=6$$$. We can append zeroes to the front of the array to make $$$n$$$ a multiple of $$$b$$$.

Consider some block representing range $$$[l,r]$$$. Let's consider the subarray $$$a_l,a_{l+1},\ldots ,a_r$$$. Let $$$v$$$ be the value of $$$f(r)$$$ if we let $$$f(l - 1)=0$$$. Using our first observation, we know that $$$f(r)$$$ will be either $$$v$$$ or $$$v+1$$$ depending on $$$f(l - 1)$$$. So let's find the smallest value $$$c$$$ such that if $$$f(l - 1)=c$$$, then $$$f(r)=v+1$$$. This can be done by iterating over the elements of the block backwards.

For each block, we store its corresponding ($$$v,c$$$). We can build a segment tree over the blocks for an $$$\mathcal{O}((n + q) \log n)$$$ solution.

Alternatively, we can do square root decomposition by having $$$b=\sqrt n$$$ which leads to an $$$\mathcal{O}(n + q \sqrt n)$$$ solution (in practice, we should set $$$b$$$ to something small like $$$100$$$).

"Draw $$$1$$$" cards do not matter because we can immediately play them when we draw them.

Treat "draw $$$2$$$" as $$$+1$$$ and "draw $$$0$$$" as $$$-1$$$. We start with a balance of $$$+5$$$. We draw all the cards up to the first prefix where the balance dips to $$$0$$$. We are interested in the number of ways where the special cards lie in this prefix.

Read the hints.

Treat the special cards as "draw $$$0$$$" cards and multiply by the appropriate binomial coefficient at the end. Also treat cards of the same type as indistinguishable and multiply by the appropriate factorials at the end.

Enumerate the length of the prefix where the balance first hits $$$0$$$. This dictates how many $$$+1$$$ and $$$-1$$$ we have. Now we want to count the number of ways of arranging $$$+1$$$ and $$$-1$$$ such that the balance never dips to $$$0$$$, assuming we start with $$$+5$$$.

To solve this subproblem, we can draw inspiration from the path counting interpretation for counting balanced bracket sequences. We have $$$n$$$ open and $$$n$$$ close brackets and want to count the number of balanced bracket sequences starting with (((( (note that there are only $$$4$$$ instead of $$$5$$$ open brackets to shift from all balances being strictly positive to all balances being non-negative). The number of sequences ignoring the balance constraint is $$$\binom{2n-4}{n}$$$. Any bracket sequence where some balance dips negative corresponds to a path that walks above the line $$$y = x$$$. For those paths, we reflect over the line $$$y = x + 1$$$ at the first point where it steps over the line. So there is a bijection between these paths and paths that reach the point $$$(n-1,n+1)$$$, of which there are $$$\binom{2n-4}{n+1}$$$. So the total number of ways is $$$\binom{2n-4}{n} - \binom{2n-4}{n+1}$$$.

Our final answer is summing up the number of ways over all prefix lengths. Make sure to handle the case where you draw the entire deck correctly. The complexity is $$$\mathcal O(\min(a,c))$$$.

Model this as a flow problem where growth events are an input of some flow to a node and harvest events and the necessary amount of fruits are an output of flow to the sink. We will define the $$$a_i$$$ edge to be the input edge of every node, $$$b_i$$$ to be the output edge for necessary fruits, and $$$c_i$$$ to be the output edge for growth events. The connections for each individual node will look like:

$$$(\text{source}, a_i, \text{# of growth events})$$$

$$$(a_i, \text{temporary node}, \text{INF})$$$

$$$(\text{temporary node}, b_i, \text{INF})$$$

$$$(\text{temporary node}, c_i, \text{INF})$$$

$$$(b_i, \text{sink}, \text{# of required peaches})$$$

$$$(c_i, \text{sink}, \text{# of harvest events})$$$

To simulate growth events affecting the subtree, every temporary node has infinite capacity directed edges down to the temporary nodes of its children. To simulate growth events affecting the parent, every temporary node has an infinite capacity directed edge to its parent's $$$b_i$$$. To simulate harvest events affecting subtree, every node has infinite capacity directed edges to all its ancestors' $$$c_i$$$ nodes. Lets try to find the min cut of the graph. If we don't put cut some node's $$$a_i$$$, then we must cut both $$$b_i$$$ and $$$c_i$$$ for all of its descendants. If we don't cut some node's $$$a_i$$$, then we also must cut $$$c_i$$$ for all its ancestors and $$$b_i$$$ for its parent. Thus, we can model a $$$dp[i][0/1/2]$$$ to know if we are currently cutting the a_i input edge, cutting the b_i and c_i output edge, or cutting the a_i edge but there is some node in the subtree where we did not cut the a_i edge, in which case we need to cut the c_i edge as well. Transitions look like:

$$$dp[i][0] = a_i + \sum_j dp[j][0]$$$

$$$dp[i][1] = b_i + c_i + \sum_j dp[j][1]$$$

$$$dp[i][2] = a_i + c_i + \min(\sum_j \min(dp[j][0], dp[j][2]), b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2]))$$$ where at least one child is a $$$dp[j][2]$$$ or $$$dp[j][1]$$$

$$$dp[i][2]$$$ can be rewritten as:

$$$dp[i][2] = a_i + c_i + \min(\min(dp[j][2] - \min(dp[j][0], dp[j][2])) + \sum_j \min(dp[j][0], dp[j][2]),$$$ $$$\min(dp[j][1] - \min(dp[j][0], dp[j][1], dp[j][2])) + b_i + \sum_j \min(dp[j][0], dp[j][1], dp[j][2])))$$$

Use dynamic dp by representing dp transitions as a matrix where all the light children dp values are known and the heavy child dp values are variable. Then, we can accelerate each chain in the heavy light decomposition of the tree. To get the matrix representation of each transition to the heavy child, there are 5 cases when considering a $$$dp[j][0/1/2]$$$ -> $$$dp[j][2]$$$ transiton where $$$dp[j][0]$$$ is the min, $$$dp[j][1]$$$ is the min, and $$$dp[j][2]$$$ is the min, $$$dp[j][2] - \min(dp[j][0], dp[j][2])$$$ is the optimal added value, or $$$dp[j][0] - min(dp[j][0], dp[j][1], dp[j][2])$$$, is the optimal added value. For each cell in the matrix, put the min of the $$$5$$$ cases.

Since you will only ever change hld chains $$$\log n$$$ times, the total complexity will be $$$n \log^2 n \cdot 3^3$$$. If we use balanced hld or other $$$n \log n$$$ hld techniques, then the complexity becomes $$$n \log^2 n$$$. Both solutions should pass under the given constraints.

    #ifndef LOCAL
    #pragma GCC optimize("O3,unroll-loops")
    #pragma GCC target("avx,avx2,fma")
    #pragma GCC target("sse4,popcnt,abm,mmx,tune=native")
    #endif
    #include <bits/stdc++.h>
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    using namespace __gnu_pbds;
    using namespace std;
    
    #define pb push_back
    #define ff first
    #define ss second
    
    typedef long long ll;
    typedef long double ld;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    typedef pair<ld, ld> pld;
    
    const int INF = 1e9;
    const ll LLINF = 1e18;
    const int MOD = 1e9 + 7;
    
    template<class K> using sset =  tree<K, null_type, less<K>, rb_tree_tag, tree_order_statistics_node_update>;
    
    inline ll ceil0(ll a, ll b) {
        return a / b + ((a ^ b) > 0 && a % b);
    }
    
    void setIO() {
        ios_base::sync_with_stdio(0); cin.tie(0);
    }
    
    struct Matrix {
    
        array<array<ll, 3>, 3> mat;
    
        array<ll, 3> &operator[](int x){
            return mat[x];
        }
    
        const array<ll, 3> &operator[](int x) const {
            return mat[x];
        }
    
        Matrix(){
            for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) mat[i][j] = 0;
        }
    
        Matrix operator*(const Matrix &x){
            Matrix ret;
            for(int i = 0; i < 3; i++) for(int j = 0; j < 3; j++) ret[i][j] = LLINF;
            for(int i = 0; i < 3; i++){
                for(int k = 0; k < 3; k++){
                    for(int j = 0; j < 3; j++){
                        ret[i][j] = min(ret[i][j], mat[i][k] + x[k][j]);
                    }
                }
            }
            return ret;
        }
    
        Matrix &operator*=(const Matrix &x){
            (*this) = (*this) * x;
            return *this;
        }
    };
    
    struct fastset {
    
        priority_queue<ll, vector<ll>, greater<ll>> q, rem;
    
        void insert(ll x){
            q.push(x);
        }
    
        void erase(ll x){
            rem.push(x);
        }
    
        ll query(){
            while(rem.size() && q.top() == rem.top()){
                rem.pop();
                q.pop();
            }
            return q.top();
        }
    
        void clear(){
            while(q.size()) q.pop();
            while(rem.size()) rem.pop();
        }
    };
    
    vector<int> g[500005];
    int sub[500005];
    int head[500005];
    int par[500005];
    int tim = 0;
    vector<int> chain[500005];
    int weight[500005];
    
    void dfs1(int x){
        sub[x] = 1;
        for(int &i : g[x]){
            dfs1(i);
            sub[x] += sub[i];
            if(sub[i] > sub[g[x][0]]) swap(i, g[x][0]);
        }
    }
    
    int in[500005], out[500005];
    int dir[500005];
    
    void dfs2(int x, int p){
        chain[head[x]].pb(x);
        par[x] = p;
        weight[x] = 1;
        in[x] = tim++;
        for(int i : g[x]){
            head[i] = (i == g[x][0] ? head[x] : i);
            dfs2(i, x);
            if(i != g[x][0]) weight[x] += sub[i];
        }
        out[x] = tim - 1;
    }
    
    Matrix dp[500005]; 
    Matrix cum[500005];
    int rt[500005];
    int left0[500005], right0[500005], ppar[500005];
    
    int dnq(int l, int r, int p, const vector<int> &v){
        if(l > r) return 0;
        int sum = 0;
        for(int i = l; i <= r; i++) sum += weight[v[i]];
        int cur = 0;
        int mid = -1;
        for(int i = l; i <= r; i++){
            cur += weight[v[i]];
            if(cur >= sum/2){
                mid = i;
                break;
            }
        }
        if(p == -1) ppar[v[mid]] = v[mid];
        else ppar[v[mid]] = p;
        left0[v[mid]] = dnq(l, mid - 1, v[mid], v);
        right0[v[mid]] = dnq(mid + 1, r, v[mid], v);
        return v[mid];
    }
    
    void merge(int x){
        if(right0[x] && left0[x]){
            cum[x] = cum[left0[x]]*dp[x]*cum[right0[x]];
        } else if(left0[x] && !right0[x]){
            cum[x] = cum[left0[x]]*dp[x];
        } else if(right0[x] && !left0[x]){
            cum[x] = dp[x]*cum[right0[x]];
        } else {
            cum[x] = dp[x];
        }
    }
    
    void pull(int x){
        while(x != rt[x]){
            merge(x); 
            x = ppar[x];
        }
        merge(x);
    }
    
    ll a[500005], b[500005], c[500005];
    ll dp0[500005][3];
    
    void dfs3(int x){
        dp0[x][0] = a[x];
        dp0[x][2] = b[x] + c[x];
        ll deg1 = a[x] + c[x], deg2 = b[x] + a[x] + c[x];
        ll mn1 = LLINF, mn2 = LLINF;
        for(int i : g[x]){
            dfs3(i);
            dp0[x][0] += dp0[i][0];
            dp0[x][2] += dp0[i][2];
            deg1 += min(dp0[i][0], dp0[i][1]);
            deg2 += min({dp0[i][0], dp0[i][1], dp0[i][2]});
            mn1 = min(mn1, max((ll)0, dp0[i][1] - dp0[i][0]));
            mn2 = min(mn2, max((ll)0, min(dp0[i][1], dp0[i][2]) - dp0[i][0]));
        }
        dp0[x][1] = min(deg1 + mn1, deg2 + mn2);
    }
    
    fastset deg1[500005], deg2[500005];
    ll sum0[500005], sum2[500005], sum01[500005], sum012[500005];
    
    void rebuild(int x){
        dp[x][0][0] = a[x] + sum0[x];
        dp[x][0][1] = LLINF;
        dp[x][0][2] = LLINF;
        if(g[x].size()){
            dp[x][1][0] = min(a[x] + b[x] + c[x] + deg2[x].query() + sum012[x], a[x] + c[x] + deg1[x].query() + sum01[x]);
            dp[x][1][1] = min(a[x] + c[x] + sum01[x], a[x] + b[x] + c[x] + sum012[x]);
            dp[x][1][2] = a[x] + b[x] + c[x] + sum012[x];
        } else {
            dp[x][1][0] = dp[x][1][1] = dp[x][1][2] = LLINF;
        }
        dp[x][2][0] = LLINF;
        dp[x][2][1] = LLINF;
        dp[x][2][2] = b[x] + c[x] + sum2[x];
    }
    
    ll eval(int x, int ind){
        return min({cum[rt[x]][ind][0], cum[rt[x]][ind][1], cum[rt[x]][ind][2]});
    }
    
    void rem(int x){
        while(head[x] != 1){
            if(x == head[x]){
                ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2);
                deg1[par[x]].erase(max((ll)0, v1 - v0));
                deg2[par[x]].erase(max((ll)0, min(v1, v2) - v0));
                sum012[par[x]] -= min({v0, v1, v2});
                sum01[par[x]] -= min(v0, v1);
                sum0[par[x]] -= v0;
                sum2[par[x]] -= v2;
                x = par[x];
            }
            x = head[x];
        }
    }
    
    void add(int x){
        while(head[x] != 1){
            if(x == head[x]){
                ll v0 = eval(x, 0), v1 = eval(x, 1), v2 = eval(x, 2);
                deg1[par[x]].insert(max((ll)0, v1 - v0));
                deg2[par[x]].insert(max((ll)0, min(v1, v2) - v0));
                sum012[par[x]] += min({v0, v1, v2});
                sum01[par[x]] += min(v0, v1);
                sum0[par[x]] += v0;
                sum2[par[x]] += v2;
                rebuild(par[x]);
                pull(par[x]);
                x = par[x];
            }
            x = head[x];
        }
    }
    
    int main(){
        setIO();
        int t;
        cin >> t;
        while(t--){
            int n, q;
            cin >> n >> q;
            for(int i = 2; i <= n; i++){
                int x;
                cin >> x;
                g[x].pb(i);
            }
            ll sum = 0;
            for(int i = 1; i <= n; i++) cin >> b[i], sum += b[i];
            dfs1(1);
            head[1] = 1;
            dfs2(1, 1);
            dfs3(1);
            for(int i = 1; i <= n; i++){
                if(chain[i].size()){
                    int p = dnq(0, chain[i].size() - 1, -1, chain[i]);
                    for(int j : chain[i]) rt[j] = p;
                }
            }
            for(int i = 1; i <= n; i++){
                deg1[i].insert(LLINF);
                deg2[i].insert(LLINF);
                for(int j : g[i]){
                    if(head[j] == head[i]) continue;
                    deg1[i].insert(max((ll)0, dp0[j][1] - dp0[j][0]));
                    deg2[i].insert(max((ll)0, min(dp0[j][1], dp0[j][2]) - dp0[j][0]));
                    sum012[i] += min({dp0[j][0], dp0[j][1], dp0[j][2]});
                    sum01[i] += min(dp0[j][0], dp0[j][1]);
                    sum0[i] += dp0[j][0];
                    sum2[i] += dp0[j][2];
                }
                rebuild(i);
                pull(i);
            } 
            while(q--){
                int t, x, v;
                cin >> t >> x >> v;
                rem(x);
                if(t == 1) a[x] += v;
                else c[x] += v, sum += v;
                rebuild(x);
                pull(x);
                add(x);
                cout << (min({eval(1, 0), eval(1, 1), eval(1, 2)}) == sum ? "YES" : "NO") << "\n";
            }
            tim = 0;
            for(int i = 1; i <= n; i++){
                a[i] = b[i] = c[i] = 0;
                g[i].clear();
                chain[i].clear();
                deg1[i].clear();
                deg2[i].clear();
                sum0[i] = sum2[i] = sum01[i] = sum012[i] = 0;
            }
        }
    }

There also exists a solution without flows. Thanks to rainboy for discovering it during testing!

Lets greedily assign the growth events. We will always try to use the growth events to satisfy harvest events or required peaches in its subtree, and if there is any excess then we give it to the parent's required peaches. Similarly, we will always use harvest events on growth events in its subtree. Lets define a $$$dp[u]$$$ for each node $$$u$$$. If $$$dp[x] > 0$$$ then it means we can give $$$dp[u]$$$ growths to $$$u$$$'s parent. Otherwise, it means $$$dp[u]$$$ requires $$$-dp[u]$$$ growths from its ancestors. Let $$$pos_u$$$ denote the sum of positive $$$dp[v]$$$ where $$$v$$$ is a child a of $$$u$$$, and $$$neg_u$$$ denote the sum of negative $$$dp[v]$$$. First we used the excess growth to satisfy the required peaches, so we can set $$$b_u = \max(0, b_u - pos_u)$$$. Then we distribute the growth events at node $$$u$$$ to satisfy the requirements in the subtree. Define $$$a_i$$$ as the number of growth events on node $$$i$$$ and $$$c_i$$$ as the number of harvest events on node $$$i$$$. To account for the harvest events at node $$$i$$$, we can define $$$bal_u = \text{sum of } a_i \text{ in u's subtree} - \text{sum of } b_i \text{ in u's subtree} - \text{sum of } c_i \text{ in u's subtree}$$$. We know that $$$dp[u] \le bal_u$$$, and as it turns out, as long as we keep $$$bal_u$$$ as an upper bound on $$$dp[u]$$$, the harvest events will always be satisfied. Why? $$$a_u + neg_u - \max(0, b_u - pos_u)$$$ is the assignment of growth events without considering harvest events. The amount of unused growth events in the subtree of $$$u$$$ is given by $$$bal_u - (a_u + neg_u - \max(0, b_u - pos_u)) + c_u$$$. If $$$a_u + neg_u - \max(0, b_u - pos_u) \le bal_u$$$, then it means we can use all of our harvest events on unused growth events in the subtree. If $$$a_u + neg_u - \max(0, b_u - pos_u) > bal_u$$$, then it means we will use all of our harvest events but still have $$$bal_u - (a_u + neg_u - \max(0, b_u - pos_u))$$$ harvest events remaining. Thus, we can formulate our dp as $$$dp[u] = \min(a_u + neg_u - \max(0, b_u - pos_u), bal_u)$$$. Let $$$v$$$ be the heavy child of $$$u$$$ and $$$pos'_u$$$ be the sum of positive dp excluding $$$v$$$ and $$$neg'_u$$$ be the sum of positive dp excluding $$$v$$$. Then, we can rewrite our dp as $$$dp[u] = \min(dp[v] + a_u + neg'_u - \max(0, b_u - pos'_u), a_u + neg'_u, bal_u)$$$. Define $$$x_u = a_u + neg'_u - \max(0, b_u - pos'_u)$$$ and $$$y_u = a_u + neg'_u$$$. Then $$$dp[u] = \min(dp[v] + x_u, y_u, bal_u)$$$. This can be accelerated by representing the transition as a matrix and accelerating it using dynamic dp. However, we can also notice that the dp can be represented as the smallest $$$x_1 + x_2 + \ldots + x_{i - 1} + \min(y_i, bal_i)$$$ over all prefixes of each heavy light decomposition chain. Thus, we can maintain the dp by using a range add and prefix min segment tree.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	300000
#define N_	(1 << 19)	/* N_ = pow2(ceil(log2(N))) */
#define INF	0x3f3f3f3f3f3f3f3fLL

long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }

int *ej[N], eo[N], n;

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int dd[N], pp[N], qq[N], jj[N], ta[N], tb[N], qu[N];
int bb[N]; long long aa[N], zz[N], zzp[N], zzn[N];

int dfs1(int i, int d) {
	int o, s, k_, j_;

	dd[i] = d;
	s = 1, k_ = 0, j_ = -1;
	zz[i] = -bb[i];
	for (o = eo[i]; o--; ) {
		int j = ej[i][o], k = dfs1(j, d + 1);

		s += k;
		if (k_ < k)
			k_ = k, j_ = j;
		zz[i] += zz[j];
	}
	qq[i] = j_, jj[i] = j_ == -1 ? i : jj[j_];
	return s;
}

int t_;

void dfs2(int i, int q) {
	int o, j_;

	qu[ta[i] = t_++] = i;
	j_ = qq[i], qq[i] = q;
	if (j_ != -1)
		dfs2(j_, q);
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != j_)
			dfs2(j, j);
	}
	tb[i] = t_;
}

long long stx[N_ * 2], sty[N_ * 2], stz[N_ * 2], lz[N_]; int h_, n_;

void put(int i, long long x) {
	stz[i] += x;
	if (i < n_)
		lz[i] += x;
}

void pus(int i) {
	if (lz[i])
		put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}

void pul(int i) {
	if (!lz[i]) {
		int l = i << 1, r = l | 1;

		stx[i] = stx[l] + stx[r];
		sty[i] = min(sty[l], stx[l] + sty[r]);
		stz[i] = min(stz[l], stx[l] + stz[r]);
	}
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build() {
	int i, j, a, o;
        h_ = 0;

	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	memset(stx, 0, n_ * 2 * sizeof *stx);
	memset(sty, 0, n_ * 2 * sizeof *sty);
	memset(stz, 0, n_ * 2 * sizeof *stz);
	memset(lz, 0, n_ * sizeof *lz);
	memset(aa, 0, n * sizeof *aa);
	memset(zzp, 0, n * sizeof *zzp);
	memset(zzn, 0, n * sizeof *zzn);
	for (i = 0; i < n; i++) {
		a = ta[i];
		stz[n_ + a] = zz[i];
		for (o = eo[i]; o--; ) {
			j = ej[i][o];
			if (qq[j] == j)
				zzn[i] += -zz[j];
		}
		stx[n_ + a] = -zzn[i] - bb[i];
		sty[n_ + a] = -zzn[i];
	}
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

void upd(int i) {
	int i_ = n_ + ta[i];

	push(i_);
	stx[i_] = aa[i] - zzn[i] - max(bb[i] - zzp[i], 0);
	sty[i_] = aa[i] - zzn[i];
	pull(i_);
}

void update_z(int l, int r, long long x) {
	int l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++, x);
		if ((r & 1) == 0)
			put(r--, x);
	}
	pull(l_), pull(r_);
}

long long query(int l, int r) {
	long long xl, yl, zl, xr, yr, zr;

	push(l += n_), push(r += n_);
	xl = 0, yl = INF, zl = INF, xr = 0, yr = INF, zr = INF;
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1) {
			yl = min(yl, xl + sty[l]), zl = min(zl, xl + stz[l]), xl += stx[l];
			l++;
		}
		if ((r & 1) == 0) {
			yr = min(sty[r], yr == INF ? INF : stx[r] + yr), zr = min(stz[r], zr == INF ? INF : stx[r] + zr), xr += stx[r];
			r--;
		}
	}
	return min(min(xl + xr, min(yl, yr == INF ? INF : xl + yr)), min(zl, zr == INF ? INF : xl + zr));
}

int main() {
	int t;

	scanf("%d", &t);
	while (t--) {
		int q_, i, p, q;

		scanf("%d%d", &n, &q_);
		for (i = 0; i < n; i++)
			ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
		pp[0] = -1;
		for (i = 1; i < n; i++) {
			scanf("%d", &pp[i]), pp[i]--;
			append(pp[i], i);
		}
		for (i = 0; i < n; i++)
			scanf("%d", &bb[i]);
		dfs1(0, 0);
		t_ = 0, dfs2(0, 0);
		build();
		while (q_--) {
			int t, x;

			scanf("%d%d%d", &t, &i, &x), i--;
			if (t == 2)
				x = -x;
			if (t == 1)
				aa[i] += x, upd(i);
			while (i >= 0) {
				q = qq[i], p = pp[q];
				if (p >= 0) {
					if (zz[q] > 0)
						zzp[p] -= zz[q];
					else
						zzn[p] -= -zz[q];
				}
				update_z(ta[q], ta[i], x);
				zz[q] = query(ta[q], ta[jj[q]]);
				if (p >= 0) {
					if (zz[q] > 0)
						zzp[p] += zz[q];
					else
						zzn[p] += -zz[q];
					upd(p);
				}
				i = p;
			}
			printf(zz[0] >= 0 ? "YES\n" : "NO\n");
		}
		for (i = 0; i < n; i++)
			free(ej[i]);
	}
	return 0;
}

This round was mostly made possible by problemsetters from the CerealCodes initiative!

CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest here.

To make $$$a$$$ not sorted, we just need to pick one index $$$i$$$ so $$$a_i > a_{i + 1}$$$. How do we do this?

To make $$$a$$$ not sorted, we just have to make $$$a_i > a_{i + 1}$$$ for one $$$i$$$.

In one operation, we can reduce the gap between two adjacent elements $$$i, i + 1$$$ by $$$2$$$ by adding $$$1$$$ to $$$1 \dots i$$$ and subtracting $$$1$$$ from $$${i + 1} \dots n$$$.

It is clearly optimal to pick the smallest gap between a pair of adjacent elements to minimize the number of operations we have to do. If we have $$$a_i = x, a_{i + 1} = y$$$, we can make $$$x > y$$$ within $$$\lfloor \frac{(y - x)}{2} \rfloor + 1$$$ operations.

Thus, we can just go through $$$a$$$, find the minimum difference gap, and calculate the minimum operations using the above formula. Note that if $$$a$$$ is not sorted, we can just output $$$0$$$.

The time complexity is $$$O(n)$$$.

#include <bits/stdc++.h>
#include <numeric>
using namespace std;
 
int main(){
 
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int T; cin >> T;
 
    while (T--) {
 
        int n; cin >> n;
        vector<int> nums(n);
        int diff = 1e9;
        bool sorted = true;
        for (int i = 0; i < n; i++) {
            cin >> nums[i];
            if (i > 0) {
                diff = min(nums[i] - nums[i - 1], diff);
                sorted &= nums[i] >= nums[i - 1];
            }
        }
        
        if (!sorted) {
            cout << 0 << endl;
            continue;
        }
    
        cout << diff/2 + 1 << endl;
    }
}

Can a sequence involving $$$n$$$, which is up to $$$10^5$$$, really have up to $$$10^9$$$ terms?

The terms of the fibonacci sequence will increase exponentially. This is quite intuitive, but mathematically, fibonnaci-like sequences will increase at a rate of phi to the power of $$$n$$$, where phi (the golden ratio) is about $$$1.618$$$. Thus, the maximum number of terms a sequence can have before it reaches $$$10^9$$$, or the maximum value of $$$n$$$, is pretty small (around $$$\log n$$$).

Instead of trying to fix the first two elements of the sequence and counting how many sequences $$$s$$$ will have $$$s_k = n$$$, note that we already have $$$n$$$ fixed. If we loop over the $$$k-1$$$th element of the sequence, the sequence is still fixed. If we know the $$$x$$$th element and $$$x-1$$$th element of $$$s$$$, we can find that $$$s_{x - 2} = s_{x} - s_{x - 1}$$$.

Thus, we can just go backwards and simulate for $$$k$$$ iterations in $$$O(\log n)$$$ since $$$k$$$ is small, breaking at any point if the current sequence is not fibonnaci-like (there are negative elements or it is not strictly increasing). Otherwise, we add $$$1$$$ to our answer.

The time complexity is $$$O(n \cdot \log n)$$$.

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int T; cin >> T;
    
    while (T--) {
 
        int n; int k;
        cin >> n >> k;
     
        int ans = 0;
     
        for (int i = 1; i <= n; i++) {
            int second = n; //xth element where x is k
            int first = i; //fixing x-1th element where x is k-1
            bool valid_seq = true;
            for (int j = 0; j < k - 2; j++) {
                //for s_x and s_x-1, s_x-2 = s_x - s_x-1
                int fx = first;
                first = second - fx;
                second = fx;
                valid_seq &= first <= second;
                valid_seq &= min(first, second) >= 0;
                if (!valid_seq) break; //break if the sequence is not fibonacci-like
            }
            if (valid_seq) ans++;
        }
 
        cout << ans << endl;
    }
 
}

Analysis by awesomeguy856

$$$f[k] = F_{k-2}f[0]+F_{k-1}f[1]$$$

By the Extended Euclidean Algorithm, we can find one integral solution for this equation, since $$$\gcd (F_{k-2}, F_{k-1}) = 1 | f[k].$$$ Let this solution be $$$(f[0], f[1]) = (x, y).$$$ Then all other integral solutions are in the form $$$(x+cF_{k-1}, y-cF_{k-2}),$$$ for $$$c \in Z$$$ so we can find all valid solutions by binary search on $$$f[1],f[0] \geq 0$$$ and $$$f[1]>f[0]$$$, or just by some calculations.

Suppose that the numbers are arranged in a line in increasing order. Take a look at each number $$$x$$$ before some day. If it isn't deleted on that day, what new position does it occupy, and how is that impacted by its previous position?

Take this observation, and apply it to simulate the process backwards.

Suppose the numbers are arranged in a line in increasing order. Consider simulating backwards; instead of deleting the numbers at positions $$$a_1,a_2,\ldots,a_n$$$ in each operation, then checking the first number after $$$k$$$ operations, we start with the number $$$1$$$ at the front, try to insert zeroes right after positions $$$a_1-1, a_2-2, \ldots, a_{n}-n$$$ in each operation so that the zeroes will occupy positions $$$a_1, a_2, \ldots, a_n$$$ after the insertion, and after $$$k$$$ insertions, we will check the position that $$$1$$$ will end up at.

If $$$a_1$$$ is not equal to $$$1$$$, the answer is $$$1$$$. Otherwise, each insertion can be processed in $$$O(1)$$$ if we keep track of how many of $$$a_1-1, a_{2}-2,\ldots,a_{n}-n$$$ are before the current position $$$x$$$ of $$$1$$$; if $$$a_1-1$$$ through $$$a_i-i$$$ are before $$$x$$$, then we will insert $$$i$$$ zeroes before $$$x$$$.

The time complexity is $$$O(n+k)$$$ per test case. The editorial code additionally processes every insertion with the same $$$i$$$ value in $$$O(1)$$$, for $$$O(n)$$$ overall complexity.

There are alternative solutions using binary search with complexity $$$O(k\log nk)$$$ or $$$O(k\log n\log nk)$$$, and we allowed them to pass. In fact, this problem was originally proposed with $$$k \leq 10^9$$$ but we lowered the constraints.

#include <bits/stdc++.h>
using namespace std;

int n, k, a[200010];

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i;
    }
    if (a[0] != 1) {
        cout << 1 << "\n";
        return;
    }
    a[n] = 2e9;
    //start at position 1, and find what number moves to its position
    long long ans = 1;
    int inc = 1; //how many zeroes to insert
    while (inc < n) {
        int days = (a[inc] - ans + inc - 1) / inc;
        if (days >= k){
            ans += k * inc;
            k = 0;
            break;
        }
        ans += days * inc;
        k -= days;
        while (a[inc] <= ans) inc++;
    }
    ans += 1ll * k * n;
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int t; cin >> t;
    while (t--) solve();
}

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const int inf = 1e9+10;
const ll inf_ll = 1e18+10;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define cmax(x, y) (x = max(x, y))
#define cmin(x, y) (x = min(x, y))

#ifndef LOCAL
#define debug(...) 0
#else
#include "../../debug.cpp"
#endif

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        ll n, k; cin >> n >> k;
        vector<ll> a(n);
        for (int i = 0; i < n; i++)
            cin >> a[i];

        ll j = 0, x = 1;
        while (k--) {
            while (j < n && a[j] <= x+j)
                j++;
            x += j;
        }

        cout << x << "\n";
    }
}

You can solve the problem by picking one number from each pair $$$(n, -n)$$$, $$$(n - 1, -n + 1) \dots$$$, $$$(1, -1)$$$.

$$$b_i > b_j$$$ implies $$$a_i > a_j$$$.

First, try to determine one index in $$$O(n)$$$, or determine if that's impossible.

Sort the array $$$a$$$ to optimize the $$$O(n^2)$$$ solution.

At the start, let $$$x$$$ be an index such that $$$b_x$$$ has the greatest absolute value. If $$$b_x$$$ is negative, we have $$$a_x=0$$$, and else $$$a_x=n$$$. Moreover, we can't have $$$a_y=0,a_z=n$$$ for any indices $$$y$$$ and $$$z$$$, because that implies $$$b_y+b_z$$$ is both positive and negative, contradiction. Hence, the necessary and sufficient condition to check if we can determine an element in array $$$b$$$ with maximum absolute value is (there exists an element of array $$$a$$$ equal to $$$0$$$) xor (there exists an element of array $$$a$$$ equal to $$$n$$$). Then, we can remove that element and re-calculate the $$$a$$$ array, leading to an $$$O(n^2)$$$ solution. If the check fails at any moment, there is no valid solution.

To optimize it further, note that we can sort array $$$a$$$ at the start and keep track of them in a deque-like structure. We only need to check the front and end of the deque to see if our key condition holds. Finally, we can use a variable to record the number of positive elements deleted so far and subtract it from the front and end of the deque when checking our condition, so that each check is $$$O(1)$$$. The overall complexity becomes $$$O(n\log n)$$$ due to sorting.

#include <bits/stdc++.h>
using namespace std;

int n, ans[100010];
vector<pair<int,int>> arr;

void solve() {
    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i].first;
        arr[i].second = i;
    }
    sort(arr.begin(), arr.end());
    int l = 0, r = n - 1, sz = n;
    while (l <= r) {
        if ((arr[r].first == n - l) ^ (arr[l].first == n - 1 - r)) {
            if (arr[r].first == n - l) {
                ans[arr[r--].second] = sz--;
            }
            else {
                ans[arr[l++].second] = -(sz--);
            }
        }
        else {
            cout << "NO" << "\n";
            return;
        }
    }
    cout << "YES" << "\n";
    for (int i = 0; i < n; i++) cout << ans[i] << " ";
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    int t; cin >> t;
    while(t--) solve();
}

Suppose you knew in advance how many times each octopus will regenerate. Could you solve the problem then?

Can you figure out an $$$O(n^2)$$$ solution? And can you improve on it?

Suppose you already had the optimal solution for the subarray $$$a[1 \ldots i]$$$. How could you extend it to $$$a[1 \ldots i+1]$$$?

Read the solution in Hint One before continuing with this tutorial; it provides important definitions.

To reduce the number of possibilities for each $$$c[i]$$$, we prove the following lemma: There exists an optimal choice of $$$c$$$ (minimizing $$$\mathrm{throws}$$$) where all differences between adjacent $$$c[i]$$$ have absolute value less than $$$k$$$.

Intuitively, this is because we can decrease a $$$c[i]$$$ by $$$k$$$. Formally:

By the previous lemma, if we have determined $$$c[i]$$$, there are at most $$$2$$$ choices for $$$c[i+1]$$$. (There is $$$1$$$ choice when $$$b[i] = b[i+1]$$$, resulting in $$$d[i] = 0$$$, $$$c[i] = c[i+1]$$$, effectively merging the two octopuses.)

We can visualize this as a DAG in the 2D plane over all points $$$(i,c[i])$$$ (over all possible choices of $$$c[i]$$$). Each point points to the points in the next column that are the closest above and below (if it exists), forming a grid-like shape. Our goal is to find a path of minimum cost from $$$(0,0)$$$ to $$$(n+1,0)$$$.

This is the DAG for the second testcase in samples:

Call each time we choose a $$$c[i+1] > c[i]$$$ (i.e. positive $$$d[i]$$$) an ascent. Note that the number of ascents is fixed because each nonzero $$$d[i]$$$ is either $$$x$$$ or $$$x+k$$$ for some fixed negative $$$x$$$, and there must be a fixed number of $$$+k$$$'s to make the total change from $$$c[0]$$$ to $$$c[n+1]$$$ zero.

Each ascent brings the path up to the next "row" of descents. Since these rows slope downwards, the $$$j$$$th ascent must take place at or before some index $$$i_j$$$, because otherwise $$$c[i_j+1]$$$ would be negative.

We can use the following strategy to find a path which we claim is optimal:

If we can descend, then we descend. Otherwise, either we ascend, or alternatively, we change a previous descent into an ascent so we can descend here. (This can be further simplified by having a hypothetical "descent" here, so you do not need to compare two possibilities in the implementation.) Now, the best such location for an ascent is the one with minimum cost.

We can implement the above strategy with a priority queue, where for each descent we push on the cost of the corresponding ascent, and when an ascent is required, we then pop off the minimum element. In particular, if $$$b[i] < b[i+1]$$$, then the corresponding ascent has cost $$$b[i+1]-b[i]$$$, while if $$$b[i] > b[i+1]$$$, it has cost $$$b[i+1]-b[i]+k$$$. Also, since the bottom of the DAG corresponds to $$$c[i] = b[i]$$$, an ascent is required exactly when $$$b[i] < b[i+1]$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve() {
	int n, k;
	cin >> n >> k;
	priority_queue<int, vector<int>, greater<int>> differences;
	int previous = 0;
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		x %= k;
		if (x > previous) {
			differences.push(x - previous);
			ans += differences.top();
  			differences.pop();
		} else {
  			differences.push(k + x - previous);
		}
		previous = x;
  	}
  	cout << ans << "\n";
}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();
}

Solve the samples for all values of $$$k$$$.

What does constructing a second row from left to right look like?

How does knowing the possible $$$k$$$ for any first row help you construct a second row?

Apply dynamic programming to calculate the possible $$$k$$$, and use the information in the DP to construct a solution.

Call the number of adjacent pairs of cells with different characters the cost.

If we construct the second row from left to right, the amount each character adds to the cost only depends on the previous character. Thus, we can represent the problem with a DAG whose vertices represent choices for each character and whose edges represent the cost of choosing two adjacent characters. Our goal is to find a path starting from the far left and ending at the far right of cost $$$k$$$. For example, below is the DAG for the third testcase in the sample. (For convenience, we include the cost of cells in the top row with the corresponding cells in the bottom row.)

A general way to find such a path is as follows: For each vertex, store all possible costs of a path starting from the far left and ending at that vertex, which can be calculated with dynamic programming. Then we construct our path backwards from the right. For each candidate previous vertex, we check that the constructed path's cost plus the cost of the edge from this vertex plus some stored cost in this vertex equals $$$k$$$, in which case we know that some completion of the path from the far left to this vertex exists and we can choose this vertex.

Naively calculating this DP would require $$$O(n)$$$ time per operation. However, intuitively, each set of possible costs should contain almost all values between its minimum and maximum, and experiments suggest it always consists of at most two intervals. We will first formalize the DP and then prove this observation.

Let $$$\mathrm{dp}_A[i]$$$ store the set of possible values of $$$k$$$ when the grid is truncated to the first $$$i$$$ columns and the last character in the second row is $$$A$$$. Define $$$\mathrm{dp}_B[i]$$$ similarly.

Using the notation $$$[\mathrm{true}] = 1$$$, $$$[\mathrm{false}] = 0$$$, $$$S+x = \{s+x \mid s \in S\}$$$, we have the recurrences

with initial values $$$\mathrm{dp}_A[1] = [s_1 \ne A]$$$ and $$$\mathrm{dp}_B[1] = [s_1 \ne B]$$$.

Now either we hope that each set consists of $$$O(1)$$$ intervals, or we have to prove that each set indeed consists of at most two intervals:

To find the union of two sets of intervals, sort them by left endpoint and merge adjacent overlapping intervals. After computing the DP, apply the aforementioned backwards construction to obtain a valid second row.

Below is a visualization of solving the third testcase in the sample. Generate your own here!

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

struct state {

    // represents a set of integers compressed as a vector
    // of non-overlapping intervals [l, r]

    basic_string<array<int, 2>> a;

    // add d to everything in the set
    friend state add(state x, int d) {
        for (auto& [l, r] : x.a)
            l += d, r += d;
        return x;
    }

    // union of two sets of integers
    friend state unite(state x, state y) {
        state z;
        merge(all(x.a), all(y.a), back_inserter(z.a));
        int j = 0;
        for (int i = 1; i < z.a.size(); i++) {
            if (z.a[i][0] <= z.a[j][1]+1)
                z.a[j][1] = max(z.a[j][1], z.a[i][1]);
            else
                z.a[++j] = z.a[i];
        }
        z.a.erase(z.a.begin() + j + 1, z.a.end());
        return z;
    }

    // whether integer k is in the set
    friend bool contains(state x, int k) {
        for (auto& [l, r] : x.a)
            if (k >= l && k <= r)
                return true;
        return false;
    }
};

// set containing only one integer d
state from_constant(int d) {
    return state({{{d, d}}});
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        string s; cin >> s;

        vector<array<state, 2>> dp(n);

        dp[0][0] = from_constant(s[0] != 'A');
        dp[0][1] = from_constant(s[0] != 'B');

        for (int i = 1; i < n; i++) {
            dp[i][0] = add(unite(dp[i-1][0], add(dp[i-1][1], 1)), (s[i] != 'A') + (s[i] != s[i-1]));
            dp[i][1] = add(unite(dp[i-1][1], add(dp[i-1][0], 1)), (s[i] != 'B') + (s[i] != s[i-1]));
        }

        if (!(contains(dp[n-1][0], k) || contains(dp[n-1][1], k))) {
            cout << "NO\n";
            continue;
        }

        string ans;

        for (int i = n-1; i >= 0; i--) {
            char c = contains(dp[i][0], k - (i == n-1 ? 0 : (ans.back() != 'A'))) ? 'A' : 'B';
            k -= (c != s[i]);
            if (i > 0)
                k -= (s[i] != s[i-1]);
            if (i < n-1)
                k -= (c != ans.back());
            ans += c;
        }

        reverse(all(ans));
        cout << "YES\n" << ans << "\n";
    }
}

For each distinct value, only the leftmost and rightmost positions actually have an effect on the power.

Think of each distinct value as an interval corresponding to its leftmost and rightmost positions, and let that distinct value be the value of its interval. If interval $$$x$$$ strictly contains an interval $$$y$$$ with greater value, then $$$x$$$ will not have an effect on the power and it can be discarded.

In order to not change the power, we can only add intervals that strictly contain an interval with greater value. Afterwards, if $$$i$$$ is not the endpoint of an interval, $$$b_i$$$ equals the largest value of an interval containing $$$i$$$.

There will only be at most one interval that we have to add. Assume that there are multiple intervals that we can add without changing the answer. In this case it is easy to see that its more optimal to combine the interval with smaller value into the interval with larger value. Thus, it is never optimal to add multiple intervals.

Read the hints.

We can remove all intervals that will not affect the power by iterating over them in decreasing order of value and maintain a segment tree that stores for each left endpoint of any processed intervals, the right endpoint that corresponds to it. Checking if an interval is strictly contained then becomes a range minimum query.

Assume that we know the value $$$x$$$ of the interval that we want to add. We can immediately fill the value for the interior of all intervals that correspond to a value greater than $$$x$$$. However, we also have to guarantee that $$$x$$$ is strictly contained by an interval with greater value, so we can try each interval to contain $$$x$$$. If are no unfilled indices the left or right side of the interval, then we want to replace the smallest filled on either side value with $$$x$$$. Otherwise, we can just fill in all the unfilled indices with $$$x$$$. Note that it is also possible for $$$x$$$ to not be able to be contained by any interval.

Thus, we can just try every possible $$$x$$$ in decreasing order and maintain the filled indices as we iterate. There are only at most $$$n$$$ values of $$$x$$$ to check, which is just the set of $$$a_i - 1$$$ that does not appear in $$$a$$$.

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 1;

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

pii seg[400005];
int n;

void build(int l = 0, int r = n - 1, int cur = 0){
    seg[cur] = {INF, INF};
    if(l == r) return;
    int mid = (l + r)/2;
    build(l, mid, cur*2 + 1);
    build(mid + 1, r, cur*2 + 2);
}

void update(int x, int v, int l = 0, int r = n - 1, int cur = 0){
    if(l == r){
        seg[cur] = {v, l};
        return;
    }
    int mid = (l + r)/2;
    if(x <= mid) update(x, v, l, mid, cur*2 + 1);
    else update(x, v, mid + 1, r, cur*2 + 2);
    seg[cur] = min(seg[cur*2 + 1], seg[cur*2 + 2]);
}

pii query(int l, int r, int ul = 0, int ur = n - 1, int cur = 0){
    if(l <= ul && ur <= r) return seg[cur];
    if(l > r || ur < l || ul > r) return {INF, INF};
    int mid = (ul + ur)/2;
    return min(query(l, r, ul, mid, cur*2 + 1), query(l, r, mid + 1, ur, cur*2 + 2));
}

int main(){
    setIO();
    int t;
    cin >> t;
    for(int tt = 1; tt <= t; tt++){
        cin >> n;
        map<int, vector<int>> m;
        int arr[n];
        for(int i = 0; i < n; i++){
            cin >> arr[i];
            m[arr[i]].pb(i);
        }
        vector<int> rel; //relevant numbers
        for(auto &i : m){
            rel.pb(i.ff);
            for(int j = 1; j < i.ss.size() - 1; j++){
                arr[i.ss[j]] = 0;
            }
        }
        reverse(rel.begin(), rel.end());
        vector<int> nw;
        build();
        for(int i : rel){
            int l = m[i].front(), r = m[i].back();
            if(query(l, r).ff <= r){
                arr[l] = arr[r] = 0;
            } else {
                update(l, r);
                nw.pb(i);
            }
        }
        swap(rel, nw);
        set<int> s;
        for(int i = 0; i < n; i++) if(!arr[i]) s.insert(i);
        vector<int> vals; //possible target values
        for(int i = rel.size() - 1; i >= 0; i--){
            if(i == rel.size() - 1 || rel[i] - 1 != rel[i + 1]){
                vals.pb(rel[i] - 1);
            }
        }
        ll sum = 0, mx = 0, mxval = 0;
        int lex = -1, rex = -1;
        build();
        for(int i = 0; i < n; i++) if(!arr[i]) update(i, -1);
        reverse(vals.begin(), vals.end());
        queue<pii> upd;
        int ind = 0;
        //try to add an interval with value i
        for(int i : vals){
            vector<int> nxt;
            //try filling in all intervals > i
            while(ind < rel.size() && rel[ind] > i){
                int l = m[rel[ind]].front(), r = m[rel[ind]].back();
                set<int>::iterator it = s.lower_bound(l);
                while(it != s.end() && *it < r){
                    sum += rel[ind];
                    update(*it, rel[ind]);
                    upd.push({*it, rel[ind]});
                    it = s.erase(it);
                }
                nxt.pb(rel[ind++]);
            }
            //try each necessary interval to be strictly contained by i
            for(int j : nxt){
                int l = m[j].front(), r = m[j].back();
                if(s.size() && 0 < l && r < n - 1){
                    //find which indeces on each side to replace with i
                    pii rnw = query(r + 1, n);
                    pii lnw = query(0, l - 1);
                    if(rnw.ff == INF || lnw.ff == INF) continue;
                    ll add = (ll)i*s.size() + (rnw.ff == -1 ? 0 : i - rnw.ff) + (lnw.ff == -1 ? 0 : i - lnw.ff);
                    if(i && sum + add > mx){
                        mx = sum + add;
                        mxval = i;
                        lex = (lnw.ff == -1 ? -1 : lnw.ss);
                        rex = (rnw.ff == -1 ? -1 : rnw.ss);
                        //it is optimal to fill in all intervals > i
                        while(!upd.empty()){
                            arr[upd.front().ff] = upd.front().ss;
                            upd.pop();
                        }
                    }
                }
            }
        }
        //don't want to add any intervals
        if(s.size() == 0 && sum > mx){
            mx = sum;
            lex = rex = -1;
            //it is optimal to fill in all remaining intervals
            while(!upd.empty()){
                arr[upd.front().ff] = upd.front().ss;
                upd.pop();
            }
        }
        if(lex != -1) arr[lex] = 0;
        if(rex != -1) arr[rex] = 0;
        for(int i = 0; i < n; i++) cout << (arr[i] ? arr[i] : mxval) << " ";
        cout << endl;
    }
}

If we want to answer one of the questions (say, the question involving all the events) in polynomial time, how do we do it?

Construct a network with edges from the source to each of the red panda events with capacities equal to the number of red pandas, edges from red panda events to blue panda events with innite capacities if the red pandas can catch the corresponding blue pandas, and edges from each of the blue panda events to the sink with capacities equal to the number of blue pandas.

The next step is to use the max-flow min-cut theorem: the maximum flow is equal to the minimum number of red pandas plus blue pandas we need to remove from the graph such that no remaining red panda can reach any remaining blue panda.

How do we go from here?

For any cut, consider the region of the $$$x$$$-$$$t$$$ plane reachable by the remaining red pandas. No remaining blue pandas can lie in this region, and its border is a polyline that intersects each vertical line in the $$$x$$$-$$$t$$$ plane exactly once. Furthermore, the slope of every segment in this polyline has slope plus or minus $$$1$$$. Conversely, we can associate every polyline satisfying this condition with a cut; we just need to remove every red panda lying below the polyline and every blue panda lying on or above the polyline.

Now, figure out how to answer the queries online.

Read the hints to understand the solution better.

We can answer the queries online. For each $$$x$$$-coordinate $$$x$$$, maintain a treap that stores for every $$$x$$$-coordinate, the minimum cut $$$dp[x][t]$$$ associated with a polyline satisfying the condition above that starts at $$$x = -\infty$$$ and ends at $$$(x, t)$$$ when only considering events with $$$x$$$-coordinate at most $$$x$$$. When transitioning from to $$$x$$$ to $$$x+1$$$, we need to set for every $$$dp[x+1][t] = min(dp[x][t-1], dp[x][t], dp[x][t+1])$$$ for every $$$t$$$. To do this quickly, we maintain the values of $$$t$$$ where $$$dp[x][t+1] - dp[x][t] \neq 0$$$ in increasing order, of which there are at most $$$n$$$. When $$$x$$$ increases by one, each value of increases or decreases by one, depending on the sign of $$$dp[x][t+1]-dp[x][t]$$$, and some of the values of $$$t$$$ merge, decreasing the size of our treap. As long as we can process each merge in $$$\log n$$$ time, our solution will run in $$$O(n\log n)$$$ total time. When processing an event, we need to increase all $$$dp$$$ values in a suffix for red panda events, and all $$$dp$$$ values in a prefix for blue panda events. To answer a query, we just need to return the minimum prefix sum in our treap.

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int INF = 1e9 + 1;

void setIO() {
    ios_base::sync_with_stdio(0); cin.tie(0);
}

struct node {
    //mnpos - leftmost negative 
    //mxpos - rightmost positive
    int pos, tag, mnpos, mxpos;
    //minimum distance
    pair<int, pii> mndif;
    ll sum, pre, val;
    int weight;

    node(){}

    node(int pos_, ll val_){
        pos = pos_;
        val = val_;
        sum = val;
        pre = min((ll)0, val);
        mxpos = -INF;
        mnpos = INF;
        mndif = {INF, {INF, INF}};
        if(val > 0) mxpos = pos;
        if(val < 0) mnpos = pos;
        tag = 0;
        weight = rand();
    }
};

int sz = 1;
node treap[1000005];
int left0[1000005];
int right0[1000005];

int newnode(int pos, ll val){
    treap[sz] = node(pos, val);
    return sz++;
}

pair<int, pii> comb(int a, int b){
    if(a == -INF || b == INF) return {INF, {INF, INF}};
    return {b - a, {a, b}};
}

void pull(int x){
    treap[x].sum = treap[x].val;
    treap[x].pre = min((ll)0, treap[x].val);
    treap[x].mxpos = -INF;
    treap[x].mnpos = INF;
    treap[x].mndif = {INF, {INF, INF}};
    if(treap[x].val > 0) treap[x].mxpos = treap[x].pos;
    if(treap[x].val < 0) treap[x].mnpos = treap[x].pos;
    if(left0[x]){
        treap[x].mndif = min(treap[x].mndif, treap[left0[x]].mndif);
        treap[x].mndif = min(treap[x].mndif, comb(treap[left0[x]].mxpos, treap[x].mnpos));
        treap[x].mnpos = min(treap[x].mnpos, treap[left0[x]].mnpos);
        treap[x].mxpos = max(treap[x].mxpos, treap[left0[x]].mxpos);
        treap[x].pre = min(treap[left0[x]].pre, treap[left0[x]].sum + treap[x].pre);
        treap[x].sum += treap[left0[x]].sum; 
    }
    if(right0[x]){
        treap[x].mndif = min(treap[x].mndif, treap[right0[x]].mndif);
        treap[x].mndif = min(treap[x].mndif, comb(treap[x].mxpos, treap[right0[x]].mnpos));
        treap[x].mnpos = min(treap[x].mnpos, treap[right0[x]].mnpos);
        treap[x].mxpos = max(treap[x].mxpos, treap[right0[x]].mxpos);
        treap[x].pre = min(treap[x].pre, treap[x].sum + treap[right0[x]].pre);
        treap[x].sum += treap[right0[x]].sum;
    }
}

int move(node& x, int shift){
    int ret = x.pos;
    if(x.val < 0) ret -= shift;
    if(x.val > 0) ret += shift;
    return ret;
}

void apply(int x, int tag){
    treap[x].pos = move(treap[x], tag);
    treap[x].tag += tag;
    if(treap[x].mnpos != INF) treap[x].mnpos -= tag;
    if(treap[x].mxpos != -INF) treap[x].mxpos += tag;
    if(treap[x].mndif.ff != INF){
        treap[x].mndif.ff -= 2*tag;
        treap[x].mndif.ss.ff += tag;
        treap[x].mndif.ss.ss -= tag;
    }
}

void push(int x){
    if(!treap[x].tag) return;
    if(left0[x]) apply(left0[x], treap[x].tag);
    if(right0[x]) apply(right0[x], treap[x].tag);
    treap[x].tag = 0;
}

int merge(int a, int b){
    if(!a) return b;
    if(!b) return a;
    if(treap[a].weight < treap[b].weight){ 
        push(a);
        right0[a] = merge(right0[a], b);
        pull(a);
        return a;
    } else {
        push(b);
        left0[b] = merge(a, left0[b]);
        pull(b);
        return b;
    }
}

//splits rt's tree into [0, k) [k, INF)
pair<int, int> split(int x, int k){
    if(!x) return pair<int, int>{0, 0};
    push(x);
    pair<int, int> ret;
    if(treap[x].pos < k){
        ret = split(right0[x], k);
        right0[x] = ret.first;
        ret.first = x;
    } else {
        ret = split(left0[x], k);
        left0[x] = ret.second;
        ret.second = x;
    }
    pull(x);
    return ret;
}

int rt = 0;

void erase(int x){
    pair<int, int> a = split(rt, x);
    pair<int, int> b = split(a.second, x + 1);
    rt = merge(a.first, b.second);
}

//position, value
void insert(int a, ll b){
    if(!rt){
        rt = newnode(a, b);
        return;
    }
    pair<int, int> nw = split(rt, a);
    rt = merge(nw.first, merge(newnode(a, b), nw.second));
}

//value
ll query(int x){
    pair<int, int> a = split(rt, x);
    pair<int, int> b = split(a.second, x + 1); 
    ll ret = (b.first ? treap[b.first].val : 0);
    rt = merge(a.first, merge(b.first, b.second));
    return ret;
}

int main(){
    setIO();
    int n;
    cin >> n;
    int prv = 0;
    ll st = 0;
    for(int i = 1; i <= n; i++){
        int x, t, c;
        cin >> x >> t >> c;
        int dif = x - prv;
        //remove overlap
        while(rt && treap[rt].mndif.ff <= 2*dif){
            pair<int, pii> x = treap[rt].mndif;
            ll a = query(x.ss.ff), b = query(x.ss.ss);
            ll sub = min(a, -b);
            erase(x.ss.ff);
            erase(x.ss.ss);
            a -= sub, b += sub;
            if(a != 0) insert(x.ss.ff, a);
            if(b != 0) insert(x.ss.ss, b);
        }
        //shift everything
        if(rt){
            treap[rt].pos = move(treap[rt], dif);
            treap[rt].tag += dif;
            if(treap[rt].mnpos != INF) treap[rt].mnpos -= dif;
            if(treap[rt].mxpos != -INF) treap[rt].mxpos += dif;
            if(treap[rt].mndif.ff != INF){
                treap[rt].mndif.ff -= 2*dif;
                treap[rt].mndif.ss.ff += dif;
                treap[rt].mndif.ss.ss -= dif;
            }
        }
        ll cur = query(t + 1);
        if(cur != 0) erase(t + 1);
        if(cur - c != 0) insert(t + 1, cur - c);
        if(c > 0) st += c;
        cout << st + (!rt ? 0 : treap[rt].pre) << endl;
        prv = x;
    }
}