r"""WCDS lower bound for sampling + Steiner: spiders.

Spider: centre c, legs a_1..a_s (the unique minimum WCDS = unique minimum
vertex cover), leg a_i with d_i - 1 >= 1 pendant leaves, so d_T(a_i) = d_i and
n = 1 + sum d_i.  On G = T, g(X) = n - sum_{i in X} d_i exactly, so
W(y) = 2^{-n} prod_i (1 + y 2^{d_i}).  With j legs of size 3 and s - j legs
of size 2 we compute the finite-n Theorem 3.5 quantity
   min_y [ n log2(1+y) + n - sum log2(1+y 2^{d_i}) ] / n
(which equals the max_t mu_t / C(n,t) criterion up to a factor n+1, Lemma 6),
maximised over j, and compare with sqrt(5) - 1/2.
"""
from math import log2, exp, sqrt


def rate(s, j):
    ds = [3] * j + [2] * (s - j)
    n = 1 + sum(ds)
    def f(t):
        y = exp(t)
        return (n * log2(1 + y) + n - sum(log2(1 + y * 2 ** d) for d in ds)) / n
    lo, hi = -20.0, 20.0
    g = (5 ** 0.5 - 1) / 2
    for _ in range(200):
        m1, m2 = hi - g * (hi - lo), lo + g * (hi - lo)
        if f(m1) < f(m2):
            hi = m2
        else:
            lo = m1
    return f((lo + hi) / 2), n


for s in [50, 200, 1000]:
    best = max((rate(s, j) + (j,) for j in range(s + 1)), key=lambda z: z[0])
    v, n, j = best
    print(f"s={s}: worst j={j} (legs of size 3), n={n}, rate {2**v:.6f}^n")
print(f"sqrt(5)-1/2 = {sqrt(5) - 0.5:.6f}")