Given two points A and B and n circles, determine smallest possible radius for an unknown circle O that passes through A and B without intersecting any of the given circles. The constraint are 1 ≤ n ≤ 10^5, with point coordinates and radii in [-10^5, 10^5]. The solution must achieve a relative or absolute error ≤ 1e-3, and the answer is bounded by 10^12.

A binary search approach is applicable, yielding 80 points in scoring systems.

Rap God: String Comparison on Tree Paths

A tree has edges labeled with lowercase letters. For nodes a and b, f(a,b) denotes the string formed by concatenating edge labels along the path from a to b. Given multiple queries with parameters q and p, compute the sum over all m ≠ q of the indicator function [f(q,p) > f(q,m)]. Constraints: n, m ≤ 2×10^4, with a time limit of 7 seconds. A offline centroid decomposition approach is suitable, with complexity around O(n log^3 n).

Counting Graphs with Degree and Connectivity Constraints

Count the number of graphs with n nodes and m edges satisfying:

• No self-loops
• Maximum degree per node ≤ 2
• Largest connected component size exactly k

Output modulo 10^9+7. Constraints: 1 ≤ n, m, k ≤ 300.

Subtract the count of graphs with all components ≤ k-1 from those with all components ≤ k to enforce the exact size condition. Connected components are either chains or cycles. The number of distinct chains of size n is n!/2 (except n=1), and cycles count as (n-1)!/2 (except n=2).

Define DP state f[i][j] as the number of ways to use i nodes and j edges. Transitions consider adding a chain or cycle of size o:

• For chains: f[i+o][j+o-1] += f[i][j] * C(n-i-1, o-1) * (o! / 2) [with adjustment for o=1]
• For cycles: f[i+o][j+o] += f[i][j] * C(n-i-1, o-1) * ((o-1)! / 2) [with adjustment for o=2]

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, MAX = 305;
int comb[MAX][MAX], fact[MAX], inv2 = (MOD+1)/2;

void precompute(int n) {
    comb[0][0] = fact[0] = 1;
    for (int i = 1; i <= n; i++) {
        comb[i][0] = comb[i][i] = 1;
        fact[i] = 1LL * fact[i-1] * i % MOD;
        for (int j = 1; j < i; j++)
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
    }
}

int dp[MAX][MAX];
int countGraphs(int nodes, int edges, int maxComp) {
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for (int i = 0; i <= nodes; i++)
        for (int j = 0; j <= edges; j++)
            for (int compSize = 1; compSize <= maxComp && i+compSize <= nodes; compSize++) {
                long long ways = 1LL * comb[nodes-i-1][compSize-1] * fact[compSize] % MOD;
                if (compSize > 1) ways = ways * inv2 % MOD;
                if (j + compSize - 1 <= edges)
                    dp[i+compSize][j+compSize-1] = (dp[i+compSize][j+compSize-1] + 1LL * dp[i][j] * ways) % MOD;
                
                if (compSize > 1 && j + compSize <= edges) {
                    ways = 1LL * comb[nodes-i-1][compSize-1] * fact[compSize-1] % MOD;
                    if (compSize > 2) ways = ways * inv2 % MOD;
                    dp[i+compSize][j+compSize] = (dp[i+compSize][j+compSize] + 1LL * dp[i][j] * ways) % MOD;
                }
            }
    return dp[nodes][edges];
}

int main() {
    precompute(300);
    int n, m, k;
    cin >> n >> m >> k;
    int result = (countGraphs(n, m, k) - countGraphs(n, m, k-1) + MOD) % MOD;
    cout << result << endl;
    return 0;
}

Optimal Strategy in a Summation Game

Alice and Bob play n rounds. Initially x=0. Each round:

• Alice selects a real t in [0, k]
• Bob chooses to add or subtract t, but must add at least m times total

Alice aims to maximize x, Bob to minimize it. Compute the expected value of x modulo 10^9+7 under optimal play. Constraints: 1 ≤ m ≤ n ≤ 10^6, 1 ≤ k ≤ 10^9.

Bob will use exactly m additions. Let f(i,j) be the maximum score with i rounds remaining and j additions required. The recurrence is: f(i,j) = (f(i-1,j-1) + f(i-1,j)) / 2 Boundaries: f(i,0)=0, f(i,i)=i*k.

The solution involves summing contributions from boundary states f(i,i) weighted by combinatorial coefficients and powers of 1/2: Answer = k * Σ_{i=1}^{m} [ i * C(n-i-1, m-i) / 2^(n-i) ] Handle n=m as a special case.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7, MAX = 1e6+10;
int fact[MAX], invFact[MAX], pow2Inv[MAX];

int power(int base, int exp) {
    int res = 1;
    while (exp) {
        if (exp & 1) res = 1LL * res * base % MOD;
        base = 1LL * base * base % MOD;
        exp >>= 1;
    }
    return res;
}

void precompute(int n) {
    fact[0] = invFact[0] = pow2Inv[0] = 1;
    int inv2 = power(2, MOD-2);
    for (int i = 1; i <= n; i++) {
        fact[i] = 1LL * fact[i-1] * i % MOD;
        pow2Inv[i] = 1LL * pow2Inv[i-1] * inv2 % MOD;
    }
    invFact[n] = power(fact[n], MOD-2);
    for (int i = n-1; i >= 1; i--)
        invFact[i] = 1LL * invFact[i+1] * (i+1) % MOD;
}

int nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return 1LL * fact[n] * invFact[r] % MOD * invFact[n-r] % MOD;
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    if (n == m) {
        cout << (1LL * n * k % MOD) << endl;
        return;
    }
    long long sum = 0;
    for (int i = 1; i <= m; i++) {
        long long term = 1LL * i * nCr(n-i-1, m-i) % MOD;
        term = term * pow2Inv[n-i] % MOD;
        sum = (sum + term) % MOD;
    }
    cout << (1LL * k * sum % MOD) << endl;
}

int main() {
    precompute(MAX-1);
    int tests;
    cin >> tests;
    while (tests--) solve();
    return 0;
}