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.

Improve this question
\$\endgroup\$
3
  • \$\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
    Commented Oct 10, 2019 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
    Commented Oct 10, 2019 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
    Commented Oct 11, 2019 at 22:21

2 Answers 2

Reset to default
10
+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!

Improve this answer
\$\endgroup\$
6
  • \$\begingroup\$ Is it proven to approach the normal distribution? How did you figure that out? \$\endgroup\$
    – HiddenBabel
    Commented Oct 11, 2019 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
    Commented Oct 11, 2019 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\$
    – user9207
    Commented Oct 11, 2019 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\$
    – user9207
    Commented Oct 11, 2019 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
    Commented Oct 11, 2019 at 22:17
0
\$\begingroup\$

Rust

Port of @Anders Kaseorg's Python answer in Rust.

/src/main.rs

use std::{cmp, env, f64, sync::mpsc, thread, time::Duration};
use statrs::{
    function::erf::erfc,
    distribution::{Normal, Univariate},
};
use ndarray::{Array, Array1, Axis, stack, concatenate, s, prelude::*};
use ndarray_stats::QuantileExt;



fn main() {
    let args: Vec<String> = env::args().collect();
    if args.len() < 2 {
        println!("Please provide a command line argument 'n'.");
        return;
    }
    let n: usize = match args[1].parse() {
        Ok(val) => val,
        Err(_) => {
            println!("Invalid argument. Please provide an integer.");
            return;
        }
    };
    let k = n * n / 4;
    let mut out = 0.0;

    if n < 97 {
        let mut a = Array1::<f64>::from_elem(1, 1.0);
        for i in 1..n + 1 {
            let ones = Array1::<f64>::from_elem(i, 1.0);
            let zeros = Array1::<f64>::from_elem(i, 0.0);
            let a_extended = concatenate(Axis(0), &[a.view(), ones.view()]).unwrap();
            let zeros_extended = concatenate(Axis(0), &[zeros.view(), a.view()]).unwrap();
            let mut a_diff = &a_extended - &zeros_extended;
            a_diff = a_diff.slice(s![..-1]).to_owned();
            a_diff = a_diff / (i as f64);
            let cumsum = |x: &Array1<f64>| {
                let mut sum = 0.0;
                x.mapv(|val| {
                    sum += val;
                    sum
                })
            };
            a = cumsum(&a_diff);
        }
        out = a[cmp::min(k, a.len() - 1)];
    } else {
        let mean = n as f64 * (n as f64 - 1.0) / 4.0;
        let variance = n as f64 * (n as f64 - 1.0) * (2.0 * n as f64 + 5.0) / 72.0;
        // println!("{:.3} {:.3}",mean,variance);
        out = erfc((mean - k as f64 - 0.5) / f64::sqrt(2.0 * variance)) / 2.0;
    }
    println!("{:.3}", out);
}

Cargo.toml

[package]
name = "rust_hello"
version = "0.1.0"
edition = "2021"

# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html

[dependencies]
# rand = "0.8.0"
# hyper = "0.13"
# tokio = { version = "0.2", features = ["full"] }
# rayon = "1.5.1"


ndarray = "0.15.4"
statrs = "0.13.0"
ndarray-stats = "0.4.0"

Building and running

# win10 environment

$ cargo build
$ target\debug\rust_hello.exe 500
$ target\debug\rust_hello.exe 100
$ target\debug\rust_hello.exe 18
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.