The step $$$2$$$ doesn't affect step $$$1$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())

def solve():
    n = ii()
    A = lii()
    B = lii()
    return sum(a - b for a, b in zip(A, B) if a > b) + 1

for _ in range(ii()):
    print(solve())

There are no much difference between the series when $$$n=k$$$ and $$$n=k+1$$$.

Construct the series from the left to the right greedily.

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())

def solve():
    n = ii()
    if n == 1:
        return [0]
    ans = [-1, 3] * (n // 2)
    if n % 2:
        ans.append(-1)
    else:
        ans[-1] = 2
    return ans

for _ in range(ii()):
    print(*solve())

Consider the operations modulo $$$k$$$.

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())

from collections import defaultdict
from random import getrandbits
RD = getrandbits(31)

def solve():
    n, k = mii()
    A = lii()
    B = lii()
    cnt = defaultdict(int)
    for x in A:
        r = x % k
        cnt[min(r, k-r) ^ RD] += 1
    for x in B:
        r = x % k
        cnt[min(r, k-r) ^ RD] -= 1
    return all(v == 0 for v in cnt.values())

for _ in range(ii()):
    print('YES' if solve() else 'NO')

What is the minimum diameter achievable?

How are leaves significant?

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())

def solve():
    n = ii()
    g = [[] for _ in range(n)]
    deg = [0] * n
    for _ in range(n-1):
        u, v = mii()
        u -= 1; v -= 1
        g[u].append(v)
        g[v].append(u)
        deg[u] += 1
        deg[v] += 1
    if n <= 3:
        return 0

    c1 = sum(deg[u] == 1 for u in range(n))
    mx = max(sum(deg[v] == 1 for v in g[u]) for u in range(n))
    return c1 - mx

for _ in range(ii()):
    print(solve())

import sys
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mii = lambda: map(int, input().split())
lii = lambda: list(mii())

def solve():
    n = ii()
    A = lii()
    B = lii()
    if A[-1] != B[-1]:
        return False
    for i in range(n-2, -1, -1):
        if A[i] != B[i] and A[i] ^ A[i+1] != B[i] and A[i] ^ B[i+1] != B[i]:
            return False
    return True

for _ in range(ii()):
    print('YES' if solve() else 'NO')

The grid possesses a significant property. Try to generate some grids with random $$$a$$$ and $$$b$$$, and understand the distribution of $$$0$$$'s and $$$1$$$'s.

For each point $$$(x, y)$$$, you can derive the answer formula like $$$\min(f(x,y), g(x,y))$$$. Note that $$$\displaystyle\min(f,g)=\frac{f+g}{2}-\frac{|f-g|}{2}$$$

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

#define f first
#define s second
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define tiii tuple<int,int,int>
#define tiiii tuple<int,int,int,int>
#define pb push_back
#define eb emplace_back
#define emp emplace
#define mkp make_pair
#define mkt make_tuple
#define vctr vector
#define arr array
#define all(x) x.begin(), x.end()
#define amin(a,b) a = min(a,b)
#define amax(a,b) a = max(a,b)
#define brick(x) cout << #x << " = " << (x) << " | "
#define dbg(x) cout << #x << " = " << (x) << '\n'
#define vdbg(a) cout << #a << " = "; for(auto _x : a)cout << _x << ' '; cout << '\n'
#define adbg(a,n) cout << #a << " = "; for(int _i = 1; _i <= n; ++_i)cout << a[_i] << ' '; cout << '\n'
#define adbg0(a,n) cout << #a << " = "; for(int _i = 0; _i < n; ++_i)cout << a[_i] << ' '; cout << '\n'
mt19937 rng(static_cast<uint32_t>(chrono::steady_clock::now().time_since_epoch().count()));
int uid(int a, int b) { return uniform_int_distribution<int>(a,b)(rng); }
ll uld(ll a, ll b) { return uniform_int_distribution<ll>(a,b)(rng); }

const int MOD = 1e9+7; // 998244353;

int a[200005];
int b[200005];
int c[200005][2];
int d[200005][2];
ll pf[400005][2];
int cnt[400005];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int tt;
	cin >> tt;
	while (tt--) {
		int n;
		cin >> n;
		string t;
		cin >> t;
		for (int i = 1; i <= n; ++i) {
			a[i] = (t[i-1] == '1');
		}
		cin >> t;
		for (int i = 1; i <= n; ++i) {
			b[i] = (t[i-1] == '1');
		}
		const int o = n;
		for (int i = 0; i <= 2*n; ++i) {
			pf[i][0] = 0;
			pf[i][1] = 0;
			cnt[i] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			c[i][0] = c[i-1][0]+(a[i] == 0);
			c[i][1] = c[i-1][1]+(a[i] == 1);
			pf[o+c[i][0]-c[i][1]][0] += c[i][0];
			pf[o+c[i][0]-c[i][1]][1] += c[i][1];
			cnt[o+c[i][0]-c[i][1]] += 1;
		}
		for (int i = 1; i <= 2*n; ++i) {
			pf[i][0] += pf[i-1][0];
			pf[i][1] += pf[i-1][1];
			cnt[i] += cnt[i-1];
		}
		for (int i = 1; i <= n; ++i) {
			d[i][0] = d[i-1][0]+(b[i] == 0);
			d[i][1] = d[i-1][1]+(b[i] == 1);
		}
		ll ans = 0;
		for (int i = 1; i <= n; ++i) {
			int z = d[i][1]-d[i][0];
			// 0 worth it when delta <= z
			ans += d[i][0]*(ll)cnt[o+z]+pf[o+z][0];
			ans += d[i][1]*(ll)(n-cnt[o+z])+pf[2*n][1]-pf[o+z][1];
		}
		cout << ans << '\n';
	}
	return 0;
}

For a set $$$S$$$, how many operations are required to transform $$$S$$$ into $$$S \setminus {\min(S)}$$$?

$$$S$$$ can be represented as a binary number (though very large).

How to calculate the answer when elements in $$$S$$$ are very large?

MOD = 10 ** 9 + 7

dp = [0] * 31
dp[0] = 1
for i in range(1, 31):
    dp[i] = i + 1
    for j in range(i):
        dp[i] = dp[i] * dp[j] % MOD

def dfs(v, k):
    if k == 0:
        return 1
    ans = v + 1
    v = min(v - 1, 30)
    k -= 1
    for j in range(v + 1):
        if k >= 1 << j:
            ans = ans * dp[j] % MOD
            k -= 1 << j
        else:
            ans = ans * dfs(j, k) % MOD
            break
    return ans

for _ in range(int(input())):
    n, k = map(int, input().split())
    s = list(map(int, input().split()))
    for i in range(n):
        s[i] -= 1
    s.sort()
    ans = 1
    for v in s:
        if v <= 30 and k >= 1 << v:
            k -= 1 << v
            ans = ans * dp[v] % MOD
        else:
            ans = ans * dfs(v, k) % MOD
            break
    print(ans)

Let's consider an easier problem: how do we find one coprime pair from $$$a$$$?

If there exists one coprime pair, it means there exists an $$$i$$$ such that

In other words, there are at least one other indices $$$j$$$ such that $$$\gcd(a_i, a_j)=1$$$.

Therefore, we strengthen the problem that we need to find $$$\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1]$$$ for each $$$i$$$. Here, we introduce two ways to solve the formula.

In the following discussion, we denote $$$f(d)$$$ to be the count of elements in $$$a$$$ divisible by $$$d$$$. We can precompute $$$f(1), f(2), \dots, f(m)$$$ in $$$O(m\log m)$$$ time using harmonic trick.

Let's build a graph $$$G$$$ where vertex $$$i$$$ and $$$j$$$ has an undirected edge if and only if $$$\gcd(a_i, a_j) = 1$$$. The problem becomes finding a match of size $$$2$$$ in the graph. However, we only has each vertex's degrees based on the discussion above. How do we find the match only based on degrees?

We use a greedy approach to obtain the match of size $$$2$$$. Let's say $$$G$$$ has at least one edge.

1. Choose a vertex $$$u$$$ with the maximum degree.
2. From all vertices that is connected to $$$u$$$, pick a vertex $$$v$$$ with the minimum degree.
3. Remove vertices $$$u$$$ and $$$v$$$ and their associated edges from $$$G$$$ to get a new graph $$$G^\prime$$$.
4. If there are at least one remaining edge in $$$G^\prime$$$, $$$G$$$ has a match of size $$$2$$$ that contains $$$(u, v)$$$ and the remaining edge. Otherwise, it doesn't have a match of size $$$2$$$.

For our problem, for each $$$i$$$, the degree is $$$\displaystyle\sum_{j=1}^{n}[\gcd(a_i, a_j)=1] - [a_i = 1]$$$. We can then brute force to find the first edge, remove it, and then try to find the second edge.

#include <bits/stdc++.h>
using i64 = long long;
constexpr int V = 1e6 + 10;

std::array<int, V> mu, comp;
std::vector<int> primes;

void solve() {
    int n, m = 0;
    std::cin >> n;
    std::vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
        m = std::max(m, a[i]);
    }
    std::vector<int> mul(m+1), deg(n), mp(m+1);
    for (int i = 0; i < n; ++i) {
        mp[a[i]]++;
    }
    for (int j = 1; j <= m; ++j) {
        for (int x = j; x <= m; x += j) {
            mul[j] += mp[x];
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j * j <= a[i]; ++j) {
            if (a[i] % j == 0) {
                deg[i] += mu[j] * mul[j];
                if (j * j < a[i]) {
                    deg[i] += mu[a[i] / j] * mul[a[i] / j];
                }
            }
        }
        if (a[i] == 1) --deg[i];
    }
    std::array<int, 4> ans;
    int u = 0, v = 0, mind = INT32_MAX;
    for (int i = 1; i < n; ++i) {
        if (deg[i] > deg[u]) {
            u = i;
        }
    }
    if (!deg[u]) {
        std::cout << "0\n";
        return;
    }
    deg[u] = 0;
    for (int i = 0; i < n; ++i) {
        if (i == u) continue;
        if (std::gcd(a[i], a[u]) == 1) {
            --deg[i];
            if (mind > deg[i]) {
                mind = deg[i];
                v = i;
            }
        }
    }
    ans[0] = u;
    ans[1] = v;
    deg[v] = 0;
    for (int i = 0; i < n; ++i) {
        if (i == u || i == v) continue;
        if (std::gcd(a[i], a[v]) == 1) {
            --deg[i];
        }
    }
    u = 0;
    for (int i = 1; i < n; ++i) {
        if (deg[i] > deg[u]) {
            u = i;
        }
    }
    if (!deg[u]) {
        std::cout << "0\n";
        return;
    }
    v = -1;
    for (int i = 0; i < n; ++i) {
        if (i == u || !deg[i]) continue;
        if (std::gcd(a[i], a[u]) == 1) {
            v = i;
            break;
        }
    }
    assert(v >= 0);
    ans[2] = u; ans[3] = v;
    for (int i = 0; i < 4; ++i) {
        std::cout << ans[i] + 1 << " \n"[i == 3];
    }
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int T = 1;
    std::cin >> T;
    mu[1] = 1;
    for (int i = 2; i < V; ++i) {
        if (!comp[i]) {
            primes.emplace_back(i);
            mu[i] = -1;
        }
        for (auto p: primes) {
            int q = i * p;
            if (q >= V) break;
            comp[q] = true;
            if (i % p == 0) {
                mu[q] = 0;
                break;
            } else {
                mu[q] = -mu[i];
            }
        }
    }
    while (T--) solve();
    return 0;
}