Statistician's (maybe) fast C solution


  • 2
    H

    This should be fast. It's already consuming 0ms so I have no motive to further optimize it. As a statistician, I solved this problem by counting the possible ways of painting.

    The answer is $\sum{d=0}^{\lfloor n/2 \rfloor} f(n,d)(k \cdot (k-1)^{n-d-1})$. (Oh! I wish TeX is supported here...) And f(n,d) is defined to be the possible ways to have d adjacent same-color posts.

    long factorial(int x) {
        long res = 1;
        if (0 == x)
            return 1;
        for (int i = 1; i != x+1; ++i) {
            res *= i;
        }
        return res;
    }
    
    int ipow(int x, int y) {
        long res = x;
        if (0 == y)
            return 1;
        for (int i = 1; i != y; ++i)
            res *= x;
        return res;
    }
    
    int f(int n, int d) {
        long res = 1;
        for (int i = n - d; i != n - 2*d; --i) {
            if (i == d) {
                res = res / factorial(n-2*d);
                return res;
            }
            res *= i;
        }
        res = res / factorial(d);
        return res;
    }
    
    int numWays(int n, int k) {
        int sum = 0;
        int halfn = n/2;
        if (n == 0) return 0;
        // d is the number of adjacent same color posts
        for (int d = 0; d != halfn+1; ++d) {
            sum += k * ipow(k-1, n-d-1) * f(n,d);
        }
        return sum;
    }

  • 0

    I'd say this is actually a pretty slow C solution. To see it, rename your numWays to numWays1 and add this wrapper:

    int numWays(int n, int k) {
        for (int i=0; i<10000; ++i)
            numWays1(n, k);
        return numWays1(n, k);
    }
    

    I submitted that three times, got 128 ms all three times. Then I instead used the following simple solution, which took 20, 16 and 20 ms in its three attempts:

    int numWays2(int n, int k) {
        int a = 0, b = k, c = k*k;
        while (n--) {
            a = b;
            b = c;
            c = (a + b) * (k - 1);
        }
        return a;
    }
    

  • 0
    H

    Thanks for pointing this out. This is expected. My solution is slow because of the simple implementation of power and factorial, both of which are O(n) in the program. If they can be replaced with an O(1) version, my solution has the potential to be fast because it is actually O(n/2) rather than some other solution's O(n). But it only makes sense when n is very large.

    Anyway, we have already seen an O(1) solution on this forum so my solution wasn't meant to be the fastest one. The original intention of my submission here is to provide yet another way to approach this problem.


  • 0

    Yeah, I think it really is a new approach, and interesting. Your f function is not quite obvious, though, I think it would be better to show/mention outside the code that it's "n-d choose d" and then just use that directly (because binomial coefficients are standard stuff and people are already familiar with them):

    sum += k * ipow(k-1, n-d-1) * choose(n-d, d);
    

    With:

    int choose(int n, int k) {
        if (k > n-k)
            k = n-k;
        long res = 1;
        for (int i=0; i<k; ++i)
            res = res * (n-i) / (i+1);
        return res;
    }

  • 0

    TeX would be nice, but at least we can use Unicode and sub/sup tags :-)

    Σ d = 0 to ⌊n/2⌋ k·(k-1)n-d-1·(n-d choose d)


  • 1

    A Python implementation (but using "choose" instead of your "f"):

    def numWays(self, n, k):
        f = math.factorial
        def choose(n, k):
            return f(n) / f(k) / f(n-k)
        return n and sum(k * (k-1)**(n-d-1) * choose(n-d, d)
                         for d in range(n/2 + 1))

  • 0
    H

    Wow, this is awesome. Thanks @StefanPochmann !


  • 0
    H

    Can't agree more. :)


  • 0
    H

    This is a very neat solution. I've learned some useful Python tricks from it. For example, this choose() function cannot work in C because the factorial of 43 (from one of the test cases) is 60415263063373835637355132068513997507264512000000000L, which is way larger than even long integer in C. In my C version, I had to solve this problem by reduction of fractions before calculating the factorials. I'm amazed to learn that Python can support such large integers effortlessly.


  • 0

    Yep, just one of Python's many nice features :-)


  • 0
    H

    What does "n and sum(...)" mean? I briefly searched but can't find a definitive answer.


  • 0

    It's a logical conjunction, but in Python you don't just get True or False but one of the operands. If n is zero, then the result is zero. Otherwise, the result is the second operand, the sum.

    You can find more here:
    https://docs.python.org/2/reference/expressions.html#boolean-operations


  • 0
    H

    Much thanks!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.