25 March 2017, a calm Saturday at 16:13

Lucky tickets problem

I solved since a while now (about half year ago) a problem on codeabbey called Lucky tickets advanced and I wanted to do a writeup.

So In russia bus tickets have six numbers, a ticket is called lucky if the sum of the first half of the numbers, is equals to the sum of the second half (ex. 123600 is a lucky ticket), so you are given a base $b$ and number of digits $n$ and you have to determine how many lucky tickets there are, at first glance this problem seems easy, but in reality it isn't for an interpreted language like python it may take an "eternity" and also the values of $n$ are usually >30, so an algorithm the magnitude of $O(b^n)$ won't quite cut it.

The problem remains in finding the coefficients of this polynomial

where: $r = n/2$

and: $s^n$ is the number of $r$ digit numbers having the sum of digits equal to $n$

It is proved that:

So this problem now resolves to doing simple polynomial multiplication.

I won't poste the code here because it's a against the codeabbey user agreement.

Also I wanted to note that for the easier, I was incapable of writing a fast enough solution in my python so I used the same solution as the advanced one I just had to see if $r<=1$ in that case I didn't do the polynomial multiplications I just calculated

For the detailed proof I suggest skimming through the first chapter of lando' book generating functions it's free.

Just wanted to also note that simplegen supports math formulas, get the last changes from github.