8
\$\begingroup\$

\$T(n, k)\$ gives the number of permutations of length \$n\$ with up to \$k\$ inversions. This values grows very quickly, for example for \$T(20, 100) = 1551417550117463564\$.

The maximum number of inversions possible is \$n\frac{n-1}{2}\$ so for \$k = n\frac{n-1}{2}\$ we know that \$T(n, k) = n!\$.

To make this task more interesting, and to allow for a wider variety of possible answers you will only have to compute \$T(n, k)\$ approximately.

Examples:

For \$n = 3\$ and \$k\$ from \$0…3\$:

0.167, 0.5, 0.833, 1.0

For \$n = 4\$ and \$k\$ from \$0…6\$:

0.042, 0.167, 0.375, 0.625, 0.833, 0.958, 1.0

For \$n = 5\$ and \$k\$ from \$0…10\$:

0.008, 0.042, 0.117, 0.242, 0.408, 0.592, 0.758, 0.883, 0.958, 0.992, 1.0

For \$n = 50\$ and \$k\$ from \$0…1225\$:

0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.001, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.002, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.003, 0.004, 0.004, 0.004, 0.004, 0.005, 0.005, 0.005, 0.005, 0.006, 0.006, 0.006, 0.006, 0.007, 0.007, 0.007, 0.008, 0.008, 0.008, 0.009, 0.009, 0.01, 0.01, 0.011, 0.011, 0.012, 0.012, 0.013, 0.013, 0.014, 0.015, 0.015, 0.016, 0.017, 0.017, 0.018, 0.019, 0.02, 0.02, 0.021, 0.022, 0.023, 0.024, 0.025, 0.026, 0.027, 0.028, 0.029, 0.03, 0.032, 0.033, 0.034, 0.035, 0.037, 0.038, 0.039, 0.041, 0.042, 0.044, 0.046, 0.047, 0.049, 0.051, 0.052, 0.054, 0.056, 0.058, 0.06, 0.062, 0.064, 0.066, 0.069, 0.071, 0.073, 0.075, 0.078, 0.08, 0.083, 0.085, 0.088, 0.091, 0.094, 0.096, 0.099, 0.102, 0.105, 0.108, 0.112, 0.115, 0.118, 0.121, 0.125, 0.128, 0.132, 0.136, 0.139, 0.143, 0.147, 0.151, 0.155, 0.159, 0.163, 0.167, 0.171, 0.175, 0.18, 0.184, 0.189, 0.193, 0.198, 0.202, 0.207, 0.212, 0.217, 0.222, 0.227, 0.232, 0.237, 0.242, 0.247, 0.253, 0.258, 0.263, 0.269, 0.274, 0.28, 0.286, 0.291, 0.297, 0.303, 0.309, 0.315, 0.321, 0.327, 0.333, 0.339, 0.345, 0.351, 0.357, 0.363, 0.37, 0.376, 0.382, 0.389, 0.395, 0.401, 0.408, 0.414, 0.421, 0.427, 0.434, 0.44, 0.447, 0.454, 0.46, 0.467, 0.473, 0.48, 0.487, 0.493, 0.5, 0.507, 0.513, 0.52, 0.527, 0.533, 0.54, 0.546, 0.553, 0.56, 0.566, 0.573, 0.579, 0.586, 0.592, 0.599, 0.605, 0.611, 0.618, 0.624, 0.63, 0.637, 0.643, 0.649, 0.655, 0.661, 0.667, 0.673, 0.679, 0.685, 0.691, 0.697, 0.703, 0.709, 0.714, 0.72, 0.726, 0.731, 0.737, 0.742, 0.747, 0.753, 0.758, 0.763, 0.768, 0.773, 0.778, 0.783, 0.788, 0.793, 0.798, 0.802, 0.807, 0.811, 0.816, 0.82, 0.825, 0.829, 0.833, 0.837, 0.841, 0.845, 0.849, 0.853, 0.857, 0.861, 0.864, 0.868, 0.872, 0.875, 0.879, 0.882, 0.885, 0.888, 0.892, 0.895, 0.898, 0.901, 0.904, 0.906, 0.909, 0.912, 0.915, 0.917, 0.92, 0.922, 0.925, 0.927, 0.929, 0.931, 0.934, 0.936, 0.938, 0.94, 0.942, 0.944, 0.946, 0.948, 0.949, 0.951, 0.953, 0.954, 0.956, 0.958, 0.959, 0.961, 0.962, 0.963, 0.965, 0.966, 0.967, 0.968, 0.97, 0.971, 0.972, 0.973, 0.974, 0.975, 0.976, 0.977, 0.978, 0.979, 0.98, 0.98, 0.981, 0.982, 0.983, 0.983, 0.984, 0.985, 0.985, 0.986, 0.987, 0.987, 0.988, 0.988, 0.989, 0.989, 0.99, 0.99, 0.991, 0.991, 0.992, 0.992, 0.992, 0.993, 0.993, 0.993, 0.994, 0.994, 0.994, 0.994, 0.995, 0.995, 0.995, 0.995, 0.996, 0.996, 0.996, 0.996, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.997, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.998, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 0.999, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0

Input:

One value: \$n\$.

Output:

\$\frac{T(n,\lfloor n^2/4 \rfloor)}{n!}\$ rounded to three decimal places. \$T(n, k)\$ is defined by OEIS sequence A161169.

Sample input and output

n = 3. Output: 0.833
n = 6. Output: 0.765
n = 9. Output: 0.694
n = 12. Output: 0.681
n = 15. Output: 0.651
n = 18. Output: 0.646
n = 50. Output: 0.586
n = 100. Output: 0.56
n = 150. Output: 0.549
n = 200. Output: 0.542
n = 250. Output: 0.538
n = 300. Output: 0.535

Your code should be correct no matter what values of \$n\$ and \$k\$ are given but will only be tested on \$k = \lfloor n^2/4 \rfloor \$. Your output must be within \$0.001\$ of the correct value.

Score

I will run your code on my machine: 8GB RAM, AMD FX(tm)-8350 Eight-Core Processor running Ubuntu 16.04.6 LTS.

I will test for \$n = 50, 100, 150, 200, 250, 300, 350, 400, ...\$ until it no longer completes in 10 seconds. I will also limit the RAM used to 6GB using https://github.com/pshved/timeout.

Your score is the highest \$n\$ your code can reach on my computer within the time limit. If there is a tie, the first answer wins.

Notes

Your code does not need to be deterministic. That is random sampling methods are allowed as long as they give the right answer at least 9 times out of the first 10 times I test them.

\$\endgroup\$
  • \$\begingroup\$ I think the restriction that the code should work for all \$(n,k)\$ should be changed to for all \$n\$ if you only look at the cases where \$k=\lfloor\frac{n^2}{4}\rfloor\$ and the only required output is \$\frac{T(n,\lfloor\frac{n^2}{4}\rfloor)}{n!}\$. \$\endgroup\$ – Shieru Asakoto Oct 10 at 0:14
  • 2
    \$\begingroup\$ FWIW, a naive random-sampling implementation in MATLAB can get to 200 on my laptop before timing out. \$\endgroup\$ – HiddenBabel Oct 10 at 7:53
  • 1
    \$\begingroup\$ I would suggest asking for a program that takes both \$n\$ and \$k\$ as input, so that “correct no matter what values of \$n\$ and \$k\$ are given” is not a non-observable requirement. \$\endgroup\$ – Anders Kaseorg Oct 11 at 22:21
9
+50
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ Is it proven to approach the normal distribution? How did you figure that out? \$\endgroup\$ – HiddenBabel Oct 11 at 0:36
  • 1
    \$\begingroup\$ @HiddenBabel Inserting \$n\$ into any permutation of \$1, \dotsc, n - 1\$ adds a number of inversions equal to \$n\$ minus its position. When building random permutations, this number of added inversions is an independent uniformly random number from \$0, \dotsc, n - 1\$. The central limit theorem tells you that when you add a large number of small enough independent random variables, the result approaches a normal distribution. \$\endgroup\$ – Anders Kaseorg Oct 11 at 0:44
  • \$\begingroup\$ Is it correct (up to the required precision) for all n and k? I will test it in about 12 hours time. \$\endgroup\$ – Anush Oct 11 at 6:54
  • \$\begingroup\$ Unfortunately my internet connection has gone down so it will take me a few days until I can test this. \$\endgroup\$ – Anush Oct 11 at 18:43
  • 1
    \$\begingroup\$ @Anush Yeah, all \$n\$ and \$k\$ (if you edit the program to take \$k\$ as input). Although I just realized that I had forgotten to take into account the combined effect of the normal distribution approximation with the three-digit rounding, so I’ve bumped the cutoff to \$n \ge 97\$. The worst case is \$T(97, 2217)/97! \approx 0.24598945\$, where the normal distribution approximation is \$0.24548087\$ which rounds to \$0.245\$ for an error of \$0.00098945\$. \$\endgroup\$ – Anders Kaseorg Oct 11 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.