Skip to main content
Code Golf

Return to Answer

Bounty Ended with 50 reputation awarded by CommunityBot
Update cutoff to account for combined error of normal distribution approximation and three-place rounding
Source Link
Anders Kaseorg
Anders Kaseorg
  • 40.1k
  • 3
  • 75
  • 146

Python 3 + SciPy, score ≈ 1.86 · 10103

\$T(n, k)\$ approaches the normal distribution quickly enough that we can just compute it exactly for \$n < 50\$\$n < 97\$ and use the CDF of the normal distribution for \$n \ge 50\$\$n \ge 97\$. This solution runs in effectively constant time. (Technically, for \$n > 1.86 \cdot 10^{103}\$ the numbers start being too large to convert to float and we start getting OverflowError. This hardly matters because the answer is 0.500 for \$n > 1500000\$ or so.)

import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 5097:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

Try it online!Try it online!

Python 3 + SciPy, score ≈ 1.86 · 10103

\$T(n, k)\$ approaches the normal distribution quickly enough that we can just compute it exactly for \$n < 50\$ and use the CDF of the normal distribution for \$n \ge 50\$. This solution runs in effectively constant time. (Technically, for \$n > 1.86 \cdot 10^{103}\$ the numbers start being too large to convert to float and we start getting OverflowError. This hardly matters because the answer is 0.500 for \$n > 1500000\$ or so.)

import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 50:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

Try it online!

Python 3 + SciPy, score ≈ 1.86 · 10103

\$T(n, k)\$ approaches the normal distribution quickly enough that we can just compute it exactly for \$n < 97\$ and use the CDF of the normal distribution for \$n \ge 97\$. This solution runs in effectively constant time. (Technically, for \$n > 1.86 \cdot 10^{103}\$ the numbers start being too large to convert to float and we start getting OverflowError. This hardly matters because the answer is 0.500 for \$n > 1500000\$ or so.)

import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 97:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

Try it online!

Source Link
Anders Kaseorg
Anders Kaseorg
  • 40.1k
  • 3
  • 75
  • 146

Python 3 + SciPy, score ≈ 1.86 · 10103

\$T(n, k)\$ approaches the normal distribution quickly enough that we can just compute it exactly for \$n < 50\$ and use the CDF of the normal distribution for \$n \ge 50\$. This solution runs in effectively constant time. (Technically, for \$n > 1.86 \cdot 10^{103}\$ the numbers start being too large to convert to float and we start getting OverflowError. This hardly matters because the answer is 0.500 for \$n > 1500000\$ or so.)

import sys
import numpy as np
from scipy.special import erfc

n = int(sys.argv[1])
k = n * n // 4

if n < 50:
    a = np.array([1])
    for i in range(1, n + 1):
        a = np.cumsum((np.r_[a, np.ones(i)] - np.r_[np.zeros(i), a])[:-1] / i)
    out = a[k]
else:
    mean = n * (n - 1) / 4
    variance = n * (n - 1) * (2 * n + 5) / 72
    out = erfc((mean - k - 0.5) / np.sqrt(2 * variance)) / 2

print("%.3f" % (out,))

Try it online!