Introduction

Learning from problem-solving can be approached in various ways. One effective method is to first understand a new technique and then apply it to different problems. Alternatively, one might focus on a single problem, exploring numerous unique solutions and considering where else these methods could be useful. Today, we will delve into a mathematical approach to solve the “Number of Ways to Rearrange Sticks With K Sticks Visible” problem (LeetCode 1866), showcasing how a specific mathematical strategy originating from ideas similar to the Fast Fourier Transform can be applied to this fun challenge.

Our approach to solving the problem involves use of polynomial manipulations, making computational algebra systems like Magma particularly suitable. While Magma isn’t a standard language for platforms like LeetCode, its simplicity and efficiency in handling such algebraic problems are noteworthy. This method could also be replicated in Python using libraries like NumPy, though with additional complexity. The essence of this approach lies not in the coding language used, but in the application of mathematical ideas to solve the problem.

The Basic Recursion

So given two integer n, k the question is to find the number S_n,k of permutations of n elements with exactly k elements that have no elements from the left bigger themselves. The key for this challenge is to notice that S_n,k satisfies the following recurrent relation:

S_n,k = S_{n – 1, k – 1} + (n – 1)S_{n – 1,k}.

This relation can be used to solve the problem with the dynamic programming approach:

p := 10^9 + 7;
function RearrangeSticksDP(n, k)
    Zp := Integers(p);
    dp := ZeroMatrix(Zp, n+1, k+1);

    dp[1,1] := 1;
    for j in [1..k] do
        for i in [j..n] do
            dp[i+1,j+1] +:= dp[i,j] + dp[i,j+1] * Zp!(i-1);
        end for;
    end for;

    return dp[n+1,k+1];
end function;

n := 1000;
k := 379;

print RearrangeSticksDP(n, k);

The Magma code can be run using this free online calculator available. In our random test case for n = 1000 and k = 379 this gives the value 701573779(remember that we return result modulo 10⁹ + 7) which coincides with the value provided by the Leetcode’s test engine. An interesting note is that the online calculator also gives us Time and Memory consumptions: Total time: 0.460 seconds; Total memory usage: 32.09MB.

This solution has a time complexity of O(n*k) which implies that if we increase each argument tenfold, the expected wait time for the computation would be approximately 100 times longer. Indeed for (n, k) =(10000,3799) we get: Total time: 46.390 seconds; Total memory usage: 177.09MB

Polynomial Multiplication Part 1

A natural idea (that also appeared in the solutions section) is to try to replace the recursion with the polynomial multiplication. Because the generating function:

x(x+1)(x+2) … (x + (n-1))

obviously satisfies the same recurrent relation and initial values its k-th coefficient should be equal to the S_n,k. Of course if we naively multiply n polynomials( each of degree less than n) we expect about O(n³) actions and therefore this solution will be infeasible. But using Fast Fourier Transform we can achieve one polynomial multiplication with O( n log(n)) and therefore the total solution will be about O(n² log(n)). A good thing about using Magma is that it uses built-in fast polynomial multiplication, so we can write a very compact code that solves the challenge and compare the performance:

p := 10^9 + 7;
P<x> := PolynomialRing(Integers(p));

function ComputeCoefficient(i, k)
    poly := 1; 
    for j in [1..i] do
        poly := poly * (x + j - 1);
    end for;
    return Coefficients(poly)[k+1];
end function;

n := 10000;
k := 3799;

print ComputeCoefficient(n, k);

And on this input it produces the same result as above, but about a few times faster than the direct DP solution(even though we expected it to be a bit slower): Total time: 13.380 seconds; Total memory usage: 32.09MB.

Polynomial Multiplication Part 2

So far, we haven’t improved the theoretical running time compared to the DP solution. However, expressing the problem in polynomial form allows us to uncover some hidden symmetries.

So we need to compute:

x(x+1)(x+2)(x+3) … (x + (n-1)).

Let’s split the product on two parts:

f(x) = x(x+2)(x + 4)…

g(x) = (x+1)(x + 3)(x + 5)…

The key observation is that g(x) = f(x + 1) when n is even. But if we look carefully at the product x(x+2)(x + 4)… we can see that it is essentially the same polynomial we started with: replace x with x = 2y and divide each bracket by 2 you get y(y+1)(y+2)… same polynomial but the degree is twice as small.

This means that instead of n multiplication we only need log(n) which reduces the total time to O(n log²(n)). The code is still compact and quite readable:

p := 10^9 + 7;
P<x> := PolynomialRing(Integers(p));

function ComputeF(n)
    if n eq 1 then
        return x;
    end if;

    if IsOdd(n) then
        return (x + (n-1)) * ComputeF(n - 1);
    end if;

    h := ComputeF(n div 2);
    scaleFactor := 2^n;

    return scaleFactor * Evaluate(h, x/2) * Evaluate(h, (x + 1)/2);
end function;

n := 10000;
k := 3799;

Coefficients(ComputeF(n))[k+1];

And the results are about 10 times faster then the original DP solution: Total time: 3.600 seconds; Total memory usage: 32.09MB.

Final Remarks

A seasoned reader might point out an alternative method for multiplying n polynomials efficiently, in O(n log²n) time, applicable in a broader context. This involves dividing the polynomials into two halves, recursively multiplying each half, and then combining the results. Indeed, this is a viable and effective strategy in the general case. However, the technique described in Part 2 holds its own unique appeal due to its elegance…