This problem requires a simple implementation. Set a variable (initially $$$0$$$) to represent the gold Robin has, and update it according to the rules as he scans through $$$a_i$$$, adding $$$1$$$ to answer whenever Robin gives away a gold.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
    n,k=mint()
    a=aint()
    cur=0
    ans=0
    for ai in a:
        if ai >= k:
            cur+=ai
        elif ai==0 and cur:
            ans+=1
            cur-=1
    print(ans)

#include <iostream>
 
using namespace std;
 
void work(){
    int n,k;
    cin >> n >> k;
 
    int res = 0, gold = 0;
    for (int i=0;i<n;i++){
        int cur;
        cin >> cur;
        if (!cur && gold) gold--, res++;
        else if (cur >= k) gold += cur; 
    }
 
    cout << res << '\n';
}
 
int main(){
 
    int t;
    cin >> t;
    while (t--) work();
 
    return 0;
}

The key observation is that $$$i^i$$$ has the same even/odd parity as $$$i$$$. Therefore, the problem reduces to finding whether the sum of $$$k$$$ consecutive integers ending in $$$n$$$ is even. This can be done by finding the sum of $$$n-k+1, n-k+2, ..., n-1, n$$$ which is $$$k*(2n-k+1)/2$$$, and checking its parity. Alternatively, one can count the number of odd numbers in those $$$k$$$ consecutive integers.

Note: Originally, the number of leaves grown was to be $$$i^m$$$ according to the fractal nature of life where $$$m$$$ is set to some integer. Developers decided to replace $$$m$$$ with $$$i$$$ for simplicity, following Filikec's suggestion.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
    n,k=mint()
    if n&1:
        odd=(k+1)//2
    else:
        odd=k//2
    print('NO' if odd&1 else 'YES')

#include <iostream>
 
using namespace std;
 
 
void work(){
    int n,k;
    cin >> n >> k;
 
    cout << (((n+1)*n/2 - (n-k)*(n-k+1)/2)%2?"NO":"YES") << '\n';
}
 
int main(){
 
    int t;
    cin >> t;
    while (t--) work();
    return 0;
}

If we sort the wealth in increasing order, then the $$$j$$$-th person must be unhappy for Robin to appear, where $$$j=\lfloor n/2 \rfloor +1$$$ if $$$1$$$-indexing or $$$j=\lfloor n/2 \rfloor$$$ if $$$0$$$-indexing. We need $$$a_j < \frac{s+x}{2*n}$$$, where $$$s$$$ is the original total wealth before $$$x$$$ gold from the pot was added. Rearranging the equation gives $$$x>2*n*a_j-s$$$. Because $$$x$$$ is a non-negative integer, we arrive at the answer $$$max(0,2*n*a_j-s+1)$$$.

Of course, this problem can also be solved by binary search, with two caveats. First, one needs to be careful to avoid comparison between integer and float types, as rounding errors could create issues. You can always avoid division by $$$2n$$$ by multiplying it out. Second, one needs to pick the upper limit carefully to ensure it is large enough. Note that $$$2*n*max(a)$$$ can serve as the upper limit for the binary search for $$$x$$$, because that would push the average to be strictly above $$$2*max(a)$$$ and everyone except the one with the pot of gold would be unhappy.

There are $$$2$$$ edge cases, $$$n=1, 2$$$, where the condition for Robin can never be reached, because the richest person will always be happy (at least in this problem, though perhaps not IRL). ChatGPT struggled to identify these edge cases, so it was tempting to leave at least one hidden. Following testing, we decided to give both in samples to reduce frustration.

Note: Wealth inequality is better measured by the Gini coefficient which is too involved for this problem. Our criterion is a crude approximation for the Gini coefficient, and is equivalent to setting the mean to median ratio (a well known indicator for inequality) to $$$2$$$. For a random distribution, this ratio is close to $$$1$$$. Interestingly, this ratio for UK salary distribution is around $$$1.2$$$, so no Robin yet.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
    n=sint()
    w=aint()
    if n<3:print(-1);continue
    tot=sum(w)
    w.sort()
    print(max(0,2*n*w[n//2]-tot+1))

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void work(){
    int n;
    cin >> n;
    
    long long sum = 0;
    vector<long long> v(n);
    for (auto &c : v) cin >> c, sum += c;
 
    sort(v.begin(),v.end());
 
    if (n < 3){
        cout << "-1\n";
        return;
    }
    cout << max(0LL,v[n/2]*2*n-sum+1) << '\n';
}
 
 
int main(){
    
    int t;
    cin >> t;
    while (t--) work();
 
 
    return 0;
}

Since the number of days $$$n$$$ is capped, we can check all possible start day $$$x$$$ in range $$$[1,n-d+1]$$$ (so that the duration of $$$d$$$ days would fit). We would like to find the number of overlapped jobs for each value of $$$x$$$.

A job between days $$$l_i$$$ and $$$r_i$$$ would overlap with the visit if the start day $$$x$$$ satisfies $$$l_i-d+1 \le x \le r_i$$$. Naively, this range update could be potentially $$$O(n)$$$, which is too slow. However, noting the start and end, each job update could be done in $$$2$$$ operations. We add $$$+1$$$ at $$$l_i-d+1$$$ and $$$-1$$$ at $$$r_i+1$$$, and after all jobs are recorded, we will take a prefix sum to work out the number of overlapped jobs for each $$$x$$$. When $$$l_i-d+1$$$ drops below $$$1$$$, we simply use $$$1$$$ to avoid lower values which are not being considered for $$$x$$$.

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

Note: Robin's risky jobs are generally deemed illegal by the Sheriff of Nottingham. Robert is practical and helpful. Like all good parents, Mrs Hood is a worrier.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
    n,d,k=mint()
    ct=[0]*(n+2)
    for _ in range(k):
        L,R=mint()
        ct[max(1,L-d+1)]+=1
        ct[R+1]-=1
    cur=0
    mn=10**6;mni=0
    mx=-1;mxi=0
    for i in range(1,n-d+2):
        cur+=ct[i]
        if cur<mn:mn=cur;mni=i
        if cur>mx:mx=cur;mxi=i
    print(mxi,mni)

#include <iostream>
#include <vector>
 
using namespace std;

void work(){
    int n,k,d;
    cin >> n >> d >> k;
 
    vector<int> ss(n+1),es(n+1);
 
    for (int i=0;i<k;i++){
        int a,b;
        cin >> a >> b;
        ss[a]++;
        es[b]++;
    }
 
    for (int i=0;i<n;i++) ss[i+1] += ss[i];
    for (int i=0;i<n;i++) es[i+1] += es[i];
 
    int most = 0;
    int robert = 0;
    int mrs = 0;
    int least = 1e9;
    for (int i=d;i<=n;i++){
        int cur = ss[i] - es[i-d];
        if (cur > most) most = cur, robert = i-d+1;
        if (cur < least) least = cur, mrs = i-d+1;
    }
 
    cout << robert << ' ' << mrs << "\n";
}
 
int main(){
    int t;
    cin >> t;
    while (t--) work();
 
    return 0;
}

This problem builds on the standard Dijkstra algorithm. So please familiarise yourself with the algorithm if not already.

In Dijkstra algorithm, a distance vector/list is used to store travel times to all vertices, here we need to double the vector/list to store travel times to vertices arriving with and without a horse. If a vertex has a horse, then it's possible to transition from without horse to with horse there. The Dijkstra algorithm is then run as standard.

What if a horse has already been taken by Marian when Robin arrives, and vice versa? Well, the optimal solution would not require the second person to arrive to use the horse, because the first to arrive could simply wait for the second to arrive, giving an earlier meeting than whatever is possible if the second to arrive had to use the horse and go elsewhere. Therefore, for any vertex, $$$1$$$ horse is sufficient.

We run Dijkstra algorithm twice to find the fastest time Robin and Marian could reach any vertex $$$i$$$ as $$$tR(i)$$$ and $$$tM(i)$$$. The earliest meeting time at a given vertex $$$i$$$ is $$$max(tR(i),tM(i))$$$, and we need to check all vertices.

The time complexity is that of Dijkstra algorithm which, in this problem, is $$$O(n \log n)$$$.

import sys
from heapq import *
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
def dij(ss):
    dis=[[big]*2 for _ in range(n+1)]
    dis[ss][0]=0
    chkd=[[0]*2 for _ in range(n+1)]
    Q=[(0,ss,0)]
    while Q:
        v,i,ride=heappop(Q)
        if chkd[i][ride]:continue
        chkd[i][ride]=1
        ride|=H[i]
        for j,w in g[i]:
            nv=v+w//2*(2-ride)
            if nv<dis[j][ride]:dis[j][ride]=nv;heappush(Q,(nv,j,ride))
    return dis
#################################################
big=float('inf')
t = sint()
for _ in range(t):
    n,m,h=mint()
    H=[0]*(n+1)
    for i in aint():H[i]=1
    g = [[] for _ in range(n + 1)]  #set up adjacency matrix
    for _ in range(m):
        u, v, w = mint()
        g[u].append((v,w))
        g[v].append((u,w))
    dM=dij(1)
    dR=dij(n)
    best,idx=big,0
    for i in range(1,n+1):
        tmp=max(min(dM[i]),min(dR[i]))
        if tmp<best:idx=i;best=tmp
    print(best if best!=big else -1)

#include <iostream>
#include <vector>
#include <set>

using namespace std;


void dijkstra(int s, vector<vector<long long>> &d, vector<vector<pair<int,long long>>> &graph, vector<bool> &hs){
    auto cmp = [&](auto &a, auto &b){return make_pair(d[a.first][a.second],a) < make_pair(d[b.first][b.second],b);};
    set<pair<int,int>,decltype(cmp)> q(cmp);
    
    d[s][0] = 0;
    q.insert({s,0});

    while (q.size()){
        auto [curv,curh] = *q.begin();
        q.erase(q.begin());

        bool horse = (curh || hs[curv]);
        for (auto &[neighv, neighd] : graph[curv]){
            long long dist = horse?neighd/2:neighd;
            if (d[neighv][horse] > d[curv][curh] + dist){
                q.erase({neighv,horse});
                d[neighv][horse] = d[curv][curh] + dist;
                q.insert({neighv,horse});
            }
        }
    }
}

void work(){
    int n,m,h;
    cin >> n >> m >> h;

    vector<bool> hs(n);
    vector<vector<pair<int,long long>>> graph(n);
    
    for (int i=0;i<h;i++){
        int c;
        cin >> c;
        hs[--c]=1;
    }

    for (int i=0;i<m;i++){
        int a,b,c;
        cin >> a >> b >> c;

        a--,b--;
        graph[a].push_back({b,c});
        graph[b].push_back({a,c});
    }

    vector<vector<long long>> d1(n,vector<long long>(2,1e18));
    vector<vector<long long>> d2(n,vector<long long>(2,1e18));

    dijkstra(0,d1,graph,hs);
    dijkstra(n-1,d2,graph,hs);


    long long best = 1e18;
    auto get = [&](int a){return max(min(d1[a][0],d1[a][1]),min(d2[a][0],d2[a][1]));};

    for (int i=0;i<n;i++) best = min(best,get(i));
    
    cout << (best==1e18?-1:best) << '\n';
}


int main(){
    int t;
    cin >> t;
    while (t--) work();

    return 0;
}

An important observation is that strengthening a base only influences its neighbors, so we can just keep consider adjacent nodes as later ones are not affected. Let's consider induction to solve this problem. Let $$$d[i][0]$$$ denote the most gold from node $$$i$$$ and all its children if we don't strengthen node $$$i$$$ and $$$d[i][1]$$$ if we do strengthen the node $$$i$$$.

1. Base case: If the current node $$$i$$$ is a leaf, $$$d[i][0] = 0$$$, $$$d[i][1] = a_i$$$.

2. Induction step: Consider the node $$$i$$$ with children $$$1 \dots m$$$. Assume that all nodes $$$1 \dots m$$$ are already calculated. If we don't strengthen the node $$$i$$$, $$$d[i][0] = {\sum_{j = 1}^m max(d[j][0],d[j][1])}$$$. If the node $$$i$$$ is strengthened, $$$d[i][1] = a_i + {\sum_{j = 1}^m max(d[j][0],d[j][1]-2\cdot c)}$$$.

Time complexity — $$$O(n)$$$.

import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
###############################################
T = sint()
for _ in range(T):
    n,c=mint()
    a=aint()
    g=[[] for _ in range(n)]  #set up adjacency matrix
    for _ in range(n - 1):
        u,v = map(int, input().strip().split())
        u-=1;v-=1
        g[u].append(v)
        g[v].append(u)
    dp=[[0]*n,a]
    kids=[[] for _ in range(n)]
    vis=[0]*n
    Q=[0]
    while Q:
        i=Q.pop()
        if i>=0:
            if vis[i]:continue
            vis[i]=1
            Q.append(~i)
            for j in g[i]:
                if vis[j]:continue
                Q.append(j)
                kids[i].append(j)
        else:
            i=~i
            for j in kids[i]:
                dp[0][i]+=max(dp[0][j],dp[1][j])
                dp[1][i]+=max(dp[0][j],dp[1][j]-2*c)
    print(max(dp[0][0],dp[1][0]))

#include <iostream>
#include <vector>
 
using namespace std;
 
void work(){
    int n,k;
    cin >> n >> k;
 
    vector<long long> v(n);
    vector<vector<int>> g(n);
    
    for (auto &c : v) cin >> c;
 
    for (int i=0;i<n-1;i++){
        int a,b;
        cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
 
    vector<bool> vis(n);
    vector<vector<long long>> d(n,vector<long long>(2));
 
    auto dfs = [&](auto &&dfs, int cur, int p) -> void {
        
        for (auto &neigh : g[cur]){
            if (neigh == p) continue;
            dfs(dfs,neigh,cur);
            d[cur][1] += max(d[neigh][0],d[neigh][1] - 2*k);
            d[cur][0] += max(d[neigh][0],d[neigh][1]);
        }
 
        d[cur][1] += v[cur];
    };
 
    dfs(dfs,0,-1);
 
    cout << max(0LL,max(d[0][0],d[0][1])) << '\n';
}
 
int main(){
 
    int t;
    cin >> t;
    while (t--) work();
 
    return 0;
}

The key for this problem is the use of a stack, where last item in is the first item out. As we scan through the diary entries, we will only drink till the day of the next entry. If there is left over milk, we will push them into the stack with number of pints and the day they were acquired. If there isn't enough milk to reach the next entry, we will check the stack for left overs. Careful implementation is required to check for expiry day. It might help to append a fictitious entry with large day number and $$$0$$$ pints. Since every pop from the stack accompanies either the processing of a diary entry or permanently removing a stack item, the number of stack operation is $$$O(n)$$$.

Since diary entries are presented in sorted order, the time complexity is $$$O(n)$$$.

Note: Originally, this problem has an easy version, where Little John drinks the oldest drinkable milk first. However testers and the team were uncertain about the difficulties of the two problems, and there was concern that they are too 'implementation heavy'. For the sake of balance, only the hard version is presented here as G. However, you may wish to try the easy version yourself. I recall my parents telling to open the oldest milk in fridge, and now I say the same to my children. Has it all been worthwhile?

import sys
input = lambda: sys.stdin.readline().rstrip("\r\m")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: tuple(map(int, input().split()))
###############################################
t = sint()
for _ in range(t):
    n,m,k=mint()
    a=[]
    for _ in range(n):a.append(aint())
    #a.sort() #not needed as entries are sorted
    ####Extravagant
    happy=0
    stack=[]
    a.append((10**12,0))
    for pt in range(n):
        cur_day,cur_milk=a[pt]
        cur_milk=min(cur_milk,m*k)
        days,extra=divmod(cur_milk,m)
        good=min(a[pt+1][0]-cur_day,days)
        happy+=good
        cur_day+=good
        cur_milk-=good*m
        if cur_day==a[pt+1][0] and cur_milk:stack.append((cur_day-good,cur_milk))
        while cur_day<a[pt+1][0] and stack and cur_day<stack[-1][0]+k:
            old,v=stack.pop()
            cur_milk+=v
            days,extra=divmod(cur_milk,m)
            good=min(a[pt+1][0]-cur_day,days,old+k-cur_day)
            happy+=good
            cur_day+=good
            cur_milk-=good*m
            if cur_day==a[pt+1][0] and cur_milk:stack.append((old,cur_milk))
    print(happy) #say hello to Wibbles the cat who also likes milk

#include <iostream>
#include <map>
#include <list>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;


void work(){
    int n,m,k;
    cin >> m >> n >> k;

    map<ll,ll> days;
    for (int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        days[a] += b;
    }

    days[1e18] = 0;

    ll curd = 1;
    ll got = 0;  
    ll res = 0;

    list<pll> pq;
    
    for (auto &cur : days){
       while (pq.size() && curd < cur.first){
            auto [d,x] = pq.front();
            pq.pop_front();

            if (d+k-1 < curd) continue;
            else if (d > curd) curd = d, got = 0;

            if (n-got > x) got += x;
            else{
                ll sat = min(curd + (x-n+got)/n + 1,min(d + k, cur.first));
                ll newx = x-(sat-curd)*n+got;
                if (newx) pq.push_front({d,newx});
                res += sat-curd;
                got = 0;
                curd = sat;
            } 
        }
        pq.push_front(cur);
    }
    
    cout << res << '\n';
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    int t;
    cin >> t;
    while (t--) work();

    return 0;
}

Sheriff can never win. This is quite obvious as Robin is the first to pick and both just keep picking the current biggest number. This means that Sheriff can at best get a tie — this happens if and only if all elements have even appearance. The segment $$$a_l \dots a_r$$$ is a tie if and only if there's no element that appears an odd number of times.

There are multiple ways to solve this problem. Two are outlined.

Mo's algorithm — offline

We can keep the count of appearances of each element using an array in $$$O(1)$$$ time. Sort the queries into blocks of size $$${\sqrt n}$$$. Keep updating the boundaries of the current segment and the total count of elements that appear an odd number of times. Sheriff can tie iff there is no odd appearance.

Time complexity — $$$O((n+q){\sqrt n})$$$.

Xor hashing

Consider the prefixes of all targets. If the current segment is $$$a_l \dots a_r$$$, there's no element with odd appearance if and only if the set of numbers with odd appearance in $$$a_1 \dots a_{l-1}$$$ is the same as $$$a_1 \dots a_r$$$. We can check if two prefixes have the same set of elements with odd appearance with xor hashing.

Time complexity — $$$O(n+q)$$$.

#xor hashing
import sys
import random
input = lambda: sys.stdin.readline().rstrip("\r\n")
sint = lambda: int(input())
mint = lambda: map(int, input().split())
aint = lambda: list(map(int, input().split()))
 
nmax=1<<64
tmp=random.randint(1,nmax)
T=sint()
for _ in range(T):
    n,q=mint()
    v=aint()
    w=[0]*n
    hsh=dict()
    rev=dict()
    for i in range(n):
        if v[i] not in hsh:
            while tmp in rev:tmp=random.randint(1,nmax)
            hsh[v[i]]=tmp
            rev[tmp]=v[i]
        w[i]=hsh[v[i]]
    psv=[0]
    for i in v:psv.append(psv[-1]^i)
    psw=[0]
    for i in w:psw.append(psw[-1]^i)
    for _ in range(q):
        L,R=mint()
        ans='YES' if psv[R]^psv[L-1]==0 and psw[R]^psw[L-1]==0 else 'NO'
        print(ans)

#Mo's algorithm
#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
 
using namespace std;
 
int K = 500;
int Cnt[1000001];
 
void work(){
    int n,q;
    cin >> n >> q;
 
    vector<int> v(n);
    for (auto &c : v) cin >> c, Cnt[c] = 0;
 
    vector<array<int,3>> qs(q);
    for (int i=0;i<q;i++) cin >> qs[i][0] >> qs[i][1], qs[i][2] = i;
 
    auto cmp = [&](array<int,3> &a, array<int,3> &b){return make_pair(make_pair(a[0]/K,a[1]/K),a) < make_pair(make_pair(b[0]/K,b[1]/K),b);};
    sort(qs.begin(),qs.end(),cmp);
 
    int l, r;
    l = r = 0;
    int odd = 1;
    Cnt[v.front()]++;
 
    vector<bool> res(q);
 
    for (auto &c : qs){
        c[0]--,c[1]--;
 
        while (r < c[1]){
            Cnt[v[++r]]++;
            if (Cnt[v[r]]%2) odd++;
            else odd--;
        }
 
        while (l > c[0]){
            Cnt[v[--l]]++;
            if (Cnt[v[l]]%2) odd++;
            else odd--;
        }
 
        while (l < c[0]){
            Cnt[v[l]]--;
            if (Cnt[v[l++]]%2) odd++;
            else odd--;
        }
 
        while (r > c[1]){
            Cnt[v[r]]--;
            if (Cnt[v[r--]]%2) odd++;
            else odd--;
        }
 
        res[c[2]] = odd;
    }
 
    for (bool c : res) cout << (c?"NO\n":"YES\n");
}
 
int main(){
    int t;
    cin >> t;
    while (t--) work();
    return 0;
}

#xor hashing
#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <set>
 
using namespace std;
 
 
void work(){
    int n,q;
    cin >> n >> q;
    vector<unsigned long long> v(n);
    for (auto &c : v) cin >> c;
 
    random_device rd; 
    mt19937_64 gen(rd());
    map<unsigned long long, unsigned long long> mapping;
    set<unsigned long long> used = {0};
 
    for (auto &c : v){
        unsigned long long random;
        if (!mapping.contains(c)){
            do{
                random = gen();
            }while (used.contains(random));
            used.insert(random);
            mapping[c] = random;
        }else{
            random = mapping[c];
        }
        c = random;
    }
 
    vector<unsigned long long> xor_pref(n+1);
 
    for (int i=0;i<n;i++) xor_pref[i+1] = xor_pref[i] ^ v[i];
    
    for (int i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        cout << ((xor_pref[r]^xor_pref[l-1])?"NO\n":"YES\n");
    }
}
 
int main(){
 
    int t;
    cin >> t;
    while (t--) work();
 
    return 0;
}