Блог пользователя rand

Автор rand, история, 2 года назад, По-русски

Привет codeforces!

Недавно я писал корневую декомпозицию + снм, причем использовать снм мне приходилось только в случае, если запрос содержит блок целиком. Какая будет асимптотика этого решения?

Вам может показаться очевидным, что асимптотика будет $$$O(n \cdot \sqrt{n \cdot \varphi^{-1} {(n)}})$$$ ($$$\varphi^{-1} {(n)}$$$ — обратная функция Аккермана).

Но на самом деле асимптотика — $$$O(n \cdot B \cdot \varphi^{-1}{(n)} + \frac{n ^ 2}{B})$$$ ($$$B$$$ — размер блока) и для того, чтобы достичь асимптотики с аккреманом под корнем нам нужно знать $$$\varphi^{-1}{(n)}$$$, чтобы поставить $$$B = \sqrt{n * \varphi^{-1} {(n)}}$$$, а для этого нужно знать $$$\varphi^{-1} {(n)}$$$. Таким образом все сводится к быстромы вычислению $$$\varphi^{-1} {(n)}$$$. Возможно ли это сделать?

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
2 года назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Is it theoretical or practical question?

For practical reasons, this should not bother you. For all reasonable values of $$$n \le 10^{18}$$$, $$$\alpha(n) \le 4$$$ (could be easily calculated, using the recurrence from wikipedia). You can put $$$B = \sqrt{n}$$$, or, if you want to achieve the optimal time, then you need to benchmark the code to get know, which parts of it are more fast and which are more slow to adjust the constant $$$B$$$ properly. It will be somewhere near $$$\sqrt{n}$$$, but could easily be $$$5$$$ times less than it, or $$$5$$$ times greater — all depends on the constant factors.

For theoretical reasons, it is easy to calculate the inverse Ackerman function say in $$$\mathcal{O}(n)$$$. You just need to follow the recurrence, and stop the calculations, once the values are too big. The following is a sketch of the solution, though you need to be careful with big integers and overflowing.

fun inverse_ackerman(int n) {
    int k = sqrt(n) + 10; // I am sure that inverse ackerman of n is less than k 
    int a[k][k] = {n + 1, n + 1, ...}; // n + 1 stands for infinity: any number greater than n
    for m = 0..k:
        for n = 0..k:
            if m == 0: a[m][n] = n + 1;
            else if n == 0: a[m][n] = a[m - 1][n + 1];
            else if (a[m][n - 1] < k) a[m][n] = a[m - 1][a[m][n - 1]];
    for x = 0..k: if a[x][x] >= n: return x;

The Ackerman function grows so fast that it should be not so hard to prove that the code above produces correct answer, though it doesn't calculates all of the required values.

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Известно, что обратная функция Аккермана вычислима за линейное время: doi.org/10.3233/FI-2021-2077.

Учитывая, что для нужной нам прямой функции Аккермана $$$\alpha \colon n \mapsto A(n,n)$$$ верно следующее

$$$ \alpha(0) = 1, \: \alpha(1) = 3, \: \alpha(2) = 7, \: \alpha(3) = 61, \: \alpha(4) = 2^{2^{65536}} - 3, $$$

то ее обратную можно в простейшем виде посчитать как (я использовал округление вверх для промежуточных значений)

template<class T>
constexpr int inverse_ackerman(T x)
{
  if (x <= T(1)) return 0;
  if (x <= T(3)) return 1;
  if (x <= T(7)) return 2;
  if (x <= T(61)) return 3;
  return 4;
}

Можно, конечно, использовать линейную или еще какую-нибудь интерполяцию, что приведет к

template<class T>
constexpr float inverse_ackerman(T x)
{
  if (x <= T(1)) return 0.0f;
  if (x == T(2)) return 0.5f;
  if (x == T(3)) return 1.0f;
  if (x == T(4)) return 1.25f;
  if (x == T(5)) return 1.5f;
  if (x == T(6)) return 1.75f;
  if (x == T(7)) return 2.0f;
  if (x <= T(61)) return 2.0f + (float(x) - 7.0f) / 54.0f;
  return 4.0f;
}

P. S. $$$B = \sqrt{n / \alpha(n)}$$$.