Notice that all initial elements are positive, so the initial arithmetic mean will always be $$$\geq 1$$$. We want the sum to be equal to the number of elements, so we need to increase the number of elements, but not the total sum. To do this, we can insert the number $$$0$$$. Adding one $$$0$$$ element increases the number of elements by one, and the total sum remains the same. To find out the number of zeroes we have to add we can solve the equation $$$sum = n + ans \equiv sum-n = ans$$$.

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

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        int sum = 0;
        for (int i = 0;i < n; i++){
            int a;
            cin >> a;
            sum += a;
        }

        cout << sum - n << "\n";
    }
}

We can notice that the optimal strategy is to put the yoyos in the corners of the board. One solution may be checking the best distance for all pairs of corners. But, if we think a bit more, we can notice that placing the yoyos in opposite corners, the distance will always be the maximum possible (the distance always being $$$2 \cdot (n - 1) + 2 \cdot (m - 1)$$$). So, one possible answer is to always place the first yoyo in the top-left cell and the second one in the bottom-right cell. This is always optimal because, for any initial position of Anton, the distance will still be the same ($$$2 \cdot (n - 1) + 2 \cdot (m - 1)$$$), this being the largest possible distance. The distance can not get larger than that because if we move one of the yoyos, it will get closer to the other yoyo, and the distance will decrease by $$$1$$$ or won't decrease, but it can't increase.

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

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n, m, i, j;
        cin >> n >> m >> i >> j;

        cout << 1 << " " << 1 << " " << n << " " << m << "\n";
    }
}

We claim that the maximum difficulty is at least $$$n-2$$$. Assume the array is sorted. We first need to find the two mountains which go on the ends. To do this, we can iterate through every mountain in the sorted array and check the difference between a mountain and its neighbours in the array. Let $$$m_k$$$ and $$$m_{k+1}$$$ be the mountains with the smallest height difference. We can achieve at least a difficulty of $$$n-2$$$ by arranging the mountains as $$$m_k, m_{k+2}, m_{k+3} ... m_n, m_1, m_2, ....., m_{k+1}$$$. To get difficulty $$$n-1$$$, we need $$$m_k$$$ to be the shortest mountain and $$$m_{k+1}$$$ to be the tallest mountain. This will only happen if $$$n = 2$$$.

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

int main()
{
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<int> h(n);

        for (int i = 0;i < n; i++){
            cin >> h[i];
        }
        sort(h.begin(), h.end());

        if(n == 2){
            cout << h[0] << " " << h[1] << "\n";
            continue;
        }

        int pos = -1, mn = INT_MAX;

        for (int i = 1;i < n; i++){
            if(mn > abs(h[i] - h[i - 1])){
                pos = i;
                mn = abs(h[i] - h[i - 1]);
            }
        }
        
        for (int i = pos;i < n; i++){
            cout << h[i] << " ";
        }
        for(int i = 0;i < pos; i++){
            cout << h[i] << " ";
        }

        cout << "\n";

    }
}

Let's consider $$$3$$$ cases for this problem:

1) n is odd

2) n is even, and $$$n$$$ is not a power of $$$2$$$

3) n is a power of $$$2$$$

If $$$n$$$ is odd, the only move is to subtract an odd divisor (since all the divisors are odd). Doing this, we will obtain an even number that is not a power of $$$2$$$(case 2). If $$$D$$$ is the divisor of $$$n$$$, then $$$n-D$$$ must also be divisible by $$$D$$$, and since $$$D$$$ is odd, $$$n-D$$$ cannot be a power of $$$2$$$.

If $$$n$$$ is even and is not a power of $$$2$$$, it means that $$$n$$$ has an odd divisor. By subtracting this odd divisor, we will obtain $$$n-D$$$ is odd(case 1). Now let's show that subtracting an odd divisor every move results in a win. Primes are losing since the only move you can make on them is subtracting the entire number, which results in $$$n = 0$$$ and a loss. Since every prime is odd or a power of 2, it works to give the other player an odd number because it will either be a prime(the other player loses), or they will make a move and give you another even number that is not a power of 2. You can continue this process because you will never land on a losing number and because the game must end after a finite number of moves, your opponent must always lose.

So we proved that odd numbers are losing and even numbers that are not powers of $$$2$$$ are winning.

What if $$$n$$$ is a power of $$$2$$$? You can do two things in one move, halve $$$n$$$ or make n an even number that is not a power of $$$2$$$(we proved that this is a winning position for the other player). The only optimal move is to halve $$$n$$$, making it another power of $$$2$$$. The players continue like this until one gets $$$2$$$, which is a prime number, so it's losing. If $$$log_2(n)$$$ is even, Alice wins, otherwise Bob wins.

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

string get(string s, int k){
    while((int)s.size() < k){
        s = s + s;
    }
    while((int)s.size() > k)
        s.pop_back();
    return s;
}
int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    string pref = "";
    pref += s[0];

    string mn = get(pref, k);

    for(int i = 1;i < n;i++){
        if(s[i] > s[0])break;
        pref += s[i];
        mn = min(mn, get(pref, k));
    }
    cout << mn << "\n";
}

We claim that it is optimal to choose a prefix of the string, then duplicate it until we have a length bigger than $$$k$$$, then delete the excess elements. An important observation is that we cannot omit the first character, so every time we duplicate, the first character would be the next. I will define a good prefix as: 1) It does not contain any character bigger than the first one. 2) It does not end in a character equal to the first one(except in cases where the prefix has length $$$1$$$)

Suppose a good prefix has a character bigger than the first one. In that case, it means that it's possible to delete this character and duplicate the string, thus placing the first character in its position and making the string lexicographically lower.

If a good prefix ends in a character equal to the first character, then it is possible to delete that character. After duplication, the string will be lexicographically lower.

Knowing that duplicating a good prefix is optimal, we know that we can't delete the last element after duplication as it is smaller than the first one. We proved that it is optimal to choose a prefix, duplicate it until the length is bigger than k then delete the excess. As the constraints are low, we can iterate through every prefix on the original string and make a string of length $$$k$$$ with it. Then we take the minimum of all these strings as the answer. Solution complexity $$$O(n\cdot k)$$$.

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

string get(string s, int k){
    while((int)s.size() < k){
        s = s + s;
    }
    while((int)s.size() > k)
        s.pop_back();
    return s;
}
int main()
{
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    string pref = "";
    pref += s[0];

    string mn = get(pref, k);

    for(int i = 1;i < n;i++){
        if(s[i] > s[0])break;
        pref += s[i];
        mn = min(mn, get(pref, k));
    }
    cout << mn << "\n";
}

TBA

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

vector<pair<pair<int,int>,int>> a;

void count_sort(vector<pair<pair<int,int>,int>>& a){
 
    int n = (int)a.size();
    {
        vector<int> cnt(n, 0);
        for(auto x: a)cnt[x.first.second]++;
        vector<pair<pair<int,int>,int>> new_a(n);
        vector<int> pos(n);
        pos[0] = 0;
        for(int i = 1;i < n;i++){
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for(auto x: a){
            int i = x.first.second;
            new_a[pos[i]] = x;
            ++pos[i];
        }
        a = new_a;
    }
 
    {
        vector<int> cnt(n, 0);
        for(auto x: a)cnt[x.first.first]++;
        vector<pair<pair<int,int>,int>> new_a(n);
        vector<int> pos(n);
        pos[0] = 0;
        for(int i = 1;i < n;i++){
            pos[i] = pos[i - 1] + cnt[i - 1];
        }
        for(auto x: a){
            int i = x.first.first;
            new_a[pos[i]] = x;
            ++pos[i];
        }
        a = new_a;
    }
}

vector<int> suffix_array(string s){
    int n = (int)s.size();
    vector<int> p(n), c(n);
    {
        vector<pair<char,int>> A(n);
        for(int i = 0;i < n;i++)A[i] = {s[i], i};
        sort(A.begin(), A.end());
        for(int i = 0;i < n;i++)p[i] = A[i].second;
        c[p[0]] = 0;
        for(int i = 1;i < n;i++){
            if(A[i].first == A[i - 1].first){
                c[p[i]] = c[p[i - 1]];
            }else{
                c[p[i]] = c[p[i - 1]] + 1;
            }
        }
    }
    int k = 0;
    while((1 << k) < n){
        for(int i = 0;i < n;i++){
            a[i] = {{c[i], c[(i + (1 << k)) % n]}, i};
        }
        count_sort(a);
        for(int i = 0;i < n;i++)p[i] = a[i].second;
        c[p[0]] = 0;
        for(int i = 1;i < n;i++){
            c[p[i]] = c[p[i - 1]] + (a[i].first != a[i - 1].first);
        }
        ++k;
    }
    return p;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n, k;
    string s;
    cin >> n >> k;
    cin >> s;

    a.resize(n);
    auto p = suffix_array(s);
    int len = n;

    bool ok = false;

    for(int i = 0;i < n;i++){
        
        if(ok){
            len = min(len, a[i].second);
        }
        if(a[i].second == 0)ok = true;
    }

    for(int i = 0;i < k;i++){
        cout << s[i % len];
    }
}

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

string s;
int n, k;

vector<int> z_func(string &s) {
    int n = s.size(), L = -1, R = -1;
    vector<int> z(n);
    z[0] = n;
    for(int i = 1; i < n; i++) {
        if(i <= R)
            z[i] = min(z[i - L], R - i + 1);
        while(i + z[i] < n && s[i + z[i]] == s[z[i]])
            z[i]++;
        if(i + z[i] - 1 > R) {
            L = i;
            R = i + z[i] - 1;
        }
    }
    return z;
}

void finish(int m) {
    for(int i = 0; i < k; i++)
        cout << s[i % m];
    cout << '\n';
    exit(0);
}

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

    cin >> n >> k >> s;
    auto z = z_func(s);

    int cur = 1;
    for(int i = 1; i < n; i++) {
        if(s[i] > s[i % cur])
            finish(cur);
        if(s[i] < s[i % cur]) {
            cur = i + 1;
            continue;
        }
        int off = i - cur + 1;
        if(off == cur) {
            cur = i + 1;
            continue;
        }
        if(z[off] < cur - off) {
            if(cur + off + z[off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[off + z[off]] > s[z[off]])
                cur = i + 1;
            continue;
        }
        if(z[cur - off] < off) {
            if(2 * cur + z[cur - off] >= k) {
                cur = i + 1;
                continue;
            }
            if(s[cur - off + z[cur - off]] < s[z[cur - off]])
                cur = i + 1;
            continue;
        }
        cur = i + 1;
    }

    finish(cur);
}

Let's consider $$$2$$$ cases:

1) The graph is bipartite

2) The graphs is not bipartite

If the graph is bipartite, let the nodes be coloured red and blue with the condition that all the neighbours of any red node are blue and all the neighbours of any blue node are red. Let us call $$$sum1 = \sum target_i-value_i$$$ for each blue node and $$$sum2 = \sum target_i-value_i$$$ for each red node. We want to determine if we can make $$$target_i = value_i$$$ for each node, which is equivalent to saying $$$sum1 = 0$$$ and $$$sum2 = 0$$$. We notice that the difference between $$$sum1$$$ and $$$sum2$$$ is invariant in a bipartite graph because all operations will add to sum1 and sum2 at the same time. So to make $$$sum1$$$ = 0 and $$$sum2 = 0$$$ we need sum1-sum2 to be equal to $$$0$$$ initially.

If the graph is not bipartite, then it contains an odd length cycle and we can use it to remove any difference between the target and the value of a vertex. This is an example for $$$3$$$ nodes where you can do an operation between node $$$2$$$ and $$$3$$$ to cancel the excess out.

//ADD IMAGE HERE

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

const int N = 2e5 + 10;
vector<int> adj[N];
int s[N], n, m;
bool bipartite()
{
    bool bip = true;

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

    queue<int> q;

    for(int i = 0;i < n;i++){
        if(s[i] != -1)continue;

        q.push(i);
        s[i] = 0;

        while(!q.empty()){
            int v = q.front();
            q.pop();

            for(int u: adj[v]){
                if(s[u] == -1){
                    s[u] = s[v] ^ 1;
                    q.push(u);
                }else bip &= s[u] != s[v];
            }
        }
    }
    return bip;
}

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int T;
    cin >> T;
    while(T--)
    {
        cin >> n >> m;
        for(int i = 0;i < n;i++)
            adj[i].clear();
        vector<int> v(n), t(n);

        for(int i = 0;i < n; i++){
            cin >> v[i];
        }
        for (int i = 0;i < n; i++){
            cin >> t[i];
        }

        for(int i = 0;i < m;i++){
            int a, b;
            cin >> a >> b;
            --a, --b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        if(bipartite() == false){
            cout << "YES\n";
        }else{
            vector<int> c(2, 0);

            for(int i = 0;i < n;i++){
                c[s[i]] += v[i] - t[i];
            }

            if(c[0] == c[1]){
                cout << "YES\n";
            }else cout << "NO\n";
        }
    }

}