0
$\begingroup$

I'm working on an algorithmic problem for HackerRank: https://www.hackerrank.com/contests/projecteuler/challenges/euler106/problem

The broad overview of the problem is finding how many evenly-sized subset pairs for a T-sized set of ascending values need to be tested for equality. I've gotten quite far, boosting my maximum n from 15 to 1500 to being able to get T = 10000 within 10ish seconds. But the problem requires being able to get solutions for T up to 10^6! This seems like it requires something that needs to be extremely optimized, as the software hangs and is far too slow for that input.

I noticed, after searching for patterns in sums and groupings with the ambiguous subset-pairs, that there were many figurate numbers and sums of figurate numbers. The general algorithm I found was, for each subset size s from 2 to T/2, the values followed a figurate pattern scaling with T. The first combination represents a multiplier that is the sum of the s-1 terms of the s-figurate numbers. Then, the second combination is a sum of the (s+2)-figurate numbers. $$f(T) = \sum_{s=2}^{\lfloor\frac{T}{2}\rfloor}{2s-1 \choose s-2}{T \choose T-2s}$$ That's some background, but there may yet be an optimization that I haven't seen or simply don't know about. However, this is the closest I've gotten after eliminating many computational loops, so I want to exhaust this line of thinking first. Are there any more efficient ways to reduce this? I understand that $T!$ can come out of the right combination, and that $2s!$ and $(2s-1)!$ can also simplify after applying the nCr factorial equation. But after that, I'm left with something like this: $$f(T) = \frac{T!}{2}\sum_{s=2}^{\lfloor\frac{T}{2}\rfloor}\frac{1}{s^2(s^2-1)((s-2)!)^2(T-2s)!}$$

This has not changed the efficiency of the algorithm, so I either need help on the algebra or a different approach. How can I generalize some more of the repeated factorials do I'm not doing them T/2 times? I'm just not sure how to deal with the denominator here.

Edit: Somebody pointed out to me this https://oeis.org/A304011 Which is pretty much the solution, but they are still using a recursive relationship, albeit much less computationally intense than mine. I hate to have the answer in my hand like this, so I guess I wonder how they derived it.

$\endgroup$
2
  • $\begingroup$ Hint: $f(T)$ is a convolution of two sequences. Use fast Fourier transform to compute this convolution in $O(T\log T)$ time. This should be sufficient for $T\le 10^6$. $\endgroup$
    – Mike Earnest
    Commented Aug 13, 2023 at 16:09
  • $\begingroup$ Thanks, Mike. The mathematics have definitely gone beyond my middling algebraic skills, so I guess I'll have to do some reading to figure out how a Fourier transform even works. $\endgroup$
    – Andy Zou
    Commented Aug 13, 2023 at 16:44

1 Answer 1

Reset to default
1
$\begingroup$

$$A_s={2s-1 \choose s-2}{T \choose T-2s}$$ $$A_s=\frac{\Gamma (T+1)}{2}\frac{1}{s\, \Gamma (s-1)\, \Gamma (s+2)\, \Gamma (T+1-2s)}$$ For the summation, I do not see how you could avoid Gaussian hypergeometric functions.

$$f(2T)=\frac{1}{2} \left(1+\, _2F_1\left(-T+\frac{1}{2},-T;1;4\right)-2 \, _2F_1\left(-T+\frac{1}{2},-T;2;4\right)\right)$$

$$f(2T+1)=\frac{1}{2} \left(1+\, _2F_1\left(-T-\frac{1}{2},-T;1;4\right)-2 \, _2F_1\left(-T-\frac{1}{2},-T;2;4\right)\right)$$

$\log(f(2T))$ and $\log(f(2T+1))$ are almost linear functions of $T$ (same slope $\sim 2.187$)

$\endgroup$
2
  • $\begingroup$ Someone showed me the OEIS page; I'm not familiar with hypergeometric functions, but I also see it showing up on the page. Does that align with what you've described? $\endgroup$
    – Andy Zou
    Commented Aug 13, 2023 at 5:14
  • $\begingroup$ @AndyZou. It is the same. Notice the approximation $\frac{3^{n+\frac{1}{2}}}{4 \sqrt{\pi n}}$ $\endgroup$
    – Claude Leibovici
    Commented Aug 13, 2023 at 5:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .